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/html
Access Temporarily Restricted
Access Temporarily Restricted
Too many requests detected. Please wait 85940 seconds or verify that you are a human.
If you are a human user and need immediate access, you can click the button below to continue:
If you continue to experience issues, please open a ticket at
papers.cumincad.org/helpdesk
|
last changed |
1999/02/12 15:08 |
|