Course contentsShow
← Computer Science
Lesson 2760 of 2,87261. AI and Search AlgorithmsFree lesson

Weighted A* and Speed-Accuracy Tradeoffs

Understand how weighting heuristics trades optimality for faster solutions in practice.

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.*