Minimum-cost paths appear in routing telephone traffic, navigation through a maze, printed-circuit layout, mechanical theorem proving and problem solving. A purely mathematical treatment studies graph structure and ordered expansion with correctness foremost. A heuristic treatment uses information peculiar to the domain: airline distance between cities or geometry in a theorem prover: to avoid exploring parts that look unpromising.

Hart, Nilsson and Raphael make heuristic information an explicit mathematical object. The estimate is not a mystical hunch. It is a number computed at a node, interpreted against a family of possible graphs consistent with the information available there. That interpretation lets the authors ask both whether the search returns an optimal path and whether another equally informed admissible search could guarantee the answer with fewer expansions.

The word “heuristic” therefore does not mean “unprincipled”. It marks incomplete problem information brought to bear on order of exploration. The estimate may be weak, strong, cheap, expensive, safely low or dangerously high. Each property belongs to a different question: guarantee, number of expansions and total computation must not be collapsed.

The resulting method is a family. Different choices of ĥ create different A* algorithms, all sharing the rule that the smallest evaluation is expanded next. The zero heuristic uses no domain information and reduces to lowest discovered path cost. A more informative lower bound can reduce expansion, provided the effort of computing it is itself worth paying.

The graph is directed. An arc from nᵢ to nⱼ need not imply a reverse arc, and if both exist their costs may differ. Every arc costs at least some positive δ. The positivity assumption later controls termination: a path with bounded total cost cannot contain arbitrarily many arcs.

From a specified start s, the successor operator Γ reveals pairs of successor nodes and costs. Repeated application generates an explicit searched subgraph. This is an economical model for problem spaces too large to list, such as moves in a game or symbolic transformations in a prover. Search pays to expose a node's outgoing structure only when it expands that node.

A path is an ordered sequence connected by directed arcs, and its cost is the sum of those arc costs. The goal set T is non-empty. For a node n, a preferred goal is a member of T reached at minimum possible cost from n. The authors write h(n) for that true remaining optimum; from the start, f(s)=h(s) is the cost of an unconstrained optimal solution.

The algorithm stores the cheapest path discovered so far to each encountered node and a predecessor pointer. When it terminates at a goal, the path is reconstructed by following pointers backwards. A node label is therefore not only a location; it is a mutable claim about the best known way to reach that location.

First mark the start open and calculate its evaluation. Then select an open node with smallest f̂, resolving ties arbitrarily but favouring a goal. If the selected node belongs to T, mark it closed and stop. Otherwise close it, apply Γ, update the discovered costs and predecessor pointers of its successors, and return to selection.

A new successor becomes open. A previously closed successor also becomes open when its evaluation is now lower than when it was closed. Because ĥ depends only on the node in the paper's presentation, that fall reflects a cheaper discovered path and a smaller ĝ. This reopening clause is part of the published A*, not a later embellishment.

Selection by minimum evaluation creates a best-first search over complete-route estimates. It is not greedy best-first search on ĥ alone: accumulated cost constrains how attractive a node may appear. Nor is it breadth-first expansion by number of arcs. Costs, not step counts, define the objective unless all arcs cost the same.

Favouring a goal in a tie makes termination precise. When a goal and non-goal share the smallest evaluation, choosing the goal returns a path with that value. The optimality comparison later has to handle ties separately because equally rated alternatives can change the exact set expanded without changing admissibility.

The ideal f(n)=g(n)+h(n) says how much an optimal start-to-goal path through n costs. Determining it exactly could be as hard as the original problem. The algorithm therefore stores ĝ(n), the cost of the cheapest start-to-n path it has discovered, and computes an estimate ĥ(n) of the cheapest remaining path to a preferred goal.

Its evaluation is f̂(n)=ĝ(n)+ĥ(n). The two hats have different epistemic roles. ĝ is the exact cost of a concrete witnessed prefix, although a cheaper prefix may still exist. ĥ is a domain-derived estimate of an unseen optimum. The algorithm does not average them; it joins evidence already constructed to a bound on evidence still required.

The small graph in the paper shows why ĝ can change. Starting from s, the first discovered costs of n₁ and n₂ are 3 and 7. Expanding n₁ reveals another route to n₂ with total cost 6, so ĝ(n₂) is lowered and its predecessor changes. Path reconstruction follows the final predecessor chain, not the first encounter.

If ĥ=0 everywhere, f̂=ĝ and A* expands the node reached most cheaply so far. With unit arc costs this resembles breadth-first search; with arbitrary positive costs it orders by accumulated cost. Adding a safe positive ĥ can discriminate between equally affordable prefixes by their remaining promise.

Lemma 1 says that for any unclosed node n and any optimal path from s to n, some open node n′ on that path has ĝ(n′)=g(n′). The frontier cannot lose every optimally reached prefix: when a predecessor closes, its next path node is generated with the correct prefix cost unless a still cheaper discovered route already exists.

Apply the lower-bound condition to an optimal start-to-goal path P. Before termination, some open n′ on P has f̂(n′)=g(n′)+ĥ(n′)≤g(n′)+h(n′)=f(s), the optimal solution cost. The selection rule therefore never needs to choose a node rated above the optimum while that witness remains open.

The proof then eliminates three failure modes. The algorithm cannot stop at a non-goal because its stopping test forbids that. It cannot stop at a more expensive goal because the protected frontier node would have a smaller evaluation and be selected first. It cannot expand forever below the optimal cost because every arc costs at least δ, leaving only finitely many accessible nodes within the bounded number of steps, with each reopen also finite under the paper's assumptions.

“Admissible” names this algorithmic guarantee, and ĥ≤h is the sufficient condition on the heuristic. The word does not say that every estimated value is accurate, consistent or close to h. Zero is admissible but may give little guidance. A negative estimate would also be a lower bound yet could distort order; the practical family usually uses non-negative cost estimates.

Let C* be the cost of a preferred goal from s. Because every arc costs at least δ>0, any path with more than M=C*/δ steps costs more than C*. The protected optimal-frontier node always has f̂≤C*, so A* does not need to expand a node whose ĝ alone is already above that ceiling.

Only nodes accessible within M steps can compete below the bound. Under the paper's locally finite generation assumptions, this set is finite. Reopening does not create a new node, but a node might be reached through several paths. Within a bounded number of steps there are only finitely many such paths, so the number of strict improvements and reopenings is also finite.

This is a proof about the formal model, not a universal runtime claim. A finite contender set can still be astronomically large, and an implicit successor operator may be expensive. The theorem establishes that the algorithm eventually reaches the optimal goal when one exists; it does not give a useful polynomial bound.

If costs can be negative, ranking partial paths by a discovered prefix and remaining lower bound needs a different analysis. If zero-cost cycles are permitted, depth is no longer controlled by cost. Modern formulations adopt their own conditions, but fidelity requires retaining the role of δ in this paper's termination case.

At node n, let Ωₙ index the subgraphs compatible with the information the problem domain supplies about that state. Each candidate graph implies some true remaining optimum hθ(n). The paper defines ĥ(n) as the infimum of those values. No compatible world has a cheaper remainder, so the estimate is a lower bound in every world the information permits.

With no domain information, almost any connection to a goal remains possible and the greatest guaranteed lower bound may be zero. Road geometry rules out “hyperspace” shortcuts: if roads connect Euclidean locations and length cannot be below straight-line distance, airline distance is safe. Stronger constraints shrink Ωₙ and can raise the infimum.

An algorithm A is “no more informed” than A* when, at every node and actual graph, A's possible-graph set includes A*'s set. A cannot rule out a world that A* must still consider. This is a partial order on information, not a claim about code sophistication, prediction accuracy or access to more processor time.

The construction is idealised. In practice one uses a procedure known to return a lower bound rather than enumerating possible graphs and taking an explicit infimum. The possible-world account supplies semantics for the number: a larger admissible estimate is licensed only by information that genuinely excludes cheap continuations.

For an arc or reachable relation from m to n, consistency requires h(m,n)+ĥ(n)≥ĥ(m), where h(m,n) is the true cheapest cost from m to n. On a single edge of cost c(m,n), the familiar sufficient form is ĥ(m)≤c(m,n)+ĥ(n). The estimated remainder may fall along an edge by no more than the cost paid to traverse it.

Under this condition, f̂ is non-decreasing along the nodes A* closes. Lemma 2 shows that when a node closes, ĝ(n)=g(n): the discovered prefix is already optimal. Consequently a later path cannot lower its ĝ, so the reopening provision becomes vacuous. The implementation can leave closed nodes permanently closed.

Admissibility alone is weaker. Every estimate can lie below its true remaining cost while neighbouring values still violate the triangle condition. Such an inconsistent heuristic can make a node look cheap early and reveal a better prefix later. The original loop remains correct because it can reopen that node and propagate the improvement.

The paper illustrates inconsistency with an order-dependent heuristic for cities: some nodes receive airline distance and others receive a crude constant. Each local number may be a lower bound, yet the computation rule does not use information uniformly. The resulting estimate at a successor can drop too sharply relative to the connecting cost.

In the no-tie case, the paper argues that any node expanded by A* must also be expanded by every admissible algorithm A that is no more informed. Before A* reaches its preferred goal, the node's f̂ lies below the optimal cost. Because some graph compatible with A's information makes a cheapest solution pass through that node, A cannot safely leave it unexpanded and still guarantee optimality in every permitted graph.

Define N(A,Gₛ) as the number of nodes algorithm A expands on the reachable graph. The corollary gives N(A*,Gₛ)≤N(A,Gₛ), with equality only when the expanded sets coincide, under the theorem's premises. The measure counts nodes, not generated arcs, queue operations, heuristic arithmetic, memory or wall-clock time.

Ties require care. A* may choose one of several nodes with the same critical evaluation while another admissible algorithm chooses differently. Theorem 3 says that for any admissible A there exists a member of the A* family: an A* tie-breaking rule: whose expanded nodes are included in A's. A later corollary bounds an arbitrary A* member by A's expansions plus the number of critical ties.

The authors note that if another algorithm expands fewer nodes on one graph, it can be “lucky”: there exists some graph consistent with the shared information on which its skipped node matters and it loses the guarantee or must search more. Optimality is minimax over compatible problems, not retrospective praise for every realised run.

The 1968 article states the expansion-optimality theorem under the consistency assumption. The correction observes that the required inequalities follow from a weaker relation: the heuristic lower bound and the definition of the best discovered prefix are sufficient for the main comparison. Theorems 2 and 3 can therefore be strengthened by dropping consistency.

The authors replace the dependency on Lemma 3 with a new corollary: while A* has not terminated, every closed node n has f̂(n)≤f(s), the optimal solution cost. The proof uses the open frontier node on an optimal path and the fact that n was selected ahead of it. It does not require the closed node's discovered prefix to be globally optimal.

Consistency remains necessary for the original Lemmas 2 and 3. In particular, it ensures ĝ(n)=g(n) when n closes and removes the need to consider reopening closed nodes. The correction thus separates a practical implementation property from the broader node-expansion result.

This distinction matters when reconstructing the paper today. Reporting only the 1968 premise repeats a known overrestriction; reporting that consistency is irrelevant to A* erases its no-reopen consequence. The accurate account keeps both dates: the original formalisation and the authors' explicit strengthening.

Set ĥ=0 and A* uses no domain information. In the cities example, this behaves as though roads could pass through hyperspace: the goal might be arbitrarily close in road cost regardless of coordinates. Euclidean distance adds a physical restriction and commonly reduces node expansion.

A weaker bound such as half the Manhattan coordinate displacement can remain admissible while expanding more nodes than Euclidean distance. It may be cheaper to calculate. The node-minimal method under one information model need not minimise arithmetic effort, memory traffic or latency. Choosing a heuristic is a resource allocation decision.

Raise ĥ beyond the greatest safe lower bound and A* is no longer admissible. The paper notes that such a choice may find a desirable, though not necessarily minimum, path with fewer expansions. That is a legitimate trade only when the application consciously relaxes the optimality requirement; it must not be reported as the same guarantee.

The graph model also bears responsibility. If Γ or arc costs poorly represent the real problem, an optimal graph path may be an inadequate real solution. Formal correctness is conditional on modelling choices. The authors explicitly return responsibility for an adequate mathematical representation to the investigator.

Review one: scholarship. The reconstruction retains the directed δ-graph, implicit Γ operator, preferred goals, mutable ĝ and predecessor pointers, goal-favouring tie rule, reopen condition, frontier lemma, three-case admissibility proof, possible-graph semantics of information, consistency triangle, node-expansion comparison and tie-qualified family result. The 1972 correction is treated as part of the governing evidence rather than a footnote.

Review two: teaching and execution. Ten accessible SVGs each have a unique title, description, caption and source scope; reduced-motion preference disables animation; labels carry meaning independently of colour. Twelve worked examples and twelve causal probes test every load-bearing boundary. The laboratory exhaustively checks 1,024 admissible heuristic configurations against uniform-cost search, verifies path certificates and audits every reopening.

AI-telltale and evidence review. The prose does not claim that A* “understands” a map or that heuristic information is a feeling. Later terms such as monotone heuristic and uniform-cost search are used for orientation without rewriting the 1968 notation. The expansion theorem is not inflated into a universal speed or memory theorem.

Scope review. The algorithm pursues a supplied start-to-goal objective on a supplied cost graph. It neither creates goals nor judges whether graph costs represent social, moral or strategic value. Its relevance to agency lies in explicit action selection under bounded information, with a certificate and stated failure conditions.

A* acts on an estimate without treating the estimate as fact. The path prefix is witnessed, the remainder is bounded, and the two are marked separately. This epistemic bookkeeping lets a machine exploit anticipation while retaining a proof obligation.

The open set materialises unresolved possibilities. Closing a node spends computation to expose its successors; reopening admits that a past commitment rested on an inferior route. Consistency is valuable because it turns a revisable action into a final one without weakening correctness.

Information has force only through exclusions. A higher heuristic is justified when domain knowledge rules out cheap compatible continuations, not when a score is merely confident. This makes the formalism an early lesson in evidence-bounded action: stronger guidance needs a stronger warrant.

The optimality theorem is comparative and conditional. It says that another admissible algorithm with no more information cannot guarantee avoiding A*'s necessary expansion work, apart from ties. That precision matters for intelligent systems: a local success can be luck, while a guarantee quantifies over the alternatives the agent could not distinguish.