1. One-Liner
A* expands paths minimizing f(n)=g(n)+h(n): cost so far plus heuristic estimate to the goal; with admissible h, it finds optimal paths.
2. The Problem It Solves
Shortest / cheapest path in large graphs (grids, maps) faster than Dijkstra when a good heuristic focuses search toward the goal.
3. The Core Idea
Best-first guided by h: if h never overestimates (admissible), the first time a goal is popped with consistent tie-breaking, cost is optimal.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Priority queue by f=g+h; g[s]=0 |
| 2 | Pop node with smallest f |
| 3 | If goal: return path |
| 4 | Relax neighbors; push if improved g |
| 5 | Closed set can skip stale entries |
5. Dry Run Example
Grid: Manhattan distance to goal as h. A* visits far fewer cells than Dijkstra expanding in all directions.
6. Key Properties
| Property | Value |
|---|---|
| Admissible h | h(u) ≤ true distance ⇒ optimal |
| Consistent | Triangle inequality ⇒ no reopen |
7. Where It Is Used
| System | Use |
|---|---|
| Games | NPC pathfinding |
| Maps | Heuristic routing |
8. Interview Tips
Define g vs h, admissible vs consistent, when A* degrades to Dijkstra (h=0).
9. Comparison with Other Algorithms
| A* | Dijkstra | Greedy Best-First | |
|---|---|---|---|
| f | g+h | g | h only |
| Optimal? | If h admissible | Yes | No |
10. Complexity
| -- | -- |
|---|---|
| Time | Worst exponential in search space; practical with good h |
| Space | O(b^d) frontier in worst case |
Implementation Example (PYTHON)
import heapq
def astar(edges, n, start, goal, h):
g = {start: 0}
pq = [(h(start), start)]
parent = {start: None}
while pq:
f, u = heapq.heappop(pq)
if u == goal: break
for v, w in edges.get(u, []):
ng = g[u] + w
if v not in g or ng < g[v]:
g[v] = ng
parent[v] = u
heapq.heappush(pq, (ng + h(v), v))
return g.get(goal)