authors 
Galle, Per 
year 
1989 
title 
Branch & Sample : A Simple Strategy for Constraints Satisfaction 
source 
March, 1989. 29: pp. 395408 : 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 breathfirst 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 
Contenttype: text/plain

last changed 
1999/02/12 14:08 
