Editing Best-first search

{{Short description|Graph exploring search algorithm}}
'''Best-first search''' is a class of [[search algorithm]]s which explores a [[graph (data structure)|graph]] by expanding the most promising node chosen according to a specified rule.

[[Judea Pearl]] described best-first search as estimating the promise of node ''n'' by a "heuristic evaluation function <math>f(n)</math> which, in general, may depend on the description of ''n'', the description of the goal, the information gathered by the search up to that point, and most importantly, on any extra knowledge about the problem domain."<ref>[[Judea Pearl|Pearl, J.]] ''Heuristics: Intelligent Search Strategies for Computer Problem Solving''. Addison-Wesley, 1984. p. 48.</ref><ref name="RN03">
{{Cite book
| first1 = Stuart J. | last1 = Russell | author1-link = Stuart J. Russell
| first2 = Peter.    | last2 = Norvig  | author2-link = Peter Norvig
| title=[[Artificial Intelligence: A Modern Approach]]
| year = 2021
| edition = 4th 
| isbn = 9780134610993 
| lccn = 20190474
| publisher = Pearson | location = Hoboken
| pages = 73-74}}
</ref>

Some authors have used "best-first search" to refer specifically to a search with a [[Heuristic function|heuristic]] that attempts to predict how close the end of a path is to a solution (or, goal), so that paths which are judged to be closer to a solution (or, goal) are expanded first. This specific type of search is called ''[[Greedy algorithm|greedy]] best-first search''<ref name="RN03"/> or ''pure heuristic search''.<ref>{{cite encyclopedia |first=Richard E. |last=Korf|author-link=Richard E. Korf |year=1999 |title=Artificial intelligence search algorithms |encyclopedia=Handbook of Algorithms and Theory of Computation |editor-first=Mikhail J. |editor-last=Atallah |publisher=CRC Press |isbn=0849326494}}</ref>

Efficient selection of the current best candidate for extension is typically implemented using a [[priority queue]].

The [[A* search algorithm]] is an example of a best-first search algorithm, as is [[B*]]. Best-first algorithms are often used for path finding in [[combinatorial search]]. Neither A* nor B* is a greedy best-first search, as they incorporate the distance from the start in addition to estimated distances to the goal.

==Greedy BeFS==

Using a [[greedy algorithm]], expand the first successor of the parent. After a successor is generated:<ref>https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Greedy Best-First Search when EHC Fails, Carnegie Mellon</ref>

# If the successor's heuristic is better than its parent, the successor is set at the front of the queue (with the parent reinserted directly behind it), and the loop restarts.
# Else, the successor is inserted into the queue (in a location determined by its heuristic value). The procedure will evaluate the remaining successors (if any) of the parent.
Below is a [[pseudocode]] example of this algorithm, where '''queue''' represents a priority queue which orders nodes based on their heuristic distances from the goal. This implementation keeps track of visited nodes, and can therefore be used for [[Graph (discrete mathematics)#Undirected graph|undirected graphs]]. It can be modified to retrieve the path.
 '''procedure''' GBS(start, target) '''is''':
   mark start as visited
   add start to queue
   '''while''' queue '''is''' '''not''' empty '''do''':
     current_node &larr; vertex of queue with min distance to target
     remove current_node from queue
     '''foreach''' neighbor n of current_node '''do''':
       '''if''' n '''not''' '''in''' visited '''then''':
         '''if''' n '''is''' target:
           '''return''' n
         '''else''':
           mark n as visited
           add n to queue
   '''return''' failure

==See also==
*[[Beam search]]
*[[A* search algorithm]]
*[[Dijkstra's algorithm]]

==References==
<references />

==External links==
* [[wikibooks:Artificial Intelligence/Search/Heuristic search/Best-first search|Wikibooks: Artificial Intelligence: Best-First Search]]

{{Graph traversal algorithms}}

[[Category:Search algorithms]]
[[Category:Greedy algorithms]]