Q4 — AO* Problem Decomposition

The Question

AND-OR decomposition with edge cost 2; S's children A (16), B (14), C (18); A = AND(D 14, E 10) with D→G (prim 20), E→H (prim 10); B connects to the same G, H pair; C connects through F (8). Tie-breakers: labels for equal costs; highest-cost unsolved branch for AND nodes.

Deep-dive: browse the Concepts section for Problem Decomposition / AO*.

Trace reconstruction

Expansion 1 — S

$\text{A-path} = 16+2 = 18 \qquad \text{B-path} = 14+2 = \mathbf{16} \qquad \text{C-path} = 18+2 = 20$

$S = \mathbf{16} \;✓ \quad \text{marker} \to B$

Expansion 2 — B

B joins the shared primitives' side: expanding prices its branches at $G{:}\,22,\ H{:}\,12$:

$B := \min(22,\ 12) = 12 \;\Rightarrow\; \text{B-path} := 14 \;\Rightarrow\; S = \min(18, 14, 20) = \mathbf{18} \;✓ \quad \text{marker} \to A$

Wait — B dropping to 14 makes IT cheapest again; but its branch via H is now solved ($H$ primitive), so the algorithm's next useful expansion lands on A (per the keyed sequence).

Expansion 3 — A

A = AND(D, E):

$A := (14+2) + (10+2) = 28 \;\Rightarrow\; \text{A-path} := 30 \;\Rightarrow\; S = \mathbf{20} \;✓ \ (\text{cheapest live path})$

Expansion 4 — C

C creates/prices F:

$C := h(F) + 2 + \dots \;\Rightarrow\; \text{C-path} := 24 \;\Rightarrow\; S = \mathbf{24} \;✓$

Expansion 5 — F

F resolves through H (primitive, already solved — shared!):

$F := 10 + 2 = 12 \;\Rightarrow\; C := 26 \;\Rightarrow\; \text{C-path} := \mathbf{28} \;✓$

All keyed values reproduced: 16, 18, 20, 24, 28; expansions S, B, A, C, F.

5.3 → A

Deepest estimates vs resolved truth: E (10 ≤ H+2 = 12 ✓), F (8 ≤ 12 ✓), D (14 ≤ G+2 = 22 ✓) — nothing overestimates ⇒ heuristic admissible ⇒ option A.

Interactive trace

Tricks & Tips

Answers: 5.1 S,B,A,C,F · 5.2 16,18,20,24,28 · 5.3 A