That cost is an admissible heuristic for the original.
An easier problem gives a lower bound — safe to use as an estimate.
Quick check: heuristic from relaxation
Q. Drop the "B is empty" constraint: a tile can move from A to B if A and B are adjacent. Which heuristic does this give?
Manhattan distance
Misplaced tile count
Another heuristic not listed
A — Manhattan distance. Without the "B must be empty" constraint, each tile slides freely along the grid to its goal — cost = number of grid steps = Manhattan distance.
Dominating heuristics
Definition. \(h_2\) dominates \(h_1\) if \(h_2(n) \ge h_1(n)\) for all \(n\), and \(h_2(n) > h_1(n)\) for some \(n\).
Theorem. If \(h_2\) dominates \(h_1\), A* with \(h_2\) expands no more nodes than A* with \(h_1\). Higher = better — as long as still admissible.
Manhattan vs Misplaced
Q. On our example state, Manhattan = 16 and Misplaced = 7. Which heuristic dominates the other in general?
Manhattan dominates Misplaced
Misplaced dominates Manhattan
Neither dominates the other
A — Manhattan dominates. Each misplaced tile contributes at least 1 to both heuristics; Manhattan adds the actual grid distance, so Manhattan \(\ge\) Misplaced, and strictly \(>\) whenever any tile is more than one step from its goal.
Cycle pruning
Don't follow a path that revisits a node already on the current path.
When expanding path \(\langle n_0, \ldots, n_k \rangle\):
For each neighbour n of nk:
If n already appears in <n0, …, nk> → skip.
Else add <n0, …, nk, n> to the frontier.
Check is linear in path length. Saves DFS from infinite loops.
Multi-path pruning
Don't expand a node we've already expanded (across different paths). Cycle pruning is a special case.
Maintain an explored set, initialized to { }.
Pop path \(\langle n_0, \ldots, n_k \rangle\). Then:
If nk ∈ explored → skip.
Add nk to explored.
If nk is the goal → return the path.
Else push each neighbour-extension to the frontier.
Caveats of multi-path pruning
Repeats still pushed — skipped on pop
Trades memory (explored set) for time
May sacrifice optimality (see next slides)
LCFS + multi-path pruning
Q. LCFS with multi-path pruning — can it discard the optimal solution?
Yes, it can
No, never
B — No. First pop of any node already has the smallest \(g\); later paths to it can only be costlier. Safe to prune.
A* + multi-path pruning
Q. A* with admissible \(h\) + multi-path pruning — can it discard the optimal?
Yes, it can
No, never
A — Yes, it can. A* orders by \(f = g + h\), so the first pop of \(n\) need not have the smallest \(g\). A cheaper \(g(n)\) found later is then discarded. Counterexample next.
A* + multi-path: counterexample
Optimal path is S→C→E→G (cost 23). With multi-path pruning, A* returns S→B→E→G (cost 25) instead.
Frontier & Explored:Frontier: (S) Explored: { }pop S → Frontier: (SB:4, SC:21, SD:22) Explored: {S}pop SB → Frontier: (SBE:9, SC:21, SD:22) Explored: {S, B}pop SBE → Frontier: (SC:21, SD:22, SBEG:25) Explored: {S, B, E}pop SC → Frontier: (SCE:7, SD:22, SBEG:25) Explored: {S, B, E, C}pop SCE → E already explored → SKIP (the optimal path is lost here!)
Consistent (monotone) heuristic
Definition. \(h\) is consistent if for every edge \(m \to n\):
\(h(m) \le \text{cost}(m, n) + h(n)\)
i.e., the heuristic decreases by no more than the edge cost as we move toward the goal.
Theorem. If \(h\) is consistent, A* with multi-path pruning is optimal.
Most natural heuristics (Manhattan, straight-line distance, …) are consistent.
Where A* can mis-prune
Why does LCFS need no extra condition, but A* does?
LCFS — sorts by \(g(n)\):
first pop of \(n\) already has the smallest \(g(n)\) — safe.
A* — sorts by \(f = g + h\):
\(h(n)\) cancels at \(n\), but differs across prefixes \(p, p'\);
a big \(h\)-gap can pop the larger-\(g\) path first → \(n\) committed to a worse prefix.