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
- 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.
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.