A best-first graph search algorithm that orders node expansion by a cost function f(n)=g(n)+h(n), where g(n) is the cost from the start to node n and h(n) is a heuristic estimate of the cost from n to a goal; with an admissible (and preferably consistent) heuristic, A* finds least-cost paths efficiently.

Principle

Prioritize nodes with lowest estimated total cost (g + h); admissibility of h (never overestimates true cost) ensures that the first time a goal node is popped from the frontier it is optimal, and consistency (monotonicity) simplifies bookkeeping and guarantees non-decreasing f-values along paths.

Demonstration

Pathfinding on a grid: use g(n) as path length so far and h(n) as Manhattan distance to the target. A* expands nodes that appear promising under f; if h is Manhattan distance on 4-connected orthogonal moves, A* will find the shortest grid path without exploring all cells. In robotics, A* plans discrete routes on occupancy grids.

Misapplication

Using an inadmissible heuristic (one that overestimates) can produce suboptimal paths; poor heuristics that are too weak (close to zero) degrade A* to Dijkstra's algorithm, causing excessive expansions and memory use; ignoring memory limits can make A* impractical on large graphs.

Consequence

When a good admissible heuristic is available, A* greatly reduces node expansions compared to uninformed search and produces optimal paths; it also provides a flexible framework for variants (weighted A*, IDA*) that trade optimality for speed or memory.

Reversal

Dijkstra's algorithm corresponds to A* with h=0 (uninformed) and is optimal but may explore more; greedy best-first search uses f=h and can be faster but is not guaranteed to be optimal.

Boundary

Designed for discrete state-space search and shortest-path problems with nonnegative edge costs and well-defined goal tests; continuous problems require discretization or specialized continuous variants; optimality depends on heuristic properties and cost assumptions.

Semantic Tension

Tension between admissibility/optimality and practical speed: admissible heuristics guarantee optimality but may be conservative; weighted or inadmissible heuristics speed up search but risk suboptimal solutions. Also tension between memory consumption (frontier size) and expansion rate.

Synthesis

A* combines actual cost from the start and heuristic cost-to-go into a unified ordering that, with an admissible heuristic, yields optimal, often efficient search; practical deployment balances heuristic design, memory constraints, and acceptable trade-offs between speed and optimality.