The Branch & Sample algorithm (B&S) offers a search
strategy potentially applicable to constraint satisfaction
problems (CSPs) whose variables are interdependent in terms of the
constraints to be satisfied. CSPs are often combinatorially
explosive (have very large numbers of solutions), and the basic
idea of the algorithm is to overcome this by generating a
relatively small sample of solutions which are in a certain sense
representative of the entire solution space, and scattered over
it. (B&S can also handle CSPs with no solutions, or just a
suitable number which can be exhaustively generated.) This Web
publication presents B&S from the point of view of practical
programming. The algorithm is incrementally developed from a
simple sketch to full application independent source code in C,
available free of charge on gentlemanly conditions. Concerns of
user-machine interaction are introduced as part of the algorithm
development, and practical advice on how to incorporate B&S
into an application program is offered by way of example. For the
benefit of non-C programmers, the essentials of C notation is
briefly explained.

Publication status | Published - 1999 |
---|