Body: <p>In <em>Artiﬁcial Intelligence A Modern Approach</em>, search algorithms are divided into <strong>tree-search</strong> version and <strong>graph-search</strong> version, where the <strong>graph-search</strong> version keeps an extra <strong>explored set</strong> to avoid expanding nodes repeatedly.</p>
  <p>However, in <strong>breadth-first search</strong> or <strong>A* search</strong>, I think we still need to keep the expanded nodes in the memory so that we can <strong>track the path</strong> from the root to the goal. (The node structure contains its parent node which can be used to extract the solution path, but only if we have those nodes kept in the memory)</p>
  <p>So, if I'm right, why do we need the <strong>tree-search</strong> version in BFS and A*, given that the expanded nodes still need to be stored? Why not just use the <strong>graph-search</strong> version then?</p>
  <p>If I'm wrong, so how do we track the solution path given that the expanded nodes have been discarded?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-18T22:36:28.587Z
Comments.Text: The problem (and, at the same time, advantage) of graph search is that you use a closed list, where you store nodes. It's a problem because this list can grow, so the space complexity of the graph search can be bigger than the tree search's space complexity. The use of the graph search or tree search will then probably depend on your requirements. See [this answer](https://ai.stackexchange.com/a/9554/2444) too. So, I _guess_ that the answer to your question is that the nodes of the path will be fewer than all other nodes that have been visited (i.e. the nodes in the closed list).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-19T20:49:16.433Z
Comments.Text: @nbro Thanks for answering my question! You said that the nodes of the path will be fewer than all other nodes that have been visited. However, I won't know the solution path until I find a solution, so I still need to store all the nodes though only a small part of them are in the solution path. So that's what confuses me most, both the tree-search version and graph-search version need to store all the nodes to find the path.
Comments.UserDisplayName: Gu Liqi
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-19T20:56:36.520Z
Comments.Text: Hm, right... Thinking about it a little more, I guess that you can retrieve the path lazily without needing to store all information of the nodes of the path _in the frontier or closed list_. In other words, assuming that, while searching, you keep track of the parent of each node (in the nodes, which you need to have access to), for each path, you can then recursively follow these pointers/links, but, meanwhile, you don't necessarily need to store all information of these nodes _in another list_ (which is not the list of nodes of your graph), such as the frontier or closed list.
Comments.UserDisplayName: nbro
Tags: <search><a-star><breadth-first-search><graph-search><tree-search>
Title: Why do we use the tree-search version of breadth-first search or A*?
UserDisplayName: Gu Liqi
ThreadText: # Why do we use the tree-search version of breadth-first search or A*?
  
  (Asked by: username_0 on 2020-11-18)
  
  In *Artiﬁcial Intelligence A Modern Approach*, search algorithms are divided into **tree-search** version and **graph-search** version, where the **graph-search** version keeps an extra **explored set** to avoid expanding nodes repeatedly.
  
  However, in **breadth-first search** or **A\* search**, I think we still need to keep the expanded nodes in the memory so that we can **track the path** from the root to the goal. (The node structure contains its parent node which can be used to extract the solution path, but only if we have those nodes kept in the memory)
  
  So, if I'm right, why do we need the **tree-search** version in BFS and A\*, given that the expanded nodes still need to be stored? Why not just use the **graph-search** version then?
  
  If I'm wrong, so how do we track the solution path given that the expanded nodes have been discarded?
  
  **Tags:** search, a-star, breadth-first-search, graph-search, tree-search
  
  > **Comments:**
  > **username_1**: The problem (and, at the same time, advantage) of graph search is that you use a closed list, where you store nodes. It's a problem because this list can grow, so the space complexity of the graph search can be bigger than the tree search's space complexity. The use of the graph search or tree search will then probably depend on your requirements. See [this answer](https://ai.stackexchange.com/a/9554/2444) too. So, I _guess_ that the answer to your question is that the nodes of the path will be fewer than all other nodes that have been visited (i.e. the nodes in the closed list).  
  > **username_0**: @username_1 Thanks for answering my question! You said that the nodes of the path will be fewer than all other nodes that have been visited. However, I won't know the solution path until I find a solution, so I still need to store all the nodes though only a small part of them are in the solution path. So that's what confuses me most, both the tree-search version and graph-search version need to store all the nodes to find the path.  
  > **username_1**: Hm, right... Thinking about it a little more, I guess that you can retrieve the path lazily without needing to store all information of the nodes of the path _in the frontier or closed list_. In other words, assuming that, while searching, you keep track of the parent of each node (in the nodes, which you need to have access to), for each path, you can then recursively follow these pointers/links, but, meanwhile, you don't necessarily need to store all information of these nodes _in another list_ (which is not the list of nodes of your graph), such as the frontier or closed list.  
  
  ---
  
  ## 0 answers
  
  