Neural Sync Active
⭐ A* Search
Registry Synced
⭐ A* Search
878 words
4 min read
Reading compass
Now · 1. 🎯 Learning Objectives
⭐ A* Search
1. 🎯 Learning Objectives
- Trace A* with f(N)=g(N)+h(N) showing OPEN/CLOSED tables
- Prove A* admissibility: if h(N) ≤ true cost, A* finds optimal path
- Explain the dominance relation among heuristics
- Compare A* with Best First Search and Branch & Bound
- Identify when A* degenerates into BFS or DFS
2. 📖 Core Content
3.1 Intuition: Combining Cost-So-Far with Estimated-Remaining
Best First Search uses only h(N) (estimated remaining cost) — it's greedy. Branch & Bound uses only g(N) (cost so far) — it explores all promising partial solutions.
A* combines both:
Where:
- g(N): Actual cost from start to N (known)
- h(N): Estimated cost from N to goal (heuristic)
- f(N): Estimated total cost through N
3.2 The A* Algorithm
textAStar(initial_state, goal_test, move_gen, heuristic): OPEN = priority_queue() // Ordered by f(N) = g(N) + h(N) OPEN.add(initial_state, h(initial_state)) g[initial_state] = 0 CLOSED = {} nodePairs = {} while OPEN is not empty: N = OPEN.extract_min() if goal_test(N): return reconstruct_path(N, nodePairs) CLOSED.add(N) for each child in move_gen(N): tentative_g = g[N] + cost(N, child) if child in CLOSED and tentative_g >= g[child]: continue // Already have a better path if child not in OPEN or tentative_g < g[child]: g[child] = tentative_g f[child] = tentative_g + h(child) OPEN.add(child, f[child]) nodePairs[child] = N return NO_SOLUTION
3.3 Worked Example: A* Trace
Simple route-finding graph with heuristic h(N) = straight-line distance to goal:
(Diagram)
h(S)=7, h(A)=6, h(B)=2, h(C)=3, h(D)=1, h(G)=0
| Step | OPEN (f) | CLOSED | N | g(N) | f(N) | Successors | Notes |
|---|---|---|---|---|---|---|---|
| 0 | {S(7)} | {} | — | — | — | — | Start |
| 1 | {} | {S} | S | 0 | 7 | A(g=1,f=7), B(g=4,f=6) | Expand S |
| 2 | {A(7), B(6)} | {S} | B | 4 | 6 | D(g=5,f=6) | B has lower f |
| 3 | {A(7), D(6)} | {S,B} | D | 5 | 6 | G(g=7,f=7) | D has lower f |
| 4 | {A(7), G(7)} | {S,B,D} | A | 1 | 7 | C(g=3,f=6), D(g=6,f=7) | A has f=7 |
| 5 | {C(6), G(7), D(7)} | {S,B,D,A} | C | 3 | 6 | G(g=6,f=6) | C lower f |
| 6 | {G(6), G(7), D(7)} | {S,B,D,A,C} | G | 6 | 6 | — | Goal! |
Wait — we need to be more careful. Let me re-trace:
Step 0: OPEN = {S(7)}. g(S)=0. Step 1: Pop S (f=7). Not goal. Successors: A (g=1, h=6, f=7), B (g=4, h=2, f=6). Add A and B to OPEN. Step 2: OPEN = {A(7), B(6)}. Pop B (lowest f=6). Not goal. Successors: D (g=4+1=5, h=1, f=6). Add D. Step 3: OPEN = {A(7), D(6)}. Pop D (f=6). Not goal. Successors: G (g=5+2=7, h=0, f=7). Add G. Step 4: OPEN = {A(7), G(7)}. Pop A (f=7) — tie with G, but A was added earlier. Successors: C (g=1+2=3, h=3, f=6), D (g=1+5=6, h=1, f=7). D is in CLOSED, tentative_g=6 ≥ g[D]=5, so skip. Add C. Step 5: OPEN = {C(6), G(7)}. Pop C (f=6). Not goal. Successor: G (g=3+3=6, h=0, f=6). G is in OPEN with f=7. New path g=6 < old path g=7, so update G's f to 6. Step 6: OPEN = {G(6)}. Pop G (f=6). Goal! Path: S-A-C-G (cost 6).
Note: A* found the optimal path S-A-C-G (total cost 6) instead of S-B-D-G (cost 7). The heuristic properly guided A* to the better path.
3.4 Admissibility
Definition: A heuristic h is admissible if for all nodes N:
where h∗(N) is the true minimal cost from N to the goal.
Admissibility Theorem: If h is admissible, A* returns the optimal (least-cost) solution.
Proof sketch:
- Assume A* returns a suboptimal path with cost C>C∗ (optimal)
- At the point where A* terminates, there must be some node N on the optimal path in OPEN
- f(N)=g(N)+h(N)≤g(N)+h∗(N)=C∗ (by admissibility)
- f(N)≤C∗<C=f(G) (where G is the goal A* returned)
- So A* would have expanded N before G — contradiction
3.5 Dominance
Definition: Heuristic h1 dominates h2 if h1(N)≥h2(N) for all nodes N (and both are admissible).
A dominating heuristic is better because:
- It provides tighter bounds
- It prunes more nodes
- It expands fewer states
- A* with h1 never expands more nodes than A* with h2
3.6 A* Properties
| Property | Value |
|---|---|
| Optimal? | Yes (with admissible heuristic) |
| Complete? | Yes (finite state space) |
| Time complexity | O(bd) worst-case |
| Space complexity | O(bd) — stores all generated nodes |
| OPEN order | f(N)=g(N)+h(N) |
3.7 When A* Degrades
- h(N) = 0 for all N: A* becomes BFS (or Dijkstra for weighted graphs)
- h(N) very accurate: A* expands almost only nodes on the optimal path
- h(N) > h(N)* (inadmissible): A* may return suboptimal solutions
- h(N) very inaccurate: A* may expand almost as many nodes as BFS
4. 📝 Practice Questions
Q1: Show that the Manhattan distance heuristic is admissible for the 8-puzzle.Answer: Manhattan distance sums the horizontal and vertical distances each tile must travel. Each move moves one tile one step, reducing Manhattan by at most 1. Therefore, the true minimum moves ≥ Manhattan distance. Hence h(N) ≤ h*(N) — admissible. Q2: If h(N) is admissible but not consistent, what could go wrong?Answer: A* may need to re-expand nodes (move from CLOSED back to OPEN) when a better path is found. This increases time but does not affect optimality. With a consistent heuristic, the first expansion of a node is always optimal. Q3: Does a dominating heuristic always reduce A's runtime?*Answer: A dominating heuristic prunes more nodes (reducing expansions) but takes more time per node to compute. There is a trade-off between heuristic accuracy and computational cost. Join Discord PreviousAdmissibility & ConsistencyNextTSP Branch & Bound