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 mathend000# branches for some node, the search engine will explore those branches from left to right (i.e. from branch number one to number n mathend000#).

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.

Guido Tack 2007-04-26