Depth-First refers to node traversal algorithms of tree like data structures like search trees. Depth-first examines child nodes before siblings and can easily implemented with recursion using a stack of nodes. It therefor has moderate memory requirements, since only one path from the root to a leaf is kept in memory, which grows proportional with search depth.

Depth-First Node order ^{[1]}

The depth-limited search, to make the depth-first search find a solution within the depth limit, is the most common search algorithm in computer chess, as described in minimax, alpha-beta and its enhancements. Iterative deepening is a state space search strategy in which a depth-limited search is run repeatedly, with a cumulative node order effectively breadth-first.

Ayumu Nagai, Hiroshi Imai (1999). Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees. Proceedings of the Korea-Japan Joint Workshop on Algorithms and Computation

Home * Search * Depth-FirstDepth-Firstrefers to node traversal algorithms of tree like data structures like search trees. Depth-first examines child nodes before siblings and can easily implemented with recursion using a stack of nodes. It therefor has moderate memory requirements, since only one path from the root to a leaf is kept in memory, which grows proportional with search depth.^{[1]}^{[2]}## Table of Contents

## See also

## Publications

1985).Depth-first Iterative-Deepening: An Optimal Admissible Tree Search. pdf from CiteSeerX1985).A performance benchmark of the alpha-beta procedure on randomly ordered non-uniform depth-first game-trees generated by a chess program. M.Sc. thesis, East Texas State University1986).Selective Search versus Brute Force.ICCA Journal, Vol. 9, No. 31990).Breadth-First and Depth-First Search.§3.2.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 95-97,1993).Depth-first vs. best-first search: New results. AAAI'931993).Essentials of artificial intelligence. Morgan Kaufmann Publishers, ISBN13: 9781558602212, 3.2 Depth-First Search1999).Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees. Proceedings of the Korea-Japan Joint Workshop on Algorithms and Computation2002).Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees. IEICE transactions on information and systems2010).Parallel Depth First Proof Number Search. AAAI 2010 » Parallel Search, Proof-number Search2013).Parallel Dovetailing and its Application to Depth-First Proof-Number Search. ICGA Journal, Vol. 36, No. 1^{[3]}## External Links

## References

## What links here?

Up one Level