Answers.Body: <p>To draw the <em>search tree</em>, 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 <span class="math-container">$F$</span>, which would have the children <span class="math-container">$I$</span>, <span class="math-container">$B$</span>, and <span class="math-container">$E$</span>. Then <span class="math-container">$E$</span> would have the children <span class="math-container">$H$</span>, <span class="math-container">$F$</span> and <span class="math-container">$A$</span>, and so on.</p>
  <p>So, here's a simple illustration of this partially constructed search tree.</p>
  <pre><code>   F
    /|\
   / | \
  I  B  E
       /|\
      / | \
     H |F| A
          /|\
         / | \
  </code></pre>
  <p>Note that I added <span class="math-container">$F$</span> again to the search tree, but you should not expand it again, otherwise, you end up looping forever. I denoted it by <code>|F|</code> 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.</p>
  <p><a href="https://www.youtube.com/watch?v=h1RYvCfuoN4&amp;ab_channel=JohnLevine" rel="nofollow noreferrer">Here</a> 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 <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">Artificial Intelligence: A Modern Approach</a> by Russell and Norvig (you can also find freely downloadable pdfs of the 3rd edition on the web), specifically, chapter 3 &quot;Solving Problems by Searching&quot;.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-23T12:48:09.860Z
Answers.LastActivityDate: 2021-08-23T13:00:14.017Z
Answers.LastEditDate: 2021-08-23T13:00:14.017Z
Answers.UserDisplayName: nbro
Body: <p>I have been working through some search tree problems and came across this one:</p>
  <p><a href="https://i.sstatic.net/Lqmy6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Lqmy6.png" alt="enter image description here" /></a></p>
  <p><strong>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.</strong></p>
  <p><strong>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.</strong></p>
  <p><strong>b)    Provide the frontier at the time the search terminates</strong></p>
  <p>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:</p>
  <ol>
  <li>F</li>
  <li>F I B E</li>
  <li>E is expanded: F I B H A</li>
  <li>A is expanded: F I B H</li>
  <li>H is expanded: F I B J</li>
  <li>J is expanded: F I B K</li>
  <li>K is expanded: F I B L</li>
  <li>L is expanded: F I B M</li>
  </ol>
  <p>The solution has been found, as we have reached M.</p>
  <p>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.</p>
  
Tags: <search><depth-first-search>
Title: How do I create the search tree for DFS applied to a grid map?
UserDisplayName: Gerhardus Carinus
ThreadText: # How do I create the search tree for DFS applied to a grid map?
  
  (Asked by: username_0 on 2021-08-21)
  
  I have been working through some search tree problems and came across this one:
  
  [![enter image description here](https://i.sstatic.net/Lqmy6.png)](https://i.sstatic.net/Lqmy6.png)
  
  **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.
  
  **Tags:** search, depth-first-search
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-08-23. Score: 2 | Accepted answer
  
  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](https://www.youtube.com/watch?v=h1RYvCfuoN4&ab_channel=JohnLevine) 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](http://aima.cs.berkeley.edu/) 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".
  
  
  ---
  
  