25,161
edits
Changes
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..."
'''[[Main Page|Home]] * [[Search]] * Depth-First'''
[[FILE:Depth-first-tree.svg|border|right|thumb|Depth-First Node order <ref>[https://en.wikipedia.org/wiki/Depth-first_search Depth-first search from Wikipedia]</ref> ]]
'''Depth-First''' refers to [[Node|node]] traversal algorithms of tree like data structures like [[Search Tree|search trees]]. Depth-first examines child nodes before [[Sibling Node|siblings]] and can easily implemented with [[Recursion|recursion]] using a [[Stack|stack]] of nodes. It therefor has moderate [[Memory|memory]] requirements, since only one path from the [[Root|root]] to a [[Leaf Node|leaf]] is kept in memory, which grows proportional with [[Depth|search depth]].
=Depth-Limited Search=
[[FILE:Breadth-first-tree.svg|border|right|thumb|Breadth-First Node order <ref>[https://en.wikipedia.org/wiki/Breadth-first_search Breadth-first search from Wikipedia]</ref> ]]
The [https://en.wikipedia.org/wiki/Depth-limited_search 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|minimax]], [[Alpha-Beta|alpha-beta]] and its enhancements. [[Iterative Deepening|Iterative deepening]] is a [https://en.wikipedia.org/wiki/State_space_search state space search] strategy in which a depth-limited search is run repeatedly, with a cumulative node order effectively [https://en.wikipedia.org/wiki/Breadth-first_search breadth-first].
=See also=
* [[Alpha-Beta]]
* [[Backtracking]]
* [[Best-First]]
* [[Depth]]
* [[Iterative Deepening]]
* [[Minimax]]
* [[Proof-Number Search]]
=Publications=
* [[Richard Korf]] ('''1985'''). ''Depth-first Iterative-Deepening: An Optimal Admissible Tree Search''. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.288&rep=rep1&type=pdf pdf] from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.288 CiteSeerX]
* [[Stephen F. Wheeler]] ('''1985'''). ''[https://www.researchgate.net/publication/34381496_A_performance_benchmark_of_the_alpha-beta_procedure_on_randomly_ordered_non-uniform_depth-first_game-trees_generated_by_a_chess_program 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, [https://en.wikipedia.org/wiki/Texas_A%26M_University%E2%80%93Commerce East Texas State University]
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[Steven Skiena]] ('''1990'''). ''Breadth-First and Depth-First Search.'' §3.2.5 in [http://www.amazon.com/exec/obidos/ASIN/0521806860/ref=nosim/weisstein-20 Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica]. Reading, MA: Addison-Wesley, pp. 95-97,
* [[Mathematician#WZhang|Weixiong Zhang]], [[Richard Korf]] ('''1993'''). ''[http://dl.acm.org/citation.cfm?id=1867385 Depth-first vs. best-first search: New results]''. [http://www.aaai.org/Conferences/AAAI/aaai93.php AAAI'93]
* [[Matthew L. Ginsberg]] ('''1993'''). ''[http://searchworks.stanford.edu/view/2746445 Essentials of artificial intelligence]''. [https://en.wikipedia.org/wiki/Morgan_Kaufmann_Publishers 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'''). ''[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-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>
=External Links=
* [https://en.wikipedia.org/wiki/Depth-first_search Depth-first search from Wikipedia]
* [https://en.wikipedia.org/wiki/Depth-limited_search Depth-limited search from Wikipedia]
* [https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search Iterative deepening depth-first search from Wikipedia]
* [http://mathworld.wolfram.com/Depth-FirstTraversal.html Depth-First Traversal] from [http://mathworld.wolfram.com/ Wolfram MathWorld]
* [http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/depth_first_search.html Boost Graph Library: Depth-First Search]
* [http://xlinux.nist.gov/dads/HTML/depthfirst.html depth-first search] from [http://xlinux.nist.gov/dads/ Dictionary of Algorithms and Data Structures] by [http://hissa.nist.gov/~black/ Paul E. Black], [https://en.wikipedia.org/wiki/National_Institute_of_Standards_and_Technology National Institute of Standards and Technology]
* [[Videos#FlatEarthSociety|Flat Earth Society]] & [https://en.wikipedia.org/wiki/Ernst_Reijseger Ernst Reijseger] - Down Deep, [https://en.wikipedia.org/wiki/Jazz_Middelheim Jazz Middelheim] 2012, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=NpQnmYP4aT8|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one Level]]'''
[[FILE:Depth-first-tree.svg|border|right|thumb|Depth-First Node order <ref>[https://en.wikipedia.org/wiki/Depth-first_search Depth-first search from Wikipedia]</ref> ]]
'''Depth-First''' refers to [[Node|node]] traversal algorithms of tree like data structures like [[Search Tree|search trees]]. Depth-first examines child nodes before [[Sibling Node|siblings]] and can easily implemented with [[Recursion|recursion]] using a [[Stack|stack]] of nodes. It therefor has moderate [[Memory|memory]] requirements, since only one path from the [[Root|root]] to a [[Leaf Node|leaf]] is kept in memory, which grows proportional with [[Depth|search depth]].
=Depth-Limited Search=
[[FILE:Breadth-first-tree.svg|border|right|thumb|Breadth-First Node order <ref>[https://en.wikipedia.org/wiki/Breadth-first_search Breadth-first search from Wikipedia]</ref> ]]
The [https://en.wikipedia.org/wiki/Depth-limited_search 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|minimax]], [[Alpha-Beta|alpha-beta]] and its enhancements. [[Iterative Deepening|Iterative deepening]] is a [https://en.wikipedia.org/wiki/State_space_search state space search] strategy in which a depth-limited search is run repeatedly, with a cumulative node order effectively [https://en.wikipedia.org/wiki/Breadth-first_search breadth-first].
=See also=
* [[Alpha-Beta]]
* [[Backtracking]]
* [[Best-First]]
* [[Depth]]
* [[Iterative Deepening]]
* [[Minimax]]
* [[Proof-Number Search]]
=Publications=
* [[Richard Korf]] ('''1985'''). ''Depth-first Iterative-Deepening: An Optimal Admissible Tree Search''. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.288&rep=rep1&type=pdf pdf] from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.288 CiteSeerX]
* [[Stephen F. Wheeler]] ('''1985'''). ''[https://www.researchgate.net/publication/34381496_A_performance_benchmark_of_the_alpha-beta_procedure_on_randomly_ordered_non-uniform_depth-first_game-trees_generated_by_a_chess_program 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, [https://en.wikipedia.org/wiki/Texas_A%26M_University%E2%80%93Commerce East Texas State University]
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[Steven Skiena]] ('''1990'''). ''Breadth-First and Depth-First Search.'' §3.2.5 in [http://www.amazon.com/exec/obidos/ASIN/0521806860/ref=nosim/weisstein-20 Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica]. Reading, MA: Addison-Wesley, pp. 95-97,
* [[Mathematician#WZhang|Weixiong Zhang]], [[Richard Korf]] ('''1993'''). ''[http://dl.acm.org/citation.cfm?id=1867385 Depth-first vs. best-first search: New results]''. [http://www.aaai.org/Conferences/AAAI/aaai93.php AAAI'93]
* [[Matthew L. Ginsberg]] ('''1993'''). ''[http://searchworks.stanford.edu/view/2746445 Essentials of artificial intelligence]''. [https://en.wikipedia.org/wiki/Morgan_Kaufmann_Publishers 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'''). ''[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-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>
=External Links=
* [https://en.wikipedia.org/wiki/Depth-first_search Depth-first search from Wikipedia]
* [https://en.wikipedia.org/wiki/Depth-limited_search Depth-limited search from Wikipedia]
* [https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search Iterative deepening depth-first search from Wikipedia]
* [http://mathworld.wolfram.com/Depth-FirstTraversal.html Depth-First Traversal] from [http://mathworld.wolfram.com/ Wolfram MathWorld]
* [http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/depth_first_search.html Boost Graph Library: Depth-First Search]
* [http://xlinux.nist.gov/dads/HTML/depthfirst.html depth-first search] from [http://xlinux.nist.gov/dads/ Dictionary of Algorithms and Data Structures] by [http://hissa.nist.gov/~black/ Paul E. Black], [https://en.wikipedia.org/wiki/National_Institute_of_Standards_and_Technology National Institute of Standards and Technology]
* [[Videos#FlatEarthSociety|Flat Earth Society]] & [https://en.wikipedia.org/wiki/Ernst_Reijseger Ernst Reijseger] - Down Deep, [https://en.wikipedia.org/wiki/Jazz_Middelheim Jazz Middelheim] 2012, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=NpQnmYP4aT8|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one Level]]'''
