Depth-first search

Depth-first search - Definition
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph.

Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph.

Depth-first search
Depth-first search always expands one of the nodes at the deepest level of the tree. Only when the search hits a dead end (a nongoal node with no expansion) does the search go back and expand nodes at shallower levels.

Depth-first search tree with backtracking can be used to implement systematic generate-and-test procedure.

bounded depth-first search a depth-first search in which a bound is placed on the number of operator applications that can be considered; any sequence of operations that exceeds the depth bound is considered a failure.

Two basic types of brute force algorithms are the depth-first and breadth-first. Depth-first searches are expanded down first then back up and across (Mathews, 2000a).

Many algorithms textbooks describe graph searching algorithms that do not use heuristics (breadth-first search, depth-first search, Dijkstra's). Reading about them may help in understanding A*, which is a variant of Dijkstra's.

But this may cause problems in returning valid solutions at all, since you've been trimming the search space! Also, by making it a depth-first search rather than breadth-first, you can reduce the need for complex data-structures, ...

See also: Search algorithm, Hill climbing, Artificial intelligence, Dynamic programming, Breadth-first search