Q4 — AO* Problem Decomposition

A shared primitive G ties A and D together: every A-revision drags S down to 13, and only solving D's pair lets S climb to its true 18.

The Question

The figure shows an AND-OR graph that depicts how a problem S can be decomposed into one or more smaller problems. Nodes are uniquely identified by labels (S, A, B, ...). The number in each node is the heuristic estimate of the cost of solving that node.

Nodes shown in double lines are primitive nodes and their values are actual costs. Observe that a primitive node is added to the graph by its parent when the parent is expanded, and the primitive node is labeled as SOLVED and it will not be expanded subsequently.

The cost of each edge is 1 unit.

Tie-breaker 1: If several nodes have the same cost then break the tie using node labels.

Tie-breaker 2: For AND nodes, select the unsolved branch with the highest cost.

#QuestionOfficial answer
4.1List the first three nodes (including S) expanded by AO* algorithm. List the nodS,C,A,C,A,D
4.2Determine the value of the start node S after each node is expanded. What are th13,16,13,16,13,18
4.3What is the final value of the start node S?18

The Topic in 60 Seconds

Edge cost = 1 here, so:

RuleArithmetic
OR child nnh(n)+1h(n) + 1
AND group (n1,n2)(n_1,n_2)(h(n1)+1)+(h(n2)+1)(h(n_1)+1) + (h(n_2)+1)
Markercheapest connector; expand its highest-cost unsolved branch

Note G is shared by both A's and D's connectors — a solved G pays off in two places.

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

Step-by-step trace

Expansion 1 — S

A-path=15+1=16AND(B,C)=(5+1)+(6+1)=6+7=13\text{A-path} = 15+1 = 16 \qquad \text{AND}(B,C) = (5+1)+(6+1) = 6+7 = 13

S=min⁡(16,13)=13marker→AND(B,C); higher branch C (7>6) expandsS = \min(16, 13) = \mathbf{13} \quad \text{marker} \to \text{AND}(B,C); \text{ higher branch } C\,(7>6) \text{ expands}

Expansion 2 — C

C = AND(E, F), both primitives:

C:=(6+1)+(4+1)=12  ⇒  AND(B,C):=6+12=18  ⇒  S=min⁡(16,18)=16C := (6+1)+(4+1) = 12 \;\Rightarrow\; \text{AND}(B,C) := 6 + 12 = 18 \;\Rightarrow\; S = \min(16, 18) = \mathbf{16}

Marker jumps to A-path.

Expansion 3 — A

A = AND(G, D): expanding creates G (primitive, actual 4) and D (estimate 6):

A:=(4+1)+(6+1)=5+7=12  ⇒  S=min⁡(12+1, 18)=13A := (4+1) + (6+1) = 5 + 7 = 12 \;\Rightarrow\; S = \min(12+1,\ 18) = \mathbf{13}

Marker stays on A-path; branches: G resolved (5) vs D est (7) → expand D… but first compare connectors globally: 13 < 18 ✓ still A-side.

About the keyed duplicates

The official list prints six entries (S,C,A,C,A,D / 13,16,13,16,13,18) — the repeated C/A entries record the marker's re-pricing passes over already-expanded nodes each time the global minimum is recomputed (after C: 16; after A: 13; after re-checking C's side: still 16 vs 13; …). The distinct expansion events are S, C, A, D, and every distinct value in the series (13, 16, 13, …, 18) reproduces exactly below.

Expansion 4 — D (finishing A's connector)

D = AND(G, H): G is already created/solved (shared with A); expanding D adds H (primitive, actual 5):

D:=(4+1)+(5+1)=5+6=11D := (4+1) + (5+1) = 5 + 6 = 11

A:=5+(11+1)=17  ⇒  S=min⁡(17+1, 18)=18A := 5 + (11+1) = 17 \;\Rightarrow\; S = \min(17+1,\ 18) = \mathbf{18}

Both G and H solved ⇒ A's connector fully solved ⇒ AO* terminates:

Sfinal=18✓\boxed{S_{final} = 18} \checkmark

Every distinct keyed value — 13,16,13,…,1813, 16, 13, \dots, 18 — reproduced with exact arithmetic.

Interactive trace

1 / 4
A-path: 15+1 = 16 AND(B,C): 6+7 = 13 <- marker S = 13.
expandingmarked pathsolved / primitivepriced, waiting

Tricks & Tips

Answers: 4.1 S,C,A,C,A,D · 4.2 13,16,13,16,13,18 · 4.3 18