Home / Curated / Algorithms / Weighted A-star search

Weighted A-star search

Algorithms AIMech:WeightedAStar DRAFT

Aliases: Weighted A*, WA*

A heuristic best-first search algorithm that orders open nodes by g+w h using a fixed finite weight w greater than one, where g is path cost so far and h estimates remaining cost.

Identity Notes & Concept Scope The record concerns fixed-weight Weighted A-star, not a depth-dependent weight schedule, an anytime schedule of repeated searches, or weighted IDA-star. Pohl’s original expression (1−omega)g+omega h uses a different parameterization; for omega less than one, dividing by the positive factor (1−omega) gives w=omega/(1−omega), so w>1 corresponds to omega>1/2. This algebraic equivalence concerns priority ordering, not duplicate-policy equivalence. No normalized identity match was found across the 442 AIO and 124 prior native records; ignored-inclusive text hits in the main checkout were prior discovery leads, source citations and search-order contrasts, plus incidental dependency substrings, not existing concept records.

Claims & Grounded Evidence

3 Claims

Mechanism #search-procedure

Maintain a best-first frontier ranked by the cost already incurred plus a fixed amplified heuristic estimate, g+w h. The weight changes the tradeoff in node ordering while graph duplicate handling, tie-breaking and stopping rules must still be specified.

supports Source: When Does Weighted A* Fail? · Locator: Introduction, PDF p. 1: f-prime(n)=g(n)+w h(n), w in (1,infinity)

Scope #original-scope

The original paper combines cost-to-date and heuristic terms with complementary weights. Its basic graph model counts edges; it separately describes HPA+ updates that revise an open node or reopen an expanded node after a better route. These distinctions prevent treating every weighted priority implementation as the same graph algorithm.

supports Source: Heuristic Search Viewed as Path Finding in a Graph · Locator: Heuristic Path Algorithm, printed p. 196 / PDF p. 4; HPA+ update, printed p. 199 / PDF p. 7; Final Observations, printed p. 202 / PDF p. 10

Limitation #duplicate-bound-caveat

The comparison paper distinguishes the advertised weighted-search quality bound from its own duplicate-discarding experimental implementation, noting that ignoring duplicate improvements can relax the bound.

supports Source: A Comparison of Greedy Search Algorithms · Locator: Weighted A-star and Ignoring Duplicates, PDF p. 2

⚠️ Curated Limitations & Negative Results

Increasing the weight does not guarantee faster search or fewer expansions. The cited study’s empirical conditions are not asserted as necessary-and-sufficient conditions on all search spaces.
A w-suboptimality guarantee requires an admissible heuristic and appropriate graph-search and termination conditions. It must not be inferred from the priority formula alone or an implementation that indiscriminately drops improved duplicates.
The weight is finite and fixed in this record; w=1 gives the A-star priority, while a heuristic-only priority is curated separately.

Artificial Intelligence Ontology (AIO) Grounding

Explicit AIO Snapshot Assessment: No Match

Rationale: No suitable AIO counterpart for this graph/state-space search procedure was identified in the inspected snapshot. Using graphs, evaluation functions or a search subroutine in an AI system does not equate the algorithm with a learned model, a learning task or a mathematical function.

Search Scope: All 442 pinned AIO labels and scoped synonyms and 124 preceding native identities were compared. Both updated checkouts were searched including hidden and ignored files. Exact CLASS nodes and edges for GraphLanguageModel, ReasoningLLM, NeuroSymbolicLLM, MachineLearningTask, MathematicalFunction and ReinforcementLearning were inspected, alongside semantic search for search, planning, heuristic, path, traversal, symbolic, reasoning and graph terminology.

Examined AIO Candidate	Rejection Reason
`AIO:GraphLanguageModel`	A language model operating on structured graph representations is not a graph traversal or shortest-path algorithm.
`AIO:ReasoningLLM`	Language-task deductive inference does not denote general state-space search.
`AIO:NeuroSymbolicLLM`	A language-model architecture combining neural and symbolic components is not the search procedure itself.
`AIO:MachineLearningTask`	Building methods that learn from data is not the identity of an algorithm traversing a specified graph.
`AIO:MathematicalFunction`	The search procedure is distinct from the mathematical functions it may evaluate.
`AIO:ReinforcementLearning`	A learning task balancing exploration and exploitation is distinct from deterministic graph/state-space traversal.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`method-source`	When Does Weighted A* Fail? Christopher Wilt, Wheeler Ruml	primary paper full_text	ID: doi:10.1609/socs.v3i1.18250 sha256:f1cd583c7e8f…
`original-weighted-search`	Heuristic Search Viewed as Path Finding in a Graph Ira Pohl	primary paper full_text	ID: doi:10.1016/0004-3702(70)90007-X sha256:ac04fba0ca8b…
`comparison-paper`	A Comparison of Greedy Search Algorithms Christopher Wilt, Jordan Thayer, Wheeler Ruml	primary paper full_text	ID: doi:10.1609/socs.v1i1.18182 sha256:cfc3cf8f422b…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-11T05:44:44Z

Updated: 2026-10-11T05:44:44Z

Source File: data/curated/WeightedAStar.yaml