| authors |
Galle, Per |
| year |
1987 |
| title |
Branch & Sample : Systematic Combinatorial Search without Optimization |
| source |
73 p. 1987. DIKU Research Report No. 87/5. CADLINE has abstract only |
| summary |
Many constraint satisfaction problems are combinatorically explosive, i.e. have far too many solutions. Optimization techniques may help in selecting solutions for consideration, but a reasonable measure of optimality is not always at hand. The branch & sample algorithm is presented as an alternative to optimization. If the constraints themselves limit the solution set sufficiently, the algorithm finds all solutions, but otherwise a suitable number of solutions (determined by the user) is generated, such that each new solution has a maximal distance to those already generated. The distance measure used is a so called ultrametric distance expressible in terms of the search tree: solutions are viewed as m-tuples of fixed length, each of whose m decision variables corresponds to a level in the search tree. The distance between two solutions is the number of edges from their leaf nodes to the closest common predecessor node in the tree. For problems whose decision variables depend on each other (as is often the case) the set of solutions generated in this way corresponds well to the intuitive notion of a 'representative sample.' The principles of Branch & Sample are first introduced informally, then the algorithm is developed by stepwise refinement, and two examples of its use are given. A fully tested application-independent implementation of the algorithm in C is given as an appendix |
| keywords |
algorithms, combinatorics, search, constraints, floor plans, layout, synthesis, architecture |
| series |
CADline |
| references |
Content-type: text/plain
|
| last changed |
1999/02/12 15:08 |
|
