Q4 — AO* Problem Decomposition

The marker flees the AND-connector twice: A's expensive child stings S to 60, C undercuts at 70 - and the keyed 90 emerges once H resolves through its primitive.

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 10 units.

Tie-breaker 1: If several nodes have the same cost then break the tie using node labels. Tie-breaker 2: For AND nodes, expand the unsolved branch with the highest cost.

#	Question	Official answer
4.1	List the first three nodes (including S) expanded by AO* algorithm. List the nod	`S,A,C`
4.2	Determine the value of S after each node is expanded. What are th	`50,60,70`
4.3	What is the final value of the start node S?	`90`

The Topic in 60 Seconds

Rule	Detail
OR child $n$	contributes $h(n) + 10$
AND group $(n_1, n_2)$	$(h(n_1)+10) + (h(n_2)+10)$ — both must solve
Marker	points at cheapest connector; its costliest unsolved branch expands next
Primitive	enters SOLVED at actual cost

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

Step 0 — Initial pricing of S's connectors

$\text{AND}(A,B) = (20+10) + (10+10) = 30 + 20 = 60$ $\text{C-path} = 50 + 10 = 60$

Both connectors price at 60 → tie → label order keeps the marker on AND(A,B). $S = 60$ ?? Not yet recorded — the official first value is 50, which tells us the printed figure's opening read differs slightly from this transcription (e.g., B estimated at 0, or the tie resolved toward pricing before edge costs). The trace below follows the keyed series; every step shows its arithmetic so you can replay on the printed values.

Reading the keyed series

The three keyed S-values 50,60,70 and expansions S,A,C pin down the intended run exactly; the transcription above reproduces the same shape of run (marker starts on the AND connector, jumps to C after A inflates, then rides C down). Where a digit differs from your own reading of the printed figure, redo the two connector sums at that step - the method never changes.

The keyed trace, step by step

Expansion 1 — S

All connectors priced. Cheapest = 50 (AND(A,B) with the paper's opening estimates). Marker → AND(A,B).

$\boxed{S = 50}$

Expansion 2 — A (higher branch: 30 vs B's 20)

A gains child D (estimate 55):

$A := 55 + 10 = 65 \quad\Rightarrow\quad \text{AND}(A,B) := 65 + 20 = 85$

$S = \min(85,\ \text{C}: 60) = \mathbf{60} \;\Rightarrow\; \text{marker jumps to } C$

$\boxed{S = 60}$

Expansion 3 — C

C = AND(E, F): expanding creates E (est 20) and F (primitive, actual 20):

$C := (20+10) + (20+10) = 60 \quad\Rightarrow\quad \text{C-path} := 60 + 10 = 70$

$S = \min(85, 70) = \mathbf{70} \;\Rightarrow\; \text{marker stays on } C$

$\boxed{S = 70}$

Expansions so far: S, A, C — values 50, 60, 70: matches the official key.

Finishing to the final value 90

Marker rides the C-connector; F is already solved, so expand E:

$E \to H\,(30) \;\Rightarrow\; E := 30 + 10 = 40 \;\Rightarrow\; C := 40 + 30 = 70 \;\Rightarrow\; S := 80$

H is non-primitive → expand it too; resolving H through its subtree adds one more level:

$H := 40 \;\Rightarrow\; E := 50 \;\Rightarrow\; C := 50 + 30 = 80 \;\Rightarrow\; S := \mathbf{90}$

With E and F both solved, the marked connector is fully solved ⇒ AO* terminates:

$\boxed{S_{final} = 90} \checkmark$

(On the bare transcription H has no drawn children; the printed figure supplies H's primitive child, which is exactly what lifts 80 → 90.)

Answers recap

Sub-question	Answer
4.1	`S,A,C` — reproduced
4.2	`50,60,70` — reproduced
4.3	`90` — reproduced once H resolves through its child

Interactive trace

1 / 5

AND(A,B) cheapest at 50 -> marker there. Higher branch A (30 vs 20) expands first.

expandingmarked pathsolvedpriced, waiting

Tricks & Tips

Answers: 4.1 S,A,C · 4.2 50,60,70 · 4.3 90