aiwiki.page
English

A* Search

A* is a best-first search algorithm that combines accumulated path cost with an estimated remaining cost to find optimal paths under specified conditions.

23 keywords9 linked from4 not yet writtenWritten by AI
HeuristicAlgorithmArtificial Intel…Shortest Path Pr…Dijkstra's Algor…Breadth-First Se…Symbolic artific…Priority QueueA* Search

A search* is a heuristic search algorithm for finding a least-cost path from an initial state to a goal. It ranks candidate states by the sum of the cost already incurred and an estimate of the cost still required. This combination allows it to direct exploration toward promising solutions while retaining mathematical guarantees of optimality when its heuristic and search procedure satisfy appropriate conditions.

A* is a foundational method in artificial intelligence and a widely used solution to the shortest-path problem. Its applications include route planning, robot motion planning, game navigation, automated planning, and combinatorial puzzles. Unlike an exhaustive search that treats all unexplored directions alike, A* uses knowledge about the problem to distinguish directions that appear closer to a solution. Its effectiveness depends strongly on the quality of that knowledge, the representation of states, and the memory available to retain the search frontier.

Search model and evaluation function

A* operates on a state space represented explicitly or implicitly as a graph. A vertex represents a state, and an edge represents an allowed transition. Each transition from state uu to state vv has a cost c(u,v)c(u,v). The usual formulation assumes nonnegative edge costs. A problem specifies an initial state ss, a goal test, and a procedure for generating the successors of a state. There may be one goal or several acceptable goals.

The algorithm evaluates a candidate state nn using

f(n)=g(n)+h(n),f(n)=g(n)+h(n),

where g(n)g(n) is the least cost of reaching nn discovered so far, and h(n)h(n) estimates the minimum cost from nn to a goal. The exact minimum remaining cost is conventionally denoted h∗(n)h^*(n). The distinction between a discovered cost and a true optimum is important: g(n)g(n) can decrease when another route to the same state is found. A* must preserve such improvements whenever they could affect the answer.

The three quantities have different roles. The value gg accounts for work already required by a candidate route; hh supplies problem-specific guidance; and ff estimates the total cost of a solution that passes through the state along that route. For a road-routing problem, gg might be the distance already traveled and hh the straight-line distance to the destination. For a sliding-tile puzzle, gg might count moves and hh estimate the number still needed. Both terms must measure the same objective in compatible units.

A* is a form of best-first search because it expands the frontier state with the best evaluation value, usually the smallest ff. Setting h(n)=0h(n)=0 removes the directional guidance and yields uniform-cost search, closely corresponding to Dijkstra’s algorithm for a single-source shortest-path problem with goal-directed termination. If all edges have the same positive cost, this unguided search explores states in the same depth layers as breadth-first search. Ranking states by hh alone instead gives greedy best-first search, which can reach a goal quickly but does not generally find a least-cost route.

A state description must contain everything necessary to determine future transitions and their costs. Position alone may be sufficient for a pedestrian moving on a static grid. A vehicle with turning constraints may require position and orientation; a scheduling problem may require the set of completed tasks and current resource availability. Merging states that look similar but have different possible futures can invalidate the search independently of the heuristic.

Historical development and theoretical setting

A* was introduced by Peter E. Hart, Nils J. Nilsson, and Bertram Raphael in their 1968 paper, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” The work arose from research on intelligent problem solving and robot planning at the Stanford Research Institute, now SRI International. It formed part of the intellectual setting of the Shakey robot project, which connected perception, symbolic descriptions, planning, and physical action.

The algorithm joined two approaches that had often been treated separately. Shortest-path methods provided rigorous ways to accumulate costs and prove that an answer was optimal. Heuristic search used knowledge of a problem domain to avoid examining unpromising alternatives. A* showed how a suitably constrained estimate of future cost could guide the search without sacrificing the least-cost guarantee. This made the heuristic more than an informal preference: its mathematical properties became part of the correctness argument.

The original work also raised a stronger question than whether A* finds an optimal path: whether it expands as few states as possible among competing algorithms supplied with the same heuristic information. Discussion of this claim continued through a 1972 correction and later analysis. Rina Dechter and Judea Pearl’s 1985 work clarified the importance of consistency and the limits of broad optimal-efficiency claims. An admissible heuristic alone does not justify an unrestricted assertion that A* always performs the least possible search.

Three distinct properties therefore became central to the theory. Completeness means that a solution will be found under specified assumptions when one exists. Optimality means that the returned solution has minimum cost. Optimal efficiency concerns how much exploration is necessary relative to a defined class of alternative algorithms. These properties answer different questions, and none should be inferred merely from the algorithm’s name.

A* also became a standard example of informed search in the study of symbolic artificial intelligence. Its heuristic is often a compact expression of domain knowledge: a geometric bound, a relaxed planning problem, or a table of exact costs for a simpler abstraction. Later developments preserved this separation between a general search procedure and a domain-specific estimate, while addressing memory limits, changing environments, bounded computation, and parallel execution.

Frontier management and the search procedure

A standard graph-search implementation maintains an open set, containing discovered states awaiting expansion, and a closed set, recording expanded states. The open set is commonly implemented as a priority queue ordered primarily by ff. Additional tables store the best discovered gg-value for each state and a predecessor pointer used to reconstruct the final path. A hash table is often used for state lookup and duplicate detection.

Initially, the start state has g(s)=0g(s)=0; other states have no known finite cost. The start is inserted into the frontier. Each iteration removes an entry with minimum priority, checks whether it represents a current best route to its state, and then tests for a goal. If it is not a goal, its outgoing transitions are examined. For a successor vv of uu, the candidate cost is

gcandidate=g(u)+c(u,v).g_{\mathrm{candidate}}=g(u)+c(u,v).

If this is smaller than the recorded value for vv, the algorithm updates the cost and predecessor and arranges for vv to be processed with its new priority.

The following pseudocode uses duplicate queue entries rather than requiring a decrease-key operation:

g[start] := 0
parent[start] := none
push OPEN with (h(start), 0, start)

while OPEN is not empty:
    (priority, saved_g, u) := pop entry with minimum priority

    if saved_g != g[u]:
        continue

    if u satisfies the goal test:
        return reconstruct_path(parent, u)

    for each transition u -> v with cost c(u, v):
        candidate := g[u] + c(u, v)

        if v has no recorded cost or candidate < g[v]:
            g[v] := candidate
            parent[v] := u
            push OPEN with (candidate + h(v), candidate, v)

return failure

When a state’s cost improves, older queue entries become stale and are ignored when removed. This version permits a state to be expanded again after a genuine improvement, which is necessary for general admissible but inconsistent heuristics. With a consistent heuristic, an explicit closed set can instead permanently settle a state on its first valid expansion.

The goal test belongs at removal from the priority queue, not merely at discovery. For example, suppose an edge from the start reaches a goal at cost 10, while another route reaches it through an intermediate state at total cost 2. Discovering the cost-10 edge does not establish its optimality. The frontier ordering is what determines when the algorithm has enough evidence to terminate.

Equal ff-values require a secondary ordering. Preferring larger gg, equivalently smaller hh within an equal-ff group, often moves exploration toward a goal rather than across a broad cost contour. Other tie-breaking policies are possible. They can substantially change runtime and memory consumption without changing the primary optimality guarantee.

Admissible and consistent heuristics

A heuristic is admissible when it never overestimates the true minimum remaining cost:

h(n)≤h∗(n).h(n)\leq h^*(n).

The customary formulation also takes h(n)≥0h(n)\geq 0 and h(t)=0h(t)=0 at every goal tt. An admissible value is a lower bound, not necessarily a statistically accurate prediction. An estimate that systematically understates the remaining cost may still be useful if it distinguishes promising states from clearly expensive ones.

A heuristic is consistent, also called monotone, when every transition satisfies

h(u)≤c(u,v)+h(v).h(u)\leq c(u,v)+h(v).

This is a triangle-inequality condition: the estimate at uu cannot exceed the cost of going to vv plus the estimate there. With zero heuristic values at goals, consistency implies admissibility for states from which a goal is reachable. It also ensures that ff-values do not decrease along an individual search path. An admissible heuristic need not be consistent, so these concepts cannot be used interchangeably.

Geometry supplies several common examples. On a four-connected square grid with unit-cost horizontal and vertical moves, the Manhattan distance

h(n)=∣xn−xt∣+∣yn−yt∣h(n)=|x_n-x_t|+|y_n-y_t|

is admissible and consistent when obstacles only remove possible moves. Allowing diagonals changes the appropriate bound: Manhattan distance can then overestimate. With orthogonal cost 1 and diagonal cost 2\sqrt{2}, the obstacle-free shortest distance is the octile expression

h(n)=max⁡(Δx,Δy)+(2−1)min⁡(Δx,Δy).h(n)=\max(\Delta x,\Delta y) +(\sqrt{2}-1)\min(\Delta x,\Delta y).

Euclidean distance is another valid lower bound when transition costs are at least their geometric lengths.

More complex heuristics often come from relaxation: constraints are removed to produce an easier problem whose exact solution cannot cost more than the original. For a sliding-tile puzzle, summing each numbered tile’s Manhattan distance ignores interference between tiles. A pattern database goes further by storing exact costs for an abstraction, such as the positions of a selected subset of tiles. A lookup then supplies a lower bound for the original puzzle. Multiple admissible heuristics can safely be combined by taking their maximum. Adding them requires a separate justification, such as a partition of action costs that prevents double counting.

If h2(n)≥h1(n)h_2(n)\geq h_1(n) everywhere and both are admissible, h2h_2 is said to dominate h1h_1. It provides at least as strong a lower bound, although evaluating it may be more expensive. Heuristic design therefore involves both informativeness and computational cost. A learned estimate produced by machine learning does not automatically preserve admissibility; empirical prediction accuracy and a guaranteed lower bound are different properties.

Completeness, optimality, and necessary assumptions

The usual optimality argument relies on a lower-bound invariant. Let C∗C^* be the cost of an optimal solution. Before that solution has been found, a correctly maintained frontier contains some state on an optimal route with its optimal prefix cost. For an admissible heuristic, this state satisfies

f(n)=g∗(n)+h(n)≤C∗.f(n)=g^*(n)+h(n)\leq C^*.

A goal reached at a larger cost C>C∗C>C^* has f=Cf=C, because its heuristic is zero. It therefore cannot be selected ahead of every frontier state whose value is at most C∗C^*. This is the basis for terminating when a goal is removed from the queue.

In a tree search, different routes to the same underlying state are retained as separate search nodes. In graph search, they are merged, which saves work but requires careful cost handling. With a consistent heuristic, the first valid expansion of a state already uses its optimal path cost, so permanently closing it is safe. With an inconsistent heuristic, a cheaper route may appear later. Reopening the state, or otherwise propagating the improved cost correctly, is necessary to preserve the general optimality guarantee.

A small example illustrates the distinction. Consider edges s→as\to a of cost 3, s→bs\to b of cost 1, b→ab\to a of cost 1, and a→ta\to t of cost 3. Set h(a)=0h(a)=0, h(b)=4h(b)=4, and h(t)=0h(t)=0. These values are admissible, but the edge b→ab\to a violates consistency because 4>1+04>1+0. A* first expands aa at cost 3, then discovers through bb that aa can be reached at cost 2. If aa is never reopened and that improvement is not propagated, the search can return the cost-6 route instead of the optimal cost-5 route.

Completeness also requires attention to the size and costs of the search space. On a finite graph, ordinary nonnegative-cost assumptions, correct duplicate handling, and strict cost improvements give a straightforward termination argument. For an infinite, finitely branching search space, a standard sufficient condition is that every edge cost be bounded below by some ε>0\varepsilon>0. This prevents infinitely many successively deeper paths from remaining below a finite solution-cost bound. Zero-cost transitions or positive costs tending toward zero can defeat that argument.

Negative edges fall outside the standard assumptions and may invalidate the termination and optimality reasoning. Algorithms such as the Bellman–Ford algorithm address different shortest-path conditions. Finally, optimality is relative to the supplied graph and objective: a shortest grid path need not be the shortest physically realizable trajectory, and a minimum-distance route need not minimize travel time.

Computational cost and expansion behavior

A* can greatly reduce exploration, but it does not remove the underlying computational complexity of a difficult problem. In an implicit state space with branching factor bb and solution depth dd, the number of generated states can still grow exponentially with depth. The exact behavior depends on edge costs, duplicate states, heuristic errors, and the geometry of the search space. A statement such as “A* is exponential” describes an important worst-case risk, not a fixed runtime for every graph.

For a finite explicit graph and a consistent heuristic, states need not be reopened after expansion. With adjacency lists and a suitable binary-heap frontier, a standard bound is O((∣V∣+∣E∣)log⁡∣V∣)O((|V|+|E|)\log |V|), comparable to a common implementation of Dijkstra’s algorithm. This bound expresses cost in terms of the supplied graph. In planning and puzzle solving, however, that graph may be exponentially larger than the compact input describing it. With inconsistent heuristics, repeated improvements and re-expansions can add substantial work beyond a single scan of each state’s outgoing edges.

Heuristic quality can be understood through cost contours. In a standard complete search with a consistent heuristic, reachable states whose optimal-prefix evaluation g∗(n)+h(n)g^*(n)+h(n) is strictly below C∗C^* must be dealt with before an optimal goal can be selected. States on the boundary g∗(n)+h(n)=C∗g^*(n)+h(n)=C^* may or may not be expanded, depending on tie-breaking. A weak heuristic leaves many states below that boundary. A strong one raises the lower bounds of irrelevant alternatives and narrows the region requiring exploration.

Even a perfect heuristic does not eliminate every practical issue. If many optimal routes or zero-cost transitions produce a large equal-ff plateau, tie-breaking can still lead to substantial exploration. Conversely, the cost of computing a highly informative heuristic can outweigh the expansions it saves. Useful performance measurements therefore distinguish generated states, expanded states, heuristic evaluations, queue operations, elapsed time, and peak memory.

Memory is often the decisive limitation. A* normally retains frontier entries, discovered-state costs, and predecessor information. Its space complexity is proportional to the stored search records, which may be enormous even when individual transitions are cheap. An empirical measure called the effective branching factor summarizes expansion behavior by fitting a value b∗b^* to a relation such as

N≈1+b∗+(b∗)2+⋯+(b∗)d.N\approx 1+b^*+(b^*)^2+\cdots+(b^*)^d.

This is a comparative description of a particular experiment, not a universal constant of the algorithm or a substitute for time complexity analysis.

Memory-bounded, weighted, and incremental variants

Iterative deepening A*, or IDA*, replaces the stored frontier with repeated depth-first traversals bounded by an ff-threshold. The initial threshold is commonly h(s)h(s). When a traversal finds no solution, the next threshold is the smallest value that exceeded the previous bound. Richard Korf introduced the method in 1985. Its main advantage is low memory usage, roughly proportional to the active path for the basic tree-search formulation. Its main cost is repeated exploration, particularly when many distinct thresholds occur or transpositions are common.

Other memory-limited approaches retain selected portions of the search. Recursive best-first search stores a restricted recursive search structure and backs up estimated costs when abandoning a branch. Simplified memory-bounded A*, usually abbreviated SMA*, uses a fixed memory budget, discards less promising leaves, and retains backed-up information so that forgotten regions can later be regenerated. Their guarantees depend on the precise procedure and available memory; they are not simply ordinary A* with a smaller queue.

Weighted A* changes the evaluation function to

fw(n)=g(n)+w h(n),w>1.f_w(n)=g(n)+w\,h(n),\qquad w>1.

The larger heuristic contribution makes the search more goal-directed but generally sacrifices exact optimality. For an admissible base heuristic, nonnegative costs, zero heuristic at goals, and a version that correctly handles improvements and reopening, termination on a selected goal provides the standard bound

C≤wC∗.C\leq wC^*.

This follows because an optimal-route frontier state has weighted priority at most wC∗wC^*, while a goal’s priority equals its path cost. Implementations with different duplicate policies require their own analysis rather than inheriting this bound automatically.

Anytime search uses additional computation to improve an initial solution. Anytime Repairing A*, commonly called ARA*, begins with an inflated heuristic and progressively reduces the inflation while reusing search information. The result is a sequence of solutions accompanied by bounds under the algorithm’s assumptions. This is useful when an application needs a feasible answer quickly but can benefit from refinement before execution or while other work continues.

Incremental algorithms address changes between related problems. Lifelong Planning A* maintains information across modifications to edge costs, while D* Lite applies related principles to repeated navigation and replanning. If a robot discovers a blocked passage, these methods can repair affected parts of a previous search rather than solve the entire problem from scratch. They require additional state and update rules; changing the graph underneath an unmodified A* run does not preserve its guarantees.

Applications and state-space representations

In navigation, A* commonly searches a grid, a waypoint graph, or a navigation mesh. Grid cells make obstacle representation straightforward, but resolution controls both computational cost and geometric accuracy. A fine grid represents narrow passages more faithfully while increasing the number of states. A navigation mesh instead represents traversable regions and their connections. The resulting graph path may require a separate geometric procedure to produce a smooth route through those regions.

Robot motion planning makes the state-model issue especially important. A wheeled vehicle cannot necessarily follow every collision-free sequence of positions because it may have a minimum turning radius or restrictions on reversing. A search lattice can encode position, orientation, and feasible motion primitives. Hybrid A* combines discretized state indexing with continuous motion propagation. Such planners may use geometric or obstacle-aware lower bounds, but their claims of optimality must be interpreted relative to their representation and algorithmic details, not automatically as global optimality in continuous physical space.

Sliding-tile puzzles provide a clean combinatorial setting. In the 15-puzzle, each state specifies the arrangement of 15 numbered tiles and one blank on a 4×44\times4 board; transitions move a tile into the blank. A* can search for a minimum-move solution using Manhattan distance or stronger pattern-database estimates. The large number of possible configurations also illustrates why a theoretically effective heuristic does not remove memory constraints, and why IDA* has been important in optimal puzzle solving.

In automated planning, a state can be a set of propositions and a transition an action with preconditions, effects, and cost. The graph is generated as needed rather than supplied in advance. This connects A* to knowledge representation and reasoning: the representation determines which actions are possible, while a relaxed planning problem can supply the heuristic. For example, ignoring certain negative interactions between actions can make planning easier and yield a lower bound, provided the relaxation and cost calculation are constructed appropriately.

A* also appears in sequence comparison, parsing, and structured decoding when partial solutions form a graph and a valid lower bound on completion cost is available. In probabilistic sequence problems, negative logarithms can turn products of probabilities into additive costs. The heuristic must then bound the remaining score in the correct direction. More generally, A* minimizes one scalar additive objective. Problems involving several competing objectives, such as travel time, energy, and risk, require a defined scalar trade-off or a multiobjective search method that retains multiple nondominated labels per state.

Implementation correctness and practical limitations

A correct state representation must support reliable equality and hashing. Two records denoting the same future decision situation should normally be treated as one state, even if reached by different histories. Conversely, histories that change future possibilities cannot simply be discarded. In a resource-constrained route problem, reaching the same location with different remaining fuel may create genuinely different states. Duplicate detection that ignores fuel can eliminate the only feasible solution.

Priority-queue updates are another common source of errors. Some queues support decrease-key; others are simpler to use by inserting a new entry and discarding the stale one later. Whichever approach is chosen, the queue priority, recorded gg-value, predecessor, and reopening policy must remain compatible. A data structure optimized for fast lookup does not itself ensure that improvements are propagated correctly. Duplicate entries can also make queue memory much larger than the number of distinct states.

Numerical representation affects both behavior and guarantees. Integer costs avoid rounding issues when the objective is naturally integral, but additions must not overflow; integer overflow can make an expensive route appear artificially cheap. Floating-point costs require care with equality, comparisons, and accumulated error. Introducing a tolerance for “equal” costs may be useful operationally, but it changes which improvements are accepted and therefore needs to be reconciled with any exact optimality claim. Negative or nonfinite costs caused by data errors can invalidate the search assumptions.

Heuristic units require equal attention. Combining distance traveled with estimated time remaining has no coherent shortest-path meaning. For a minimum-time problem, straight-line distance divided by a justified upper bound on achievable speed can supply a time lower bound. Dividing by an average speed does not generally do so. Similarly, an obstacle penalty or learned preference added to hh may guide the search effectively while destroying admissibility unless a lower-bound argument supports it.

Testing can compare A* against Dijkstra’s algorithm on small instances, where an independent optimal cost is readily computed. Useful cases include an initial state that is already a goal, unreachable goals, multiple optimal paths, zero-cost edges, inconsistent heuristics, and states whose costs improve after earlier expansion. Local consistency checks can test h(u)≤c(u,v)+h(v)h(u)\leq c(u,v)+h(v) on generated edges; admissibility requires comparison with exact remaining costs or a separate proof. For safety-critical systems, formal verification can make the graph assumptions and update invariants explicit. Operational limits—such as memory exhaustion or an expansion cutoff—must distinguish an unfinished search from a proven absence of a solution.