# Depth-First

Revision as of 23:55, 9 March 2019 by GerdIsenberg (talk | contribs)

**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

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.

# See also

# 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^{[3]}^{[4]} - 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^{[5]} - 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

# External Links

- Depth-first search from Wikipedia
- Depth-limited search from Wikipedia
- Iterative deepening depth-first search from Wikipedia
- Depth-First Traversal from Wolfram MathWorld
- Boost Graph Library: Depth-First Search
- depth-first search from Dictionary of Algorithms and Data Structures by Paul E. Black, National Institute of Standards and Technology
- Flat Earth Society & Ernst Reijseger - Down Deep, Jazz Middelheim 2012, YouTube Video

# References

- ↑ Depth-first search from Wikipedia
- ↑ Breadth-first search from Wikipedia
- ↑ quoted by Hans Berliner, Gordon Goetsch (
**1985**).*A Study of Search Methods : The Effect of Constraint Satisfaction and Adventurousness*. pdf - ↑ Paper is mentioned by Richard Korf at Judea Pearl Symposium, 2010
- ↑ Dovetailing (computer science) from Wikipedia