How do I create the search tree for DFS applied to a grid map?

Question

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:

1. F
2. F I B E
3. E is expanded: F I B H A
4. A is expanded: F I B H
5. H is expanded: F I B J
6. J is expanded: F I B K
7. K is expanded: F I B L
8. 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.

Answer 1

To draw the search tree, you just need to add as children the nodes that you found (i.e. the nodes that you add to the queue and that you may expand next). So, in your case, the root node of the tree would be $F$, which would have the children $I$, $B$, and $E$. Then $E$ would have the children $H$, $F$ and $A$, and so on.

So, here's a simple illustration of this partially constructed search tree.

   F
  /|\
 / | \
I  B  E
     /|\
    / | \
   H |F| A
        /|\
       / | \

Note that I added $F$ again to the search tree, but you should not expand it again, otherwise, you end up looping forever. I denoted it by |F| to differentiate it from the others. Moreover, note that the creation of the search tree does not really depend on the actual problem, but on the search algorithm and how you expand nodes/states.

Here you can find a nice step-by-step example of how to construct the search tree of DFS, in case my explanation above is not clear enough. You can also find more info about this topic in the book Artificial Intelligence: A Modern Approach by Russell and Norvig (you can also find freely downloadable pdfs of the 3rd edition on the web), specifically, chapter 3 "Solving Problems by Searching".