Search Order

So far we have not specified in which order search trees are explored. Although this order has no impact on the shape and size of a search tree, it does have an impact on the time and memory resources needed to find one or all solutions: We will assume that the search engine explores the search trees always in a depth-first fashion. Moreover, when the branching strategy results in n branches for some node, the search engine will explore those branches from left to right (i.e. from branch number one to number n).

The above assumptions ensure that the exploration of a search tree is a deterministic process, provided the branching strategy generating the constraints to branch with is deterministic.

Andreas Rossberg 2006-08-28