Weighted A* and Suboptimality
What You'll Learn
You'll learn how to deliberately trade optimality for faster pathfinding by adjusting A*'s heuristic weight.
The Core Idea
Standard A* uses the evaluation function f(n) = g(n) + h(n), where g(n) is the actual cost from start to node n, and h(n) is the heuristic estimate to the goal. Weighted A* modifies this to:
f(n) = g(n) + ε*h(n)
where ε (epsilon) is a weight factor greater than 1 (typically 1.5 to 3.0).
By inflating the heuristic with ε > 1, you make A* more "greedy"—it trusts the heuristic more and rushes toward the goal faster, exploring fewer nodes. The tradeoff? The solution may no longer be optimal.
Bounded Suboptimality
The beautiful part: the suboptimality is bounded. If you use ε = 2.0, the path you find is guaranteed to cost at most 2× the optimal path cost. This gives you a precise tradeoff knob:
ε = 1.0: Standard A*, optimal but potentially slowε = 2.0: Up to 2× longer path, but much faster searchε = 5.0: Up to 5× longer path, very fast search
When to Use It
When you need a "good enough" solution quickly—like real-time game AI where a character must move now, or robotics where computation time is limited. The guarantee means you never get catastrophically bad paths.
Key Takeaway: Weighted A* uses f(n) = g(n) + ε*h(n) with ε > 1 to find solutions faster at the cost of bounded suboptimality, trading optimality for speed with precise guarantees.