Best-first search operates by utilising an assessment algorithm to select the most promising adjacent location and explore it.

A "best-first search" utilises a heuristic to assess how close the end of a path is to a solution (or objective) and extends paths that are closest first. 

A priority queue is commonly used to identify the best candidate for extension. Moreover, the A* and B* search algorithms are examples of best-first search algorithms. In combinatorial search, best-first methods are frequently employed for pathfinding. However, neither A* nor B* are greedy best-first searches since they include the distance from the start and anticipated distances to the objective.

Greedy Search

The greedy best-first search algorithm always chooses the path that appears best at the time. 

  • It is a hybrid of depth-first and breadth-first search methods. 
  • It employs the heuristic function as well as search. 
  • Best-first search allows us to benefit from both algorithms. 

We can select the most promising node at each phase using a best-first search.

The priority queue implements the greedy best first algorithm.

Step 1: Add the first node to the OPEN list.
Step 2: Stop and return failure if the OPEN list is empty.
Step 3: Remove the node n from the OPEN list with the lowest h(n) value and move it to the CLOSED list.
Step 4: Extend node n and construct the node n's descendants.
Step 5: Examine each successor of node n to see whether any of them is a goal node. If any successor node is a goal node, return success and end the search; otherwise, move to Step 6.
Step 6: For each successor node, the algorithm looks for the evaluation function f(n) and then determines if the node has been in the OPEN or CLOSED list. If the node is not on both lists, add it to the OPEN list.
Step 7: Go back to Step 2.

Using a greedy algorithm, enlarge the parent's first child. Once a successor has been generated:

  • Suppose the successor's heuristic is superior to its parent. If the parent is reinserted behind the successor, the loop restarts.
  • Otherwise, the successor is added to the queue (in a location determined by its heuristic value). The process will examine the parent's remaining successors (if any).

The pseudocode below shows a priority queue that orders nodes by heuristic distance from the destination. We can utilise this approach for undirected graphs because it keeps track of visited nodes. Moreover, it is modifiable 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 ← 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 

Want to publish your content?

Publish an article and share your insights to the world.

Get Published Icon
ALSO EXPLORE