Course contentsShow
← Computer Science
Lesson 1010 of 2,87223. Shortest Path AlgorithmsFree lesson

Weighted A* and Suboptimality

Learn weighted A* using f(n) = g(n) + ε*h(n) to trade optimality for speed with bounded suboptimality.

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.