1
$\begingroup$

In Artificial 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?

$\endgroup$
  • $\begingroup$ 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 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). $\endgroup$ – nbro Nov 18 '20 at 22:36
  • 1
    $\begingroup$ @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. $\endgroup$ – Gu Liqi Nov 19 '20 at 20:49
  • $\begingroup$ 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. $\endgroup$ – nbro Nov 19 '20 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.