4
$\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. But 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$
  • $\begingroup$ The number of possible implementations of tree search algorithm is very high. One example is Monto-carlo-tree search. In the context of AI it is important to give always the context of a problem, for example to ask for a pathplanning algorithm which guides Mrs. Pacman into a goal, or discuss a tree in which a genetic program is stored. What programmers need to judge about a certain algorithm is the cpu usage. For example if the graph is used for caching the result, it is possible to realize a speed up. Or if a certain game like Go has a high branching factor, it is possible to be pessimistic. $\endgroup$ – Manuel Rodriguez May 15 '18 at 14:42
4
$\begingroup$

Strictly speaking they're the same: a tree is a graph, but one which among other criteria is minimally connected (only one path between any two nodes) and acyclic (ie no loops).

So, for searching, algorithms operating on trees can make a certain set of assumptions which allow optimisations not possible on a generalised graph. For example, for tree traversal you know you will visit each node only once (due to the minimal connectivity), but for other graphs you need to keep track of visited nodes if you don't want to process them multiple times (as there could be multiple paths leading to the same nodes).

$\endgroup$
  • $\begingroup$ Sorry, this answer is not correct - tree is a graph, but tree search vs. graph search is not about the structure of the underlying problem. $\endgroup$ – Amrinder Arora Dec 16 '18 at 19:52
  • $\begingroup$ Great answer--concise and clear. (I might add that trees are a form of directed graph.) $\endgroup$ – DukeZhou Dec 16 '18 at 22:29
0
$\begingroup$

Expanding from the answer that @Oliver Mason gave, they are both graphs but only that a tree graph is a special case scenario.
The main difference is in the search pattern that is used to search through the graph.
Difference:

  • Graph search uses more memory because it stores all the cycles of the tree
$\endgroup$
0
$\begingroup$

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:

1) If doing graph search, keep a "closed" list, that is, a list of nodes where the search has been completed.

2) 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.

$\endgroup$
  • $\begingroup$ tbh, I can't see why the other answers are not correct. You simply re-state what I have said in my answer. $\endgroup$ – Oliver Mason Dec 17 '18 at 9:11
  • $\begingroup$ I am not sure how your answer and my answer are the same, or even similar. For example, your answer starts as "Strictly speaking they're the same". My answer actually suggests that they are quite different. The code of graph search and tree search (or pseudocode), is quite distinct. $\endgroup$ – Amrinder Arora Dec 18 '18 at 20:04
  • $\begingroup$ Where is your source of information for the definition of "Tree Search" versus "Graph Search" because I think everybody's distinction's mentioned so far are wrong to some degree? 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$ This is in most of the AI textbooks, usually the early chapters. For example, the standard text by Russell and Norvig covers this in chapter 3, around the page 90. $\endgroup$ – Amrinder Arora Dec 18 '18 at 21:45

Your Answer

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

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