Weighted A* Search (WA*)

The Simplest Explanation

A* is optimal but slow. What if you're willing to accept a solution that's a little bit worse than optimal, as long as you get it much faster?

WA* says: inflate the heuristic by a weight $w > 1$. This makes the algorithm greedier — it rushes toward the goal more aggressively, exploring fewer nodes. The tradeoff: the solution may not be optimal, but its cost is bounded by $w \times \text{optimal cost}$.

$f(n) = g(n) + w \cdot h(n), \quad w \geq 1$

• $w = 1$: standard A* (optimal, slow)
• $w > 1$: WA* (faster, suboptimal but bounded)
• $w = \infty$: Greedy Best-First Search (fastest, no guarantee)

Why WA* Works (Intuition)

Think of $w$ as a dial that controls how much you trust the heuristic vs. the actual cost:

• Low $w$ (close to 1): you trust $g(n)$ more, explore carefully, find near-optimal solutions
• High $w$: you trust $h(n)$ more, rush toward the goal, find solutions fast but they may be costly
• The error bound grows linearly with $w$, so you always know the worst case

The Algorithm

WA* is identical to A* except for the evaluation function:

1. Put the start node in the open list with $g = 0$, $f = 0 + w \cdot h(\text{start})$
2. While the open list is not empty:
   • Pick the node with the lowest $f(n) = g(n) + w \cdot h(n)$ from the open list
   • If it's the goal → done!
   • Move it to the closed list
   • For each neighbor:
     • Calculate $g(\text{neighbor}) = g(\text{current}) + \text{edge cost}$
     • Calculate $f(\text{neighbor}) = g(\text{neighbor}) + w \cdot h(\text{neighbor})$
     • Standard open/closed list checks (same as A*)
3. If open list is empty → no path exists

Bounded Suboptimality

The key theorem for WA*:

$\text{If } h \text{ is admissible, then WA* with weight } w \text{ finds a path with cost} \leq w \times C^*$

where $C^*$ is the optimal (cheapest possible) path cost.

Why the Bound Holds (Sketch)

With $w > 1$, WA* may expand nodes in a different order than A*. But it will never expand a node with $f(n) > w \cdot C^*$ before finding a solution, because the goal node has $f = g(\text{goal}) + 0 = g(\text{goal})$, and the first goal found satisfies $g(\text{goal}) \leq w \cdot C^*$.

The Weight-Error Tradeoff

Properties Summary

Anytime A*

A powerful pattern: run WA* with decreasing weights.

1. Start with $w = 5$ → get a quick but rough solution (cost ≤ 5 × C*)
2. Lower to $w = 2$ → get a better solution (cost ≤ 2 × C*)
3. Lower to $w = 1$ → get the optimal solution (cost = C*)

Each iteration reuses the search from the previous one. You can stop at any time and still have a valid solution with a known error bound. This is called Anytime A* — it gives you the best solution found so far, with improving quality over time.

Worked Example: WA* with w=2

Here's the same 8-node graph. Start at S, goal is G. We use weight $w = 2$.

Compare WA* (w=2) with A* (w=1) — notice how WA* rushes toward B because its low h=2 gets inflated to 4:

WA* vs A* on This Graph

WA* found a solution 25% worse than optimal, but expanded 25% fewer nodes. In larger graphs, the node savings are far more dramatic.

Exam Practice: WA* vs A* Comparison

This question tests whether you can trace WA* and identify when it finds a different (suboptimal) path compared to A*. The graph is designed so that WA* with w=2 takes a completely different route.

Given: Find the shortest path from P to Z using WA* with w=2. Heuristic values:

Key Observation

A* (w=1) would expand P → R → S → U → Z (cost 6). WA* (w=2) expands P → Q → T → Z (cost 8). The entire path is different because the inflated heuristic makes Q (h=5, inflated to 10) look better than R (h=6, inflated to 12), even though R is on the optimal path.

Error bound verification: 8 ≤ 2 × 6 = 12 ✓