Next: Exam-like questions Up: Simple Search Techniques Previous: Simple Search Techniques

Depth first vs Breadth first Search

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.



Next: Exam-like questions Up: Simple Search Techniques Previous: Simple Search Techniques


alison@
Fri Aug 19 10:42:17 BST 1994