Greedy best-first drawbacks; A*

Importance of searching

Most problems (route finding, puzzles, planning, games) are represented as a state space where no direct formula gives the answer. Search systematically explores the possible action sequences to find a path from the initial state to the goal, and finds the best one when many exist.

Greedy best-first search

It expands the node that appears closest to the goal, using only the heuristic: f(n) = h(n).

Drawbacks

1. Not optimal: it ignores the cost already spent, g(n), so it may return a long path.
2. Not complete: it can follow a misleading heuristic into a loop or dead end (unless repeated states are checked).
3. Worst-case time and space O(b^m); it may expand many nodes if the heuristic is poor.
4. Being greedy at every step, it can be fooled by local minima in h.

A* search

A* uses f(n) = g(n) + h(n), where g(n) = cost from the start to n and h(n) = estimated cost from n to the goal. With an admissible heuristic (one that never overestimates), A* is complete and optimal. Because g(n) is included, a path that has become expensive is abandoned, while the heuristic still guides the search towards the goal.

Example

Edges: S-A = 2, S-B = 5, A-C = 9, C-G = 1, B-G = 4. Heuristic: h(S) = 6, h(A) = 1, h(B) = 3, h(C) = 1, h(G) = 0 (admissible).

        S
     2 / \ 5
      A   B
    9 |   | 4
      C   |
    1 |   |
      G---+

Greedy: from S, compare h(A) = 1 and h(B) = 3 and choose A; then C (h = 1); then G. Path S-A-C-G, cost 2 + 9 + 1 = 12.

A*:

A* returns S-B-G, cost 9, which is better than the greedy path (12). A* did not follow the attractive h(A) = 1, because it counted the high cost 9 of the edge A-C in g.