Admissibility vs. Consistency (Monotonicity)
Let $\delta(u, t)$ denote the true shortest-path distance from vertex $u$ to target $t$. The behavior and complexity of A* depend on two hierarchy conditions on the heuristic function $h: V \to \mathbb{R}_{\ge 0}$ (with $h(t) = 0$):
- Admissibility (Never Overestimates): $h$ is admissible if for all $u \in V$: $$0 \le h(u) \le \delta(u, t)$$ Admissibility guarantees that when target $t$ is popped from the priority queue, $g(t) = \delta(s, t)$ is optimal (since $f(t) = g(t) + 0$, and any alternative path through an open node $x$ has $f(x) = g(x) + h(x) \le g(x) + \delta(x, t)$).
- Consistency / Monotonicity (Triangle Inequality): $h$ is consistent if $h(t) = 0$ and for every directed edge $(u, v) \in E$: $$h(u) \le w(u, v) + h(v) \iff w_h(u, v) := w(u, v) - h(u) + h(v) \ge 0$$ Every consistent heuristic is automatically admissible (by telescoping along any shortest path $u \leadsto t$). Crucially, under consistency, any path $P: s \leadsto u$ has reduced weight $w_h(P) = w(P) - h(s) + h(u) = f(u) - h(s)$. Since $w_h(u, v) \ge 0$, A* is literally Dijkstra's algorithm on $w_h$, guaranteeing every vertex is popped and expanded at most once!
Canonical Grid & Geometric Heuristics
- 4-Directional Grid (Up/Down/Left/Right, unit cost): Manhattan distance $h(u) = |x_u - x_t| + |y_u - y_t|$ is both admissible and consistent.
- 8-Directional Grid (King moves cost $1$): Chebyshev distance $h(u) = \max(|x_u - x_t|, |y_u - y_t|)$. (If diagonal moves cost $\sqrt{2}$, use Octile distance: $\Delta_{\max} + (\sqrt{2} - 1)\Delta_{\min}$).
- Continuous 2D/3D Euclidean Space or Road Networks: Euclidean distance $h(u) = \|p_u - p_t\|_2 / v_{\max}$ (straight-line distance divided by the maximum legal highway speed).
Compare Dijkstra’s uniform radial frontier against A* directional pruning f(u) = g(u) + h(u) and OSRM Contraction Hierarchies (shortcut insertion w(u,w)=w(u,v)+w(v,w) + upward rank-monotonic bidirectional search).
Invariant & State
std::hypot / sqrt Latency in Inner LoopsOn x86-64/ARM64, 64-bit floating-point sqrt has 12–20 cycles throughput latency and converts integer distances into floats. On 4-connected or 8-connected grids, always use exact integer heuristics (Manhattan $|dx| + |dy|$ or scaled Octile $1000(\Delta_{\max}) + 414(\Delta_{\min})$) so priority queue keys remain 64-bit integers compared in a single ALU cycle.
Complexity Matrix
| Heuristic Class | Guarantees Optimal Path? | Max Expansions per Vertex | Worst-Case Time |
|---|---|---|---|
| Zero Heuristic ($h(u) = 0$) | Yes (Standard Dijkstra) | 1 | O((V + E) log V) |
| Consistent ($h(u) \le w(u,v) + h(v)$) | Yes | 1 | O((V + E) log V) |
| Admissible Only ($h(u) \le \delta(u, t)$) | Yes (if re-expansion allowed) | O(2^V) | Exponential (if closed set re-opened) |
| Weighted A* ($f = g + \epsilon \cdot h, \epsilon > 1$) | $\epsilon$-Approximation ($\le \epsilon \cdot \text{OPT}$) | 1 (without re-opening) | O((V + E) log V) |
Production Implementation: A* Search on a Weighted Graph
#include <vector>
#include <queue>
#include <limits>
#include <functional>
struct AStarEdge {
int to;
long long weight;
};
long long astarShortestPath(int n, int start, int target,
const std::vector<std::vector<AStarEdge>>& adj,
const std::function<long long(int)>& heuristic) {
constexpr long long INF = std::numeric_limits<long long>::max() / 4;
std::vector<long long> gScore(n, INF);
std::vector<uint8_t> closed(n, 0);
using State = std::pair<long long, int>; // (fScore = g + h, u)
std::priority_queue<State, std::vector<State>, std::greater<State>> openSet;
gScore[start] = 0;
openSet.emplace(heuristic(start), start);
while (!openSet.empty()) {
auto [f, u] = openSet.top();
openSet.pop();
if (u == target) return gScore[target];
if (closed[u]) continue; // Sound and optimal when heuristic is consistent!
closed[u] = 1;
for (const auto& e : adj[u]) {
long long tentativeG = gScore[u] + e.weight;
if (tentativeG < gScore[e.to]) {
gScore[e.to] = tentativeG;
openSet.emplace(tentativeG + heuristic(e.to), e.to);
}
}
}
return -1; // Target unreachable
}On a grid where diagonal movement is allowed with cost $1$ (or $\sqrt{2} \approx 1.414$), moving from $(0, 0)$ to $(1, 1)$ has true distance $1$ (or $1.414$), but Manhattan distance gives $h = |1 - 0| + |1 - 0| = 2 > \delta$. Because Manhattan distance overestimates diagonal shortcuts, it is inadmissible on 8-way grids and can return suboptimal paths! Always match the norm to the allowed move set ($L_1$ for 4-way, $L_\infty$ / Octile for 8-way, $L_2$ for any-angle).