Informed Search - Greedy Best-First and A*

Informed (heuristic) search uses extra knowledge about the problem: a heuristic function h(n) that estimates the cost of the cheapest path from node n to a goal. A good heuristic lets the search head straight for the goal instead of exploring blindly.

For route finding, the straight-line distance to the destination is a natural heuristic. For the 8-puzzle, the number of misplaced tiles is one.

Greedy best-first search

Greedy best-first search expands the node with the smallest h(n): the node that looks closest to the goal, ignoring how much it cost to get there.

• It is often fast, but not optimal: it may follow a path that looks good early and turns out expensive.
• It is not complete in tree search (it can loop); graph search makes it complete in finite spaces.
• Worst-case time and space O(b^m), though a good heuristic cuts this dramatically.

A* search

A* expands the node with the smallest

f(n) = g(n) + h(n)

where g(n) is the cost of the path found so far from the start to n, and h(n) estimates the remaining cost. So f(n) estimates the cost of the cheapest solution through n. A* combines the cost-awareness of uniform-cost search (h = 0 gives UCS) with the goal-direction of greedy search.

Admissible and consistent heuristics

• h is admissible if it never overestimates: h(n) ≤ h*(n) for every n, where h*(n) is the true cheapest cost from n to a goal. Also h(goal) = 0.
• h is consistent (monotone) if for every edge n → n′ with cost c(n, n′): h(n) ≤ c(n, n′) + h(n′). This is a triangle inequality.

Every consistent heuristic is admissible. The converse is not always true, but most natural admissible heuristics are also consistent.

Optimality of A*:

• With an admissible heuristic, A* tree search is optimal.
• With a consistent heuristic, A* graph search is optimal, and f(n) never decreases along a path, so the first time A* expands a node it has found the cheapest path to it.
• A* is optimally efficient: no other optimal algorithm using the same heuristic is guaranteed to expand fewer nodes.

With an inadmissible heuristic that overestimates, A* can return a suboptimal path.

Worked example

The graph from the previous lesson, with heuristic values written next to each node:

Every h(n) ≤ h*(n), so h is admissible. The program also checks every edge for consistency.

import heapq

graph = {"S": {"A": 1, "B": 4}, "A": {"B": 2, "C": 5, "D": 12}, "B": {"C": 2},
         "C": {"D": 1, "G": 4}, "D": {"G": 2}, "G": {}}
h = {"S": 7, "A": 6, "B": 4, "C": 2, "D": 1, "G": 0}

consistent = all(h[n] <= c + h[m] for n in graph for m, c in graph[n].items())
print("consistent:", consistent)

def search(start, goal, priority):
    frontier, explored, order = [(priority(0, start), start, 0, [start])], set(), []
    while frontier:
        f, node, g, path = heapq.heappop(frontier)
        if node in explored:
            continue
        explored.add(node)
        order.append(f"{node}(f={f})")
        if node == goal:
            return order, path, g
        for nxt, c in graph[node].items():
            if nxt not in explored:
                heapq.heappush(frontier, (priority(g + c, nxt), nxt, g + c, path + [nxt]))

for name, pr in [("Greedy", lambda g, n: h[n]), ("A*", lambda g, n: g + h[n]), ("UCS", lambda g, n: g)]:
    order, path, g = search("S", "G", pr)
    print(f"{name:6}: expanded {' '.join(order)}")
    print(f"        path {'-'.join(path)}, cost {g}, {len(order)} expansions")

consistent: True
Greedy: expanded S(f=7) B(f=4) C(f=2) G(f=0)
        path S-B-C-G, cost 10, 4 expansions
A*    : expanded S(f=7) A(f=7) B(f=7) C(f=7) D(f=7) G(f=8)
        path S-A-B-C-D-G, cost 8, 6 expansions
UCS   : expanded S(f=0) A(f=1) B(f=3) C(f=5) D(f=6) G(f=8)
        path S-A-B-C-D-G, cost 8, 6 expansions

Greedy search rushes along the nodes with small h (S, B, C, G) and returns S-B-C-G, which costs 10. A* finds the optimal path of cost 8. Notice that every node A* expands before the goal has f = 7: h is so close to the true cost that f stays nearly constant along the optimal path. On this tiny graph UCS happens to expand the same six nodes; on large graphs, where UCS spreads out in every direction, a good heuristic saves A* an enormous number of expansions.

Comparing heuristics: dominance

If h₁ and h₂ are both admissible and h₂(n) ≥ h₁(n) for every n, then h₂ dominates h₁. A* with h₂ never expands more nodes than with h₁: a larger admissible heuristic is a better-informed one. The ideal is h = h*, with which A* expands only nodes on an optimal path; h = 0 gives no information (UCS).

If h₁ and h₂ are both admissible, max(h₁, h₂) is admissible too and dominates both.

Designing heuristics: relaxed problems

An admissible heuristic is often the exact cost of a relaxed problem, a version of the problem with some constraints removed. Removing constraints can only make solutions cheaper, so the relaxed cost never overestimates.

For the 8-puzzle (slide tiles into the blank to reach the goal arrangement):

• h₁ = number of misplaced tiles: exact if a tile could jump to any square in one move.
• h₂ = sum of Manhattan distances of each tile from its goal square: exact if a tile could slide into any adjacent square, even an occupied one.

Both are admissible, and h₂ dominates h₁ (a misplaced tile is at least 1 square away). The blank is never counted.

start = [[7, 2, 4],
         [5, 0, 6],
         [8, 3, 1]]
goal = [[0, 1, 2],
        [3, 4, 5],
        [6, 7, 8]]
where = {goal[r][c]: (r, c) for r in range(3) for c in range(3)}
tiles = [(start[r][c], r, c) for r in range(3) for c in range(3) if start[r][c] != 0]
h1 = sum(1 for t, r, c in tiles if (r, c) != where[t])
h2 = sum(abs(r - where[t][0]) + abs(c - where[t][1]) for t, r, c in tiles)
print("misplaced tiles h1 =", h1)
print("Manhattan distance h2 =", h2)

misplaced tiles h1 = 8
Manhattan distance h2 = 18

Practice questions