14
$\begingroup$

I have read various answers to this question at different places, but I am still missing something.

What I have understood is that a graph search holds a closed list, with all expanded nodes, so they don't get explored again. However, if you apply breadth-first-search or uniformed-cost search at a search tree, you do the same. You have to keep the expanded nodes in memory.

$\endgroup$
9
$\begingroup$

There is always a lot of confusion about this concept, because the naming is misleading, given that both tree and graph searches produce a tree (from which you can derive a path) while exploring the search space, which is usually represented as a graph.

Differences

Firstly, we have to understand that the underlying problem (or search space) is almost always represented as a graph (although the underlying graph may not contain cycles, so it may represent a tree). So, the difference is not whether the problem is a tree (a special kind of graph), or a general graph!

The distinction is, instead, how we are traversing the search space (represented as a graph) to search for our goal state and whether we are using an additional list (called the closed list) or not.

So, the basic differences are

  1. In the case of a graph search, we use a list, called the closed list (also called explored set), to keep track of the nodes that have already been visited and expanded, so that they are not visited and expanded again.

  2. In the case of a tree search, we do not keep this closed list. Consequently, the same node can be visited multiple (or even infinitely many) times, which means that the produced tree (by the tree search) may contain the same node multiple times.

Advantages and disadvantages

The advantage of graph search obviously is that, if we finish the search of a node, we will never search it again. On the other hand, the tree search can visit the same node multiple times.

The disadvantage of graph search is that it uses more memory (which we may or may not have) than tree search. This matters because graph search actually has exponential memory requirements in the worst case, making it impractical without either a really good search heuristic or an extremely simple problem.

So, there is a trade-off between space and time when using graph search as opposed to tree search (or vice-versa).

Conclusion

So, the difference between tree search and graph search is not that tree search works on trees while graph search works on graphs! Both can work on trees or graphs (but, given that graphs are a generalization of trees, we can simply say that both work on graphs, either trees or not) and both produce a tree!

Notes

The definitions of tree search and graph search given above are based on the definitions given in section 3.3 (page 77) of the book Artificial Intelligence: A Modern Approach (3rd edition), by Stuart J. Russell and Peter Norvig, which is the de-facto standard book in artificial intelligence, so these definitions are applicable in the context of artificial intelligence (which is also the context of this site)!

However, note that, occasionally, people may use the term tree search to refer to a tree traversal, which is used to refer to a search in a search tree (e.g., a binary search tree or a red-black tree), which is a tree (i.e. a graph without cycles) that maintains a certain order of its elements. This is another reason for having different definitions of a tree search and to think that a tree search works only on trees.

| improve this answer | |
$\endgroup$
  • $\begingroup$ My understanding of tree is that trees are not only a form of directed graph but the nodes are ORDERED, making the tree unique from a graph. Because a tree is ordered, there are no loops. Thus, a node shouldn't ever appear as multiple different nodes of the tree unless the implementer did something very wrong, because keeping track of the list of nodes visited is implicit as part of tree traversal algorithms. $\endgroup$ – Dunk Dec 18 '18 at 21:04
  • $\begingroup$ @Dunk What do you mean by "a tree is ordered"? Not all trees necessarily have their elements ordered. There are trees, like red-black trees (or, in general, binary search trees), that maintain a certain order of their stored elements, but not all tress maintain a certain order of their elements. So, a tree has no loops not because it is ordered, but because there are no cycles (of the form A -> B -> A). $\endgroup$ – nbro Nov 10 '19 at 22:41
  • $\begingroup$ @Dunk In a search tree, nodes are ordered, but not in trees in general, except in the sense of depth. Tree search however, is not "search on trees", but a specific family of search algorithms used in AI that are only guaranteed to work on tree structured problems, although they may be applied to other problems (where they may, or may not, fail). $\endgroup$ – John Doucette Nov 11 '19 at 1:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.