Question 4
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.
List the first 4 nodes inspected by Depth First Search. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: S,X,Y,Z