Next: Means-Ends Analysis
Up: Knowledge Representation and Search
Previous: And-Or Graphs
- Initialise
the graph to start node
- Traverse the graph following the current path
accumulating nodes that have not yet been expanded or solved
- Pick any of
these nodes and expand it and if it has no successors call this value
FUTILITY otherwise calculate only
for each of the successors.
- If is 0 then mark the node as SOLVED
- Change the value of for
the newly created node to reflect its successors by back propagation.
- Wherever possible use the most promising routes and if a node is marked
as SOLVED then mark the parent node as SOLVED.
- If starting
node is SOLVED or value greater than FUTILITY, stop, else repeat
from 2.
For further detail on 
Algorithm see
(Last year's AI1 notes Lecture 12).