Greedy Best – First Search tries to expand the node, i.e. closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function:

F(n) = h(n).

Let us see how this works for route. Finding problems, in Romania using the straight line distance heuristic, which we will call $h_{SLD}$ If the goal is Bucharest, we will need to know the straight – line distances to Bucharest, which are shown in figure (1).

Figure (1) Values of $h_{SLD}$ – straight – line distance to Bucharest.

Notice that the values of $h_{SLD}$ cannot be computed from the problem description itself. Moreover, it takes a certain amount of experience to know that $h_{SLD}$ is correlated with actual road distances and is therefore, a useful heuristic.

Figure (2) stages in a Greedy Best – First Search, for Bucharest using the straight line distance heuristic $h_{SLD}$. Nodes are labeled with their h – values.

Figure (2) shows the progress of Greedy Best – First Search using $h_{SLD}$ to find a path from Arad to Bucharest. The first node to be expanded from Arad will be Sibiu, because it is closer to Bucharest than either zerind or Timisoara. The next node to be expanded will be fagaras, because it is closest. Fagaras in turn generates Bucharest, which is the goal. For this particular problem, greedy best first search using $h_{SLD}$ finds a solution without ever expanding a node that is not on the solution path, hence its search cost is minimal. It is not optimal, however : the path via sibiu and fagaras to Bucharest is 32 kilometers longer than the path through Rimnicu vilcea and Pitesti. This shows why the algorithm is called “greedy” at each step it tries to get as close to the goal as it can.

Greedy Best – First Search resembles depth – First Search in the way it prefers to follow a single path all the way to the goal, but will backup when it hits a dead end. It suffers from the same defects as Depth – First Search. It is not optimal and it is incomplete. (because it can start down an infinite path and never return to try other possibilities.) The worst case time and space complexity is $O(b^m)$, where m is the maximum depth of the search space. With a good heuristic function, however, the complexity can be reduced substantially. The amount of the reduction depends on the particular problem and on the quality of the heuristic.