Question 5
SEARCH
The MoveGen function and the heuristic function for a state space is provided below. Take S as the start node and G as the goal node.
When required use alphabetical order to break ties.
| x | MoveGen(x) | h(x) |
|---|---|---|
| S | F,H | 15 |
| A | B,C,D,E | 13 |
| B | A,D,G | 6 |
| C | A,F,H | 15 |
| D | A,B,E | 5 |
| E | A,D,H,I | 6 |
| F | C,H,S | 14 |
| G | B,D,I | 0 |
| H | C,E,S | 10 |
| I | E,G | 7 |
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
What is the path found by Depth First Search?
Enter the path as a comma separated list of node labels.
Enter NIL if a path to goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: S,X,Y,G