Admissibility
h(n) ≤ actual distance to target. Guarantees optimal path found. Zero heuristic → A* = Dijkstra.
Advertisement
Consistency
h(u) ≤ w(u,v) + h(v). Stronger than admissibility. Ensures node closed only once (no re-opening).
Advertisement
Common heuristics
Grid: Manhattan, Euclidean, Chebyshev. Road networks: straight-line distance. Puzzles: pattern databases.
Complexity
Best case: O(N) with perfect heuristic. Worst: same as Dijkstra. Practice: often 10-100x faster.