The AO* algorithm:
Step 1: Place the start node s on open
Step 2: Using the search tree constructed thus far, compute the most promising solution tree T1
Step 3:Select a node n that is both on open and a part of T1. Remove n from open and place it on closed
Step 4: If n is terminal goal node, label n as solved. If the solution of n results in any of n’s ancestors being solved, label all the ancestors as solved. If the start node s is solved, exit with success where T1 is the solution tree. Remove from open all nodes with a solved ancestor
Step 5: If n is not a solvable node, label n as unsolvable. If the start node is labeled as unsolvable, exit with failure. If any of n’s ancestors become unsolvable because n is, label them unsolvable as well. Remove from open all nodes with unsolvable ancestors
Otherwise, expand node n generating all of its successors. For each such successor node that contains more than one sub-problem, generate their successors to give individual sub-problems. Attach to each newly generated node a back pointer to its predecessor. Compute the cost estimate h* for each newly generated node and place all such nodes that do not yet have descendants on open. Next recomputed the values oh h* at n and each ancestors of n
Step 7: Return to step 2
Inteligence uses cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.OkPrivacy policy
Answer ( 1 )
The AO* algorithm:
Step 1: Place the start node s on open
Step 2: Using the search tree constructed thus far, compute the most promising solution tree T1
Step 3:Select a node n that is both on open and a part of T1. Remove n from open and place it on closed
Step 4: If n is terminal goal node, label n as solved. If the solution of n results in any of n’s ancestors being solved, label all the ancestors as solved. If the start node s is solved, exit with success where T1 is the solution tree. Remove from open all nodes with a solved ancestor
Step 5: If n is not a solvable node, label n as unsolvable. If the start node is labeled as unsolvable, exit with failure. If any of n’s ancestors become unsolvable because n is, label them unsolvable as well. Remove from open all nodes with unsolvable ancestors
Otherwise, expand node n generating all of its successors. For each such successor node that contains more than one sub-problem, generate their successors to give individual sub-problems. Attach to each newly generated node a back pointer to its predecessor. Compute the cost estimate h* for each newly generated node and place all such nodes that do not yet have descendants on open. Next recomputed the values oh h* at n and each ancestors of n
Step 7: Return to step 2