Greedy Best-First Search

Greedy best-first search is an informed search algorithm where the evaluation function is strictly equal to the heuristic function, disregarding the edge weights in a weighted graph. To get from a start node to a target node, the lowest value resulting from some heuristic function, h(x), is considered as the successive node to traverse to. The goal is to choose the quickest and shortest path to the target node.

Evaluation Function

The evaluation function, f(x), for the greedy best-first search algorithm is the following:

f(x) = h(x)

Here, the evaluation function is equal to the heuristic function. Since this search disregards edge weights, finding the lowest-cost path is not guaranteed.

Heuristic Function

A heuristic function, h(x), evaluates the successive node based on how close it is to the target node. In other words, it chooses the immediate low-cost option. As this is the case, however, it does not necessarily find the shortest path to the goal.

Suppose a bot is trying to move from point A to point B. In greedy best-first search, the bot will choose to move to the position that brings it closest to the goal, disregarding if another position ultimately yields a shorter distance. In the case that there is an obstruction, it will evaluate the previous nodes with the shortest distance to the goal, and continuously choose the node that is closest to the goal.

The Algorithm

1. Initialize a tree with the root node being the start node in the open list.
2. If the open list is empty, return a failure, otherwise, add the current node to the closed list.
3. Remove the node with the lowest h(x) value from the open list for exploration.
4. If a child node is the target, return a success. Otherwise, if the node has not been in either the open or closed list, add it to the open list for exploration.

Example

Consider finding the path from P to S in the following graph:

In this example, the cost is measured strictly using the heuristic value. In other words, how close it is to the target.

C has the lowest cost of 6. Therefore, the search will continue like so:

U has the lowest cost compared to M and R, so the search will continue by exploring U. Finally, S has a heuristic value of 0 since that is the target node:

The total cost for the path (P -> C -> U -> S) evaluates to 11. The potential problem with a greedy best-first search is revealed by the path (P -> R -> E -> S) having a cost of 10, which is lower than (P -> C -> U -> S). Greedy best-first search ignored this path because it does not consider the edge weights.