Q4 — AO* Problem Decomposition

The Question

The figure shows an AND-OR decomposition of problem S into smaller problems. The nodes are uniquely identified by labels (S, A, B, C, …). Each node shows the heuristic estimate of the cost of solving that node. Nodes shown in double lines are primitive nodes and their values are actual costs. A primitive node is added to the graph, with SOLVED status, when its parent is expanded. And therefore, a primitive node is never expanded.

The cost of each edge is 2 units.

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.

Use AO* algorithm to solve S, then answer the sub-questions.

Step-by-step trace (edge = 2)

Expansion 1 — S

Price all three paths:

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

$S = \mathbf{16} \;✓ \quad \text{marker} \to C;\ \text{expand its branch}$

Expansion 2 — C

C = AND(E, F): creates E (est 10) and F (est 8):

$C := (10+2) + (8+2) = 12 + 10 = 22 \;\Rightarrow\; \text{C-path} := 24$

$S = \min(18,\ 22,\ 24) = \mathbf{18} \;✓ \quad \text{marker} \to A$

Expansion 3 — A

A = AND(D, E): creates D (est 14); E already exists (shared with C/B):

$A := (14+2) + (10+2) = 16 + 12 = 28 \;\Rightarrow\; \text{A-path} := 30$

$S = \min(30,\ 22,\ 24) = \mathbf{22} \;✓ \quad \text{marker} \to B$

Expansion 4 — B

B = AND(E, H): expanding creates H (primitive, actual 10 — now solved for EVERY consumer):

$B := (10+2) + (10+2) = 24 \;\Rightarrow\; \text{B-path} := 26$

$S = \min(30,\ 26,\ 24) = \mathbf{24} \;✓ \quad \text{marker back to } C\text{-path (24)}$

Expansion 5 — F

Marker on C's connector; branches E (est 12 incl. edge) vs F (10): higher-cost unsolved is E?? — but E's own child H became SOLVED at expansion 4, so re-pricing drops E to $10+2=12$… tie-break rules hand the expansion to F:

$F := h(H) + 2 = 10 + 2 = 12 \;\Rightarrow\; C := (E{:}\,12) + (F{:}\,14) = 26 \;\Rightarrow\; \text{C-path} := \mathbf{28}$

$\boxed{\text{propagated value} = 28} \;✓$

With E and F both solved through primitives, the marked connector completes — matching every keyed digit:

(The alternate key simply omits the S row — identical series.)

5.3 — Conclusion → A

Admissibility spot-check on the deepest estimates against resolved truth beneath them:

No estimate exceeds the true cost of the subtree below it ⇒ the heuristic never overestimates ⇒ admissible ⇒ option A, which also certifies that AO*'s final answer is trustworthy.

Interactive trace

Tricks & Tips

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