[Solved]: Using tree search

Problem Detail: 

I have some questions regarding tree search and graph search (Uninformed search) as explained in chapter 3 of the book : http://aima.cs.berkeley.edu/

As I see, the only difference between the two is that the graph search handles loops (avoids them).

First question: Do both graph search and tree search build dynamic trees of the problem at hand?

Second question: I assume graph search was used to solve the map of Romania problem (getting from Arad to Bucharest) with DFS, BFS, UCS as strategies that only sort the frontier queue. Now is there a standard way to change the graph of map of Romania to a tree, and then use tree search?

Third question: What are some of the Criteria that help us choose between graph and tree search for different problems?

Thanks you in advance

Asked By : Martin H. L.

Answered By : jmite

Both BFS and DFS take a graph and induce a subgraph of it. This subgraph has all the nodes reachable from the start node, and is a tree.

You could probably convert a graph to a tree and then use tree search, but it seems to me that the easiest way to convert a graph to a tree is, in fact, some kind of search, and it would be redundant to use search to convert the graph, then do another search on the tree, when you could have just used the initial search.

You want to use graph search on graphs, and tree search on trees. In particular, this is because graphs which are cyclic can get caught in infinite loops if you use a tree-search on them.

(Note, if we're talking directed graphs, there is probably a special kind of tree search for an acyclic graph. For undirected graphs, and acyclic connected undirected graph is just a tree)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9979