Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

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



Add Comment

No comments.