Question 17
PROBLEM DECOMPOSITION
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
Determine the value of the start node S after each node is expanded. Enter the value of S after each node is expanded.
Enter a comma separated list of numbers.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 12,42,17