25,161
edits
Changes
no edit summary
'''Best-First Search''' is a [https://en.wikipedia.org/wiki/State_space_search state space search] to traverse [[Node|nodes]] of tree-like data structures (i. e. [[Search Tree|search trees]]) in [https://en.wikipedia.org/wiki/Breadth-first_search breadth-first] manner. It is usually implemented with a [[Priority Queue|priority queue]] instead of the [[Queue|FIFO]] of breadth-first <ref>[http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/breadth_first_search.html Boost Graph Library: Breadth-First Search]</ref> , to expand the most promising node of one level first. Best-first turns a uninformed breadth-first into an informed search. Since all nodes of one level must be saved until their child nodes at the next level have been generated, the space complexity and memory requirement is proportional to the number of nodes at the deepest level.
Best-first algorithms like [https://en.wikipedia.org/wiki/A*_search_algorithm A*] are used for path finding in [https://en.wikipedia.org/wiki/Combinatorial_search combinatorial search] and [https://en.wikipedia.org/wiki/Puzzle puzzles]. [[Iterative Deepening|Iterative deepening]] is a technique to turn [[Depth-First|depth-first searches]] into best-first with the advantage space grows [https://en.wikipedia.org/wiki/Linear_growth linear] rather than [https://en.wikipedia.org/wiki/Exponential_growth exponential] with increasing [[Depth|search depth]]<ref>[[Richard Korf#JudeaPearl|Richard Korf Video]] at [[Judea Pearl#Symposium|Judea Pearl Symposium]], 2010</ref>, as applied for instance in [https://en.wikipedia.org/wiki/IDA* IDA*].
=Two-Player=
