What is the difference between Tree search and Graph Search?
A:There is always a lot of confusion about this concept. (And the naming does not help!) The other answers present so far are not correct.
Firstly, we have to understand that the underlying problem is almost always a graph - So, the difference is not whether the problem is a tree (a special kind of graph), or a general graph!
The distinction instead is how we are traversing to search for our goal state. It also includes whether we are storing closed list, or not.
So, the basic difference is:
-
If doing graph search, keep a “closed” list, that is, a list of nodes where the search has been completed.
(记录所走的路径)
-
If doing tree search, we don’t keep this closed list.
(不记录所走路径)
The advantage of graph search obviously is that if we finish the search of a node, we will never search it again, while we may do so in tree search.
The disadvantage of graph search is that it uses more memory, which we may or may not have.
In other words, graph search vs. tree search is a simple space vs. time tradeoff.
Now, about the naming:
Graph Search is called graph search, because when we observe the traversal structure, we observe a GRAPH, that this node leads us to the other node that we saw before, etc, etc.
Tree search is called a tree search, because when we observe the traversal structure, we observe a TREE. We observe a tree, even if the underlying problem structure is a graph. This is because when we observe a node, we have no recollection of having seen it earlier, we don’t store that list, etc. So, the same node in the underlying problem structure can appear as multiple times (as different nodes) of the tree.
Reference
- https://ai.stackexchange.com/questions/6426/what-is-the-difference-between-tree-search-and-graph-search?answertab=oldest#tab-top
