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:

• If we are only interested in one solution, there is no need to explore the entire search tree. Ideally, we would just explore the path leading from the root to the solution.
• If we are interested in all solutions, we need to explore the entire search tree. However, whether we explore the tree in depth-first or breadth-first manner will make a big difference in the memory needed. The memory requirements of breadth-first exploration are typically exponentially larger than those of depth-first exploration.

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.