2.9 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 engine distributes with a constraint , it explores the space obtained with first and the space obtained with $\neg C$ second.

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