Greedy Search

Greedy Search
In greedy search, the idea is to expand the node with the smallest estimated cost to reach the goal.
We use a heuristic function
f(n) = h(n)
h(n) estimates the distance remaining to a goal.
Greedy algorithms often perform very well. They tend to find good solutions quickly, although not always optimal ones.

The resulting algorithm is not optimal. The algorithm is also incomplete, and it may fail to find a solution even if one exists. This can be seen by running greedy search on the following example. A good heuristic for the route-finding problem would be straight-line distance to the goal.
Figure 2 is an example of a route finding problem. S is the starting state, G is the goal state.

 

 

Let us run the greedy search algorithm for the graph given in Figure 2. The straight line distance heuristic estimates for the nodes are shown in Figure 3.