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:

f(N) = g(N) + h(N)

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


text
AStar(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:

h(N) \leq h^*(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) \leq g(N) + h^*(N) = C^*$ (by admissibility)
$f(N) \leq 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

h_1

dominates

h_2

h_1(N) \geq h_2(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 $h_1$ never expands more nodes than A* with $h_2$

3.6 A* Properties

Property	Value
Optimal?	Yes (with admissible heuristic)
Complete?	Yes (finite state space)
Time complexity	$O(b^d)$ worst-case
Space complexity	$O(b^d)$ — 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