Answer ( 1 )

  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

Leave an answer