Difference between revisions of "Depth-First"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Search * Depth-First''' FILE:Depth-first-tree.svg|border|right|thumb|Depth-First Node order <ref>[https://en.wikipedia.org/wiki/Depth-first_sear...") |
GerdIsenberg (talk | contribs) m |
||
| Line 28: | Line 28: | ||
* [[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 | * [[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 | ||
* [[Ayumu Nagai]], [[Hiroshi Imai]] ('''2002'''). ''[http://ci.nii.ac.jp/naid/110006376599 Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees]''. [http://ci.nii.ac.jp/vol_issue/nels/AA10826272/ISS0000408668_en.html IEICE transactions on information and systems] | * [[Ayumu Nagai]], [[Hiroshi Imai]] ('''2002'''). ''[http://ci.nii.ac.jp/naid/110006376599 Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees]''. [http://ci.nii.ac.jp/vol_issue/nels/AA10826272/ISS0000408668_en.html IEICE transactions on information and systems] | ||
| − | * [[Tomoyuki Kaneko]] ('''2010'''). ''Parallel Depth First Proof Number Search''. [http://www.informatik.uni-trier.de/~ley/db/conf/aaai/aaai2010.html#Kaneko10 AAAI 2010] » [[Parallel Search]], [[Proof- | + | * [[Tomoyuki Kaneko]] ('''2010'''). ''Parallel Depth First Proof Number Search''. [http://www.informatik.uni-trier.de/~ley/db/conf/aaai/aaai2010.html#Kaneko10 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#36_1|ICGA Journal, Vol. 36, No. 1]] <ref>[https://en.wikipedia.org/wiki/Dovetailing_%28computer_science%29 Dovetailing (computer science) from Wikipedia]</ref> | * [[Kunihito Hoki]], [[Tomoyuki Kaneko]], [[Akihiro Kishimoto]], [[Takeshi Ito]] ('''2013'''). ''Parallel Dovetailing and its Application to Depth-First Proof-Number Search''. [[ICGA Journal#36_1|ICGA Journal, Vol. 36, No. 1]] <ref>[https://en.wikipedia.org/wiki/Dovetailing_%28computer_science%29 Dovetailing (computer science) from Wikipedia]</ref> | ||
Revision as of 20:30, 13 May 2018
Depth-First Node order [1]
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-Limited Search
Breadth-First Node order [2]
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
- 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
- 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,
- 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, ISBN13: 9781558602212, 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
- 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
- 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 [3]
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
