Editing Best-first search (section)

==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