Weighted A* and Speed-Accuracy Tradeoffs
You'll learn: How multiplying the heuristic by a weight factor lets you find solutions faster at the cost of guaranteed optimality.
The Core Idea
Standard A* guarantees optimal solutions when using an admissible heuristic, but sometimes explores many nodes. Weighted A* modifies the evaluation function to be more aggressive:
f(n) = g(n) + w × h(n)
where w > 1 is the weight parameter.
By inflating the heuristic, you make A* "trust" its estimate more and expand fewer nodes—it rushes toward the goal more greedily. The larger the weight w, the more the search behaves like Greedy Best-First Search (which you learned earlier). When w = 1, you get standard A*.
The Tradeoff
Speed: Weighted A* typically expands dramatically fewer nodes, finding solutions much faster.
Accuracy: The solution is no longer guaranteed optimal. With weight w, the solution cost is bounded: it won't exceed w times the optimal cost. So w = 2 might give you a path that's up to twice as expensive as optimal, but finds it in a fraction of the time.
When to Use It
This tradeoff shines in real-time applications—robotics, video games, route planning—where a "good enough" solution now beats a perfect solution that arrives too late. You tune w based on your tolerance for suboptimality.
Think of it like choosing between GPS route options: the "fastest route" (higher w) might not be the absolute shortest distance, but gets you there quicker in practice.
Key Takeaway:
Weighted A sacrifices optimality guarantees for speed by inflating the heuristic, letting you tune the speed-accuracy tradeoff via the weight parameter.*