What happens when W equals one?

The priority becomes the ordinary A* expression g + h.

Does W = 2 mean the route will cost twice the optimum?

No. Under the relevant assumptions, twice the optimum is an upper bound.

Is a larger weight always faster?

No. Expansion order changes, but runtime depends on the problem, heuristic, and implementation.

AI Glossary / Graphs and symbolic AI / Intermediate

Weighted A* search

Definition

Weighted A* search is a best-first search method that prioritizes a state using f(n) = g(n) + W*h(n), where g is the path cost already incurred, h estimates the remaining cost, and W is usually greater than one. It emphasizes the heuristic more strongly than ordinary A*, allowing a trade-off between finding a solution quickly and finding the cheapest solution.

What it means

The weight changes the search priority, not the actual cost of traversing an edge. A path found by weighted A* is still evaluated using the original problem costs.
Under appropriate conditions, weighted A* provides a bounded-suboptimal solution: its cost is at most W times the optimum. That is an upper bound, not a prediction that every answer will be exactly that much worse. The guarantee depends on the heuristic and the handling of repeated states. A number entered into a priority formula does not by itself establish the required conditions.

How it works

Maintain a frontier of discovered states and repeatedly select the state with the smallest weighted priority. Expand it, compute successor path costs, and update the frontier when better routes are found. Test for the goal when it is selected for processing, rather than stopping immediately when any goal is first generated.
For a concrete sufficient setting, consider a finite graph with nonnegative costs and a nonnegative, consistent heuristic that is zero at the goal. Standard weighted A* can retain its W bound without reopening closed states under this setting. More general admissible but inconsistent heuristics require care with reopening and the applicable guarantee. Larger weights do not guarantee faster execution on every problem.

Three practical examples

A game pathfinder can investigate whether accepting a bounded increase in route cost reduces search effort on representative maps.
A planning experiment can compare ordinary A* and weighted A* using the same action costs and heuristic.
A search tutorial can show how changing W alters expansion order while leaving the underlying graph unchanged.

Think of it this way

Think of choosing which promising route to investigate next while giving extra emphasis to estimated distance remaining. This may focus the investigation, but it can overlook a cheaper alternative temporarily. The analogy is limited because the formal quality bound requires mathematical properties of the heuristic and search procedure, not merely a confident travel estimate.

Worked example

Consider an original directed graph with four states S, A, B, and goal G. The only edges are S to A with cost 1, A to G with cost 9, S to B with cost 4, and B to G with cost 8. The two complete routes cost 10 and 12, so the optimum is 10.
Use h(S) = 0, h(A) = 9, h(B) = 0, and h(G) = 0. These estimates do not overestimate remaining costs and are consistent on every edge. The estimate at B is deliberately uninformative, which is allowed.
With W = 2, expanding S places A on the frontier with priority 1 + 2*9 = 19 and B with priority 4 + 2*0 = 4. Expand B next, generating G with path cost and priority 12. G is then selected ahead of A, and the search returns S-B-G with cost 12.
The returned route is 20% more expensive than the optimum, while the stated worst-case bound allows cost up to 2*10 = 20. Actual performance can be much better than the bound.
With W = 1, B is still selected first, but A has priority 10 and is selected before the tentative goal of cost 12. Expanding A improves the goal's path cost to 10, so ordinary A* returns the cheaper route. Excluding the goal selection itself, the weighted run expands S and B; the ordinary run expands S, B, and A. This tiny trace illustrates a trade-off, not a general runtime benchmark.

Illustrative case study

Fictional case: a puzzle-platform team wants responsive route suggestions. It compares W = 1, 1.2, and 2 on a fixed set of maps, recording solution costs, expansion counts, and elapsed time.
Before describing a quality guarantee, it checks the heuristic and duplicate-state policy. It also examines difficult cases where extra heuristic emphasis does not help. The team chooses a setting from measured trade-offs rather than assuming the largest weight is best. No particular speed improvement is claimed for this fictional evaluation.

Common misconceptions and mistakes

Do not confuse weighted A* with simply running A* on a graph whose edges have weights. Ordinary A* already supports path costs. Here, the special weight multiplies the heuristic.
Do not report W as a guaranteed speedup. Do not assume an arbitrary learned estimate is admissible or consistent. Do not assume the first generated goal meets the same guarantee as a goal selected by the specified search rule. Finally, a bound on the modeled path cost does not validate whether that cost captures the real application's priorities.

Business use

The method is relevant when search effort matters and some extra solution cost is acceptable. It makes the quality budget explicit.
Define the business meaning of path cost before selecting a weight. Measure time and memory alongside solution quality, and preserve the assumptions behind any bound. If the heuristic is empirical and lacks the required properties, label the evaluation as empirical rather than claiming a mathematical guarantee. For changing environments, also check whether the graph and costs used during search still describe the situation when the plan is executed.

Check your understanding

Why does the W = 2 run return cost 12 before investigating A?

Answer: The goal's priority is 12, while A's weighted priority is 19, so the goal is selected first.

Related terms

Heuristic
Consistency
Bounded suboptimal search
Frontier
A* search
Admissibility
Node reopening
Path cost

Learn next

Repeat the worked example with W = 1.2. A's priority becomes 11.8, which is below the tentative goal's 12. Follow the remaining steps to confirm that the returned route costs 10, despite using a weight greater than one.

Sources

Primary sources: AIMA original weighted-search context: https://raw.githubusercontent.com/aimacode/aima-glossary/master/sentences.txt ; Chen and Sturtevant, Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search: https://www.ijcai.org/proceedings/2019/0170.pdf . The four-state trace is original.

Previous: Weight tying Next: Weighted Alternating Least Squares