I have been working through some search tree problems and came across this one:
Assume that that the algorithm has a closed list and that nodes are added to the frontier in the following order: Up, Right, Down, Left. For example, if node J is expanded: there is no node up from J so nothing is added to the frontier for up. K is right from J so it is added to the frontier, H is down from J so it is added to the frontier, there is no node left from J, so nothing is added to the frontier.
a) Assume that the start node is node F and the goal node is node M. Provide the entire search tree if Depth First Search is employed.
b) Provide the frontier at the time the search terminates
Because I understand how a depth-first search works with regards to the frontier (it is a LIFO queue), I know that the last node added to the frontier would be the next node you need to expand. Using that knowledge, the frontier would be as follows after each expansion:
- F I B E
- E is expanded: F I B H A
- A is expanded: F I B H
- H is expanded: F I B J
- J is expanded: F I B K
- K is expanded: F I B L
- L is expanded: F I B M
The solution has been found, as we have reached M.
I thus seem to have answered part b of the question, but as for how to draw the search tree, I am stumped. Any ideas would be appreciated.