| authors |
Galle, Per |
| year |
1989 |
| title |
Branch & Sample : A Simple Strategy for Constraints Satisfaction |
| source |
March, 1989. 29: pp. 395-408 : ill. includes bibliography |
| summary |
Many constraint satisfaction problems have too many solutions for exhaustive generation. Optimization techniques may help in selecting a small number of solutions for consideration, but a reasonable measure of optimality is not always at hand. A simple algorithm called Branch & Sample is suggested as an alternative to optimization. Combining breath-first and depth- first search Branch & Sample finds solution distributed over the search tree. The aim is to obtain a limited set of solutions that corresponds well to the intuitive motion of a representative, uniformly scattered sample. A precise definition of this notion is discussed in relation to the algorithm whose effect is illustrated by two geometric design problems. The performance of the algorithm is evaluated and it is concluded that Branch & Sample is applicable to certain types of problems, and refinements can extend the scope of application |
| keywords |
automation, design, constraints, backtracking |
| series |
CADline |
| references |
Content-type: text/plain
|
| last changed |
1999/02/12 15:08 |
|
