Informed Search: Greedy Best-First and A* with Admissible Heuristics

Blind search is honest but slow. A human planning a route from Dhaka to Chattogram does not consider roads heading towards Rajshahi, because they know roughly where Chattogram is. Today we give our search algorithms that kind of knowledge through a heuristic function, and we study the most celebrated algorithm in classical AI: A\*.

Heuristic functions#

A heuristic $h(n)$ estimates the cost of the cheapest path from node $n$ to a goal. For route finding, the straight-line distance is a natural choice. For the 8-puzzle, two classic heuristics are:

• $h_1$ = number of misplaced tiles;
• $h_2$ = sum of Manhattan distances of each tile from its goal position.

Greedy best-first search#

Greedy search expands the node with smallest $h(n)$ — whatever looks closest to the goal. It is often fast but neither optimal nor (in tree search) complete: it can be lured down a path that looks promising but is expensive or a dead end.

A* search#

A* combines the cost already paid with the estimated cost remaining:

where $g(n)$ is the path cost from the start to $n$. A* expands the node with the lowest $f$ — the estimated cost of the cheapest solution through $n$.

import heapq, itertools

def a_star(start, is_goal, neighbors, h):
    counter = itertools.count()          # tie-breaker so states need not be comparable
    frontier = [(h(start), next(counter), 0, start)]
    g_best = {start: 0}
    parent = {start: None}
    while frontier:
        f, _, g, s = heapq.heappop(frontier)
        if is_goal(s):
            path = []
            while s is not None:
                path.append(s); s = parent[s]
            return g, path[::-1]
        if g > g_best[s]:
            continue
        for t, cost in neighbors(s):
            g2 = g + cost
            if g2 < g_best.get(t, float("inf")):
                g_best[t] = g2
                parent[t] = s
                heapq.heappush(frontier, (g2 + h(t), next(counter), g2, t))
    return None

Admissibility and consistency#

Every consistent heuristic is admissible (with $h(\text{goal}) = 0$), but not vice versa.

Why A* is optimal#

Theorem. With an admissible heuristic, A* tree search returns an optimal solution.

Proof sketch. Suppose A* selects a suboptimal goal $G_2$ for expansion, with $g(G_2) > C^*$. Let $n$ be a node on an optimal path that is still on the frontier (one always exists). Then

so $n$ has a strictly smaller $f$ than $G_2$ and would have been expanded first — a contradiction. $\blacksquare$

With a consistent heuristic, $f$ values are non-decreasing along any path, which means that the first time A* expands a state it has found the optimal path to it — so graph search with a closed set remains optimal.

The quality of a heuristic#

If $h_2(n) \ge h_1(n)$ for all $n$ and both are admissible, we say $h_2$ dominates $h_1$, and A* with $h_2$ never expands more nodes. For the 8-puzzle, Manhattan distance dominates misplaced tiles. Typical results at solution depth 20:

Inventing heuristics by relaxation#

Where do good heuristics come from? The most powerful technique is problem relaxation: remove constraints from the problem, then solve the easier problem exactly. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original.

For the 8-puzzle, the rule is "a tile can move from A to B if A is adjacent to B and B is blank."

• Drop both conditions → a tile can jump anywhere → $h_1$.
• Drop "B is blank" → tiles slide through each other → $h_2$.

Other techniques include pattern databases (store exact costs for sub-problems) and learned heuristics, where a neural network predicts cost-to-go — the idea behind modern systems that combine search with learning.

Variants you should know#

• Weighted A\*: $f = g + w\,h$ with $w > 1$ trades optimality (bounded by factor $w$) for speed.
• IDA\*: iterative deepening on $f$-cost, using linear memory.
• SMA\*: uses all available memory and drops the worst nodes when full.