Using tree search

Question

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

Answer 1

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)

Answer 2

To use which search method(tree search or graph search) depending on the question that you'r handling. Usually the view to think the question affect the solving method. The two search method differ from handling different structures, tree search handle with tree and graph search handle with graph. As we know, the tree is a special kind of graph, which has no cycles. So, if you can modeling the question as a tree, then you can use tree search easily. For example, in the Eight Puzzle, the number which is not in the edge can has 4 decisions, let's consider a case, we move a number up, and the number still has 4 decisions in the new location, but when we deal this question, we only prepare 3 decisions in the new location to avoid the new state is same with the previous. This restriction is helpful to solve the problem. Then the Eight Puzzle solving process can construct a state transfer tree.