Depth first and breadth first search both have some advantages.
Which is best depends on properties of the problem you
are solving. For tree search at least, depth first search
tends to require less memory, as you only need to record nodes
on the `current' path. If there are lots of solutions, but
all at a comparable `depth' in the tree, then you may hit on a
solution having only explored a very small part of the tree.
On the other hand, that may not be the best solution.
Also, depth first search may get stuck exploring long (and potentially
infinite) blind alleys, when there is in fact a solution path
of only one or two steps. (We could prevent this by setting a *depth
limit* to our search, but then it wouldn't be exhaustive.).
So depth first
is good when there are many possible solutions, and you only want one (and
you don't care which one). It may be less appropriate when there is
only one solution, or if you want the shortest one.

Breadth first search may use more memory, but will not get stuck in blind alleys, and will always find the shortest path first (or at least, the path that involves the least number of steps). It may be more appropriate when exploring very large search spaces where there is an expected solution which takes a relatively small number of steps, or when you are interested in all the solutions (perhaps up to some depth limit).

To summarise so far: Search techniques are used in AI to find a sequence of steps that will get us from some initial state to some goal state(s). You can either search backwards, from the goal state, or forwards, from the initial state. And whichever direction you choose you can use various search algorithms to do the search. We've so far discussed simple breadth first search and depth first search. These are both systematic, exhaustive search techniques that will eventually try all the nodes in the search space (if its finite!). The appropriate direction of search and the appropriate algorithm depend on the nature of the problem you are trying to solve, and in particular the properties of the search space.

Fri Aug 19 10:42:17 BST 1994