CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

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 14:08
HOMELOGIN (you are user _anon_517689 from group guest) Works Powered by SciX Open Publishing Services 1.002