Greedy Best-First Search (Russell Norvig)

Definition

*Greedy best-first search is a form of best-first search that expands first the node with the lowest h(n) value - the node that appears to be closest to the goal - on the grounds that this is likely to lead to a solution quickly. So the evaluation function is f(n) = h(n). (p. 103)

Worked example

Take for example a route-finding algorithm where we store the ‘crow flies’ distance between each city and our destination. We could use that distance as the value of h(n) and the greedy best-first search will expand whichever node has the lowest value in the table.

Note that the values of h(n) cannot be computed from the problem description itelf (the Actions and Result functions), and that it takes a certain world knowledge to know that the crow flies distance is correlated with actual road distances and so is a useful heuristic.

Properties

The algorithm is ‘greedy’ because it will try on each iteration to get as close to the goal as possible, but the resulting solution may not be optimal.

It is complete in finite state spaces, but not infinite ones. The worst case time and space complexity is \(O(|V|)\), however with a good heuristic function that can be reduced substantially reaching \(O(bm)\) on certain problems.