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) |
||
| (6 intermediate revisions by the same user not shown) | |||
| Line 20: | Line 20: | ||
=Publications= | =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] | + | ==1970 ...== |
| + | * [[Toshihide Ibaraki]] ('''1978'''). ''[https://link.springer.com/article/10.1007/BF00991818 Depth-m search in branch-and-bound algorithms]''. [https://link.springer.com/journal/10766 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]] <ref>quoted by [[Hans Berliner]], [[Gordon Goetsch]] ('''1985'''). ''A Study of Search Methods : The Effect of Constraint Satisfaction and Adventurousness''. [https://www.ijcai.org/Proceedings/85-2/Papers/083.pdf pdf]</ref> <ref>Paper is mentioned by [[Richard Korf#JudeaPearl|Richard Korf]] at [[Judea Pearl#Symposium|Judea Pearl Symposium]], 2010</ref> | ||
| + | * [[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] | * [[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]] | * [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]] | ||
| + | ==1990 ...== | ||
* [[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, | * [[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]''. [ | + | * [[Nageshwara Rao Vempaty]], [[Vipin Kumar]], [[Richard Korf]] ('''1991'''). ''Depth-First vs Best-First Search''. [[Conferences#AAAI-91|AAAI-91]], [https://www.aaai.org/Papers/AAAI/1991/AAAI91-067.pdf pdf] |
| − | * [[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] | + | * [[Mathematician#WZhang|Weixiong Zhang]], [[Richard Korf]] ('''1993'''). ''[http://dl.acm.org/citation.cfm?id=1867385 Depth-first vs. best-first search: New results]''. [[Conferences#AAAI-93|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], 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]] ('''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'''). ''[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''. [ | + | ==2010 ...== |
| + | * [[Tomoyuki Kaneko]] ('''2010'''). ''Parallel Depth First Proof Number Search''. [[Conferences#AAAI-2010|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> | ||
| + | * [[Tom Everitt]], [[Marcus Hutter]] ('''2015'''). ''Analytical Results on the BFS vs. DFS Algorithm Selection Problem. Part I: Tree Search''. Australasian Conference on Artificial Intelligence, [https://pdfs.semanticscholar.org/1b4b/c878b2d068214e39b258ee250e5b8889e84c.pdf 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''. [[Conferences#IJCAI2017|IJCAI 2017]] | ||
=External Links= | =External Links= | ||
| Line 38: | Line 49: | ||
* [http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/depth_first_search.html Boost Graph Library: Depth-First Search] | * [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] | * [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] | ||
| − | * [[ | + | * [[:Category:Flat Earth Society|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}} | : {{#evu:https://www.youtube.com/watch?v=NpQnmYP4aT8|alignment=left|valignment=top}} | ||
| Line 45: | Line 56: | ||
'''[[Search|Up one Level]]''' | '''[[Search|Up one Level]]''' | ||
| + | [[Category:Flat Earth Society]] | ||
Latest revision as of 23:55, 9 March 2019
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.
Contents
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
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
