Depth-First

Home * Search * Depth-First

Depth-First Node order 1 Depth-First Node order ¹

Depth-first search from Wikipedia ↩︎

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.

Contents

Depth-Limited Search

`Breadth-First Node order `` ` Breadth-First Node order ¹

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.

Publications

1970 ...

Toshihide Ibaraki (1978). Depth-m search in branch-and-bound algorithms. International Journal of Parallel Programming, Vol. 7, No. 4

1980 ...

Richard Korf (1984). The Complexity of Brute Force Search. Technical Report, Department of Computer Science, Columbia University ² ³
Richard Korf (1985). Depth-first Iterative-Deepening: An Optimal Admissible Tree Search. pdf from CiteSeerX
Stephen F. Wheeler (1985). 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 University
Hermann Kaindl, Helmut Horacek, Marcus Wagner (1986). Selective Search versus Brute Force. ICCA Journal, Vol. 9, No. 3

1990 ...

Steven Skiena (1990). 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,
Nageshwara Rao Vempaty, Vipin Kumar, Richard Korf (1991). Depth-First vs Best-First Search. AAAI-91, pdf
Weixiong Zhang, Richard Korf (1993). Depth-first vs. best-first search: New results. AAAI-93
Matthew L. Ginsberg (1993). Essentials of artificial intelligence. Morgan Kaufmann Publishers, 3.2 Depth-First Search
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

2000 ...

Ayumu Nagai, Hiroshi Imai (2002). Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees. IEICE transactions on information and systems

2010 ...

Tomoyuki Kaneko (2010). Parallel Depth First Proof Number Search. AAAI-2010 » Parallel Search, Proof-Number Search
Kunihito Hoki, Tomoyuki Kaneko, Akihiro Kishimoto, Takeshi Ito (2013). Parallel Dovetailing and its Application to Depth-First Proof-Number Search. ICGA Journal, Vol. 36, No. 1 ⁴
Tom Everitt, Marcus Hutter (2015). Analytical Results on the BFS vs. DFS Algorithm Selection Problem. Part I: Tree Search. Australasian Conference on Artificial Intelligence, pdf
Tom Everitt, Marcus Hutter (2015). Analytical Results on the BFS vs. DFS Algorithm Selection Problem: Part II: Graph Search. Australasian Conference on Artificial Intelligence
Chao Gao, Martin Müller, Ryan Hayward (2017). Focused Depth-first Proof Number Search using Convolutional Neural Networks for the Game of Hex. IJCAI 2017