A* Heuristic Search theory

The A* evaluation function estimates the total cost of the cheapest path from start vertex s to goal vertex g passing through vertex n: f(n) = g(n) + h(n). Here, g(n) is the exact cost of the shortest path found so far from s to n (historical cost-to-come), updated dynamically through edge relaxation. The term h(n) is an admissible and consistent heuristic function estimating the minimum cost from n to g (prospective cost-to-go). The sum f(n) represents the total estimated cost, allowing A* to prioritize nodes that balance verified short distance from the start with promising proximity to the target.

A heuristic h(n) is admissible if it never overestimates the true minimum cost to reach the goal g from node n: 0 ≤ h(n) ≤ h*(n) for all n, with h(g) = 0. Admissibility guarantees that A* will never overlook an optimal shortest path: if a sub-optimal path reaches the goal first, there will always remain an unexpanded node on the optimal path in the Open Set with a strictly smaller f-value, ensuring that the optimal node is expanded prior to accepting the sub-optimal goal. Thus, admissibility guarantees mathematical optimality of the returned path.

Admissibility requires that h(n) ≤ h*(n) globally. Consistency (or monotonicity) is a stronger local condition requiring that for every node n and each successor n' reached via edge (n, n'), the heuristic satisfies the triangle inequality: h(n) ≤ c(n, n') + h(n'). A consistent heuristic guarantees that f(n) is monotonically non-decreasing along every path (f(n') ≥ f(n)). Crucially, consistency guarantees that when a node n is extracted from the Open Set, its g(n) value is already strictly optimal, meaning closed nodes never need to be reopened, enabling highly efficient graph search with O(1) closed-set lookups.

Dijkstra's algorithm is mathematically equivalent to A* with h(n) = 0, meaning f(n) = g(n). Without directional information, it expands nodes strictly in order of distance from the start, generating a uniform circular wavefront that expands all nodes within radius D, resulting in area πD² = Θ(D²) expansions. In contrast, an admissible and consistent Manhattan heuristic adds a strong directional potential gradient toward the goal. In 4-connected grid movement, the heuristic value drops by 1 for each step toward the goal, keeping f(n) = g(n) + h(n) constant along the direct line of sight while increasing f for lateral deviations. A* thus restricts exploration to a narrow linear corridor along the path, expanding only ~3 nodes per step (E(D) = 3D = O(D)).

On a 4-connected grid where only orthogonal movements (N, S, E, W with cost 1) are permitted, the Manhattan distance h(n) = |Δx| + |Δy| is both admissible and consistent, and accurately reflects true grid distances. Euclidean distance h(n) = √(Δx² + Δy²) is also admissible on a 4-connected grid, but because it assumes straight-line diagonal travel (which is impossible on a 4-connected grid), it severely underestimates true path costs (by up to √2 ≈ 1.414×), causing A* to expand more nodes than Manhattan. Conversely, on an 8-connected grid with diagonal movement, Manhattan distance overestimates diagonal costs (2 instead of √2) and is inadmissible, while Octile or Euclidean distance is required to maintain admissibility.

Greedy Best-First Search evaluates nodes using only the heuristic function: f(n) = h(n), completely ignoring historical path cost g(n). It always expands the node that appears closest to the goal. While this can reach the goal rapidly in open terrain, it is not optimal: it readily chooses a path with expensive edge weights if the endpoints look close, and it can become trapped in dead ends, U-shaped obstacles, and concavities, backtracking extensively and producing wildly sub-optimal routes.

Jump Point Search (Harabor and Grastien, 2011) is an algorithmic optimization for uniform-cost grid maps that eliminates the overhead of inserting every intermediate grid cell into the Open Set. JPS exploits grid symmetries: instead of stepping node by node, it shoots straight horizontal, vertical, and diagonal rays (jumping) until it hits an obstacle boundary or discovers a 'forced neighbor'—a turning point where the path must bend around an obstacle. Only these jump points are inserted into the Open Set, reducing priority queue operations by 90% to 95% while preserving 100% path optimality.