# Catalogue of Artificial Intelligence Techniques

View Maths as: Images | MathML

## Depth-first Search

**Aliases:**
Chronological Backtracking

**Keywords:**
graph searching

### Categories: Search

Author(s): **Dave Plummer**

An uninformed graph searching strategy which searches the graph by exploring each possible path through it until either the required solution or a previously encountered node is encountered. The nodes are expanded in order of depth: with the deepest node expanded first and nodes of equal depth expanded in an arbitrary order. To prevent searching of an infinite path, a depth-bound is usually fixed and nodes below this depth are never generated, thus the strategy is neither guaranteed to produce the shortest path to the solution if one exists, nor to find a solution even if one exists. (See also Iterative Deepening.)

### References:

- Korf, R.E.,
*Search: A Survey of Recent Results*,*Exploring Artificial Intelligence (Survey talks from the National Conferences on Artificial Intelligence)*(Shrobe, H.E. , ed.), Morgan Kaufmann, San Mateo, California, 1988, pp.197--237 (Chapter 6).

### Comments:

No comments.