What is the difference between graphical search and tree search?

Question

What is the difference between graph search and tree search with respect to DFS, A * searches in artificial intelligence?

Answer 1

Judging by the existing answers, there seems to be a lot of confusion in this concept.

The problem is always on schedule.

The distinction between tree search and graph is not based on whether the problem graph is a tree or a general graph. It is always assumed that you are dealing with a general schedule. The difference lies in the crawl pattern, which is used to search in a graph, which may take the form of a graph or tree.

If you are dealing with a tree-shaped problem, both versions of the algorithm produce equivalent results. Thus, you can choose a simpler search option on the tree.

Difference Between Graph and Tree Search

Your main graph search algorithm looks something like this: From the beginning of the start node, oriented edges like successors and goal specifications used in state loops. open contains the nodes in memory that are currently under review, an open list. Please note that the following pseudo-code is not correct in all aspects (2).

Tree search

 open <- [] next <- start while next is not goal { add all successors of next to open next <- select one node from open remove next from open } return next 

Depending on how you implement select from open , you get different options for search algorithms, such as depth search (DFS) (select a new item), width search (BFS) (select the oldest item) or a search with a uniform cost (selecting the item with the lowest path cost), the popular A-star search by selecting the node with the lowest cost plus heuristic value and so on.

The above algorithm is actually called tree search . He will visit the state of the main problem graph several times if there are several directed paths to it with the root in the initial state. You can even visit the state an infinite number of times if it lies on a directed loop. But each visit corresponds to a separate node in the tree generated by our search algorithm. This apparent inefficiency is sometimes required, as explained later.

Graph search

As we have seen, a tree search can visit a state several times. And as such, he will several times examine the "subtree" found after this condition, which can be expensive. A graph search corrects this by keeping track of all visited states in a closed list. If the newly found successor next already known, it will not be inserted into the open list:

 open <- [] closed <- [] next <- start while next is not goal { add next to closed add all successors of next to open, which are not in closed remove next from open next <- select from open } return next 

comparison

We notice that a graph search requires more memory, as it keeps track of all the states visited. This can be offset by a smaller open list, which leads to increased search efficiency.

Optimal solutions

Some select implementation methods can guarantee the return of optimal solutions - that is, the shortest path or the path with the least cost (for graphs with costs tied to edges). This is mainly done whenever nodes expand in order of increasing cost or when the cost is a nonzero positive constant. A common algorithm that implements this type of selection is a search with uniform cost , or, if the cost per step is identical, BFS or IDDFS . IDDFS avoids the aggressive use of BFS memory and is usually recommended for uninformed search (aka brute force) when the step size is constant.

A *

Also, the (very popular) A * tree search algorithm provides an optimal solution when used with valid heuristics . However, the search algorithm for the graph A * gives such a guarantee only if it is used with a consistent (or "monotonic") heuristic (a stronger condition than admissibility).

(2) Pseudo-code disadvantages

For simplicity, the presented code does not have:

• handle failed searches, that is, it only works if a solution can be found

Answer 2

A tree is a special case of a graph, so everything that works for general graphs works for trees. A tree is a graph where there is exactly one path between each pair of nodes. This means that it does not contain cycles, as the previous answer claims, but a directed graph without cycles (DAG, directed acyclic graph) is not necessarily a tree.

However, if you know that your schedule has some limitations, for example. Since it is a tree or a DAG, you can usually find a more efficient search algorithm than for an unlimited graph. For example, it probably does not make sense to use A * or its non-heuristic analogue of the “Dijkstra's algorithm” on a tree (where there is only one path that you can find using DFS or BFS) or on DAG (where the optimal path can be found by looking at the vertices in the order obtained by topological sorting).

As for directed vs non-oriented, an undirected graph is a special case of a directed graph, namely, the case following the rule "if there is an edge (link, transition) from u to v, there is also an edge from v to u.

Refresh . Please note: if you are interested in the search crawl pattern, and not the structure of the chart itself, this is not the answer. See, for example, @ ziggystar answer.

Answer 3

The only difference between the graph and the tree is the loop. A graph can contain loops, a tree cannot. Therefore, when you are going to implement a search algorithm on a tree, you do not need to consider the existence of loops, but when working with an arbitrary graph, you will need to consider them. If you do not process loops, the algorithm may end up in an infinite loop or infinite recursion.

Another point to think about is the directional properties of the graph you are dealing with. In most cases, we are dealing with trees that represent the relationship between parents and children on each edge. DAG (directed acyclic graph) also shows similar characteristics. But bidirectional graphics are different. Each edge in bidirectional graphs represents two neighbors. Therefore, algorithmic approaches should be slightly different for these two types of graphs.

Answer 4

In simple words, a tree does not contain cycles and where can there be a graph. Therefore, when we perform a search, we should avoid loops in graphs so that we do not fall into infinite loops.

Another aspect is that the tree typically has some topological sorting or property, such as a binary search tree, that makes searching so quick and easy compared to graphs.

Answer 5

GRAPH VS TREE

• Graphs have loops
• Trees do not have cycles. For example, imagine any tree in your head, branches do not have direct connections to the root, but branches have connections with other branches up "

But in case of AI Graph-search vs Tree-search

A graph search has the good property that whenever an algorithm examines a new node and marks it as visited, "Regardless of the algorithm used," the algorithm usually examines all the other nodes that are reachable from the current node.

For example, consider the following graph with three vertices AB and C and consider the following edges

AB, BC and CA, well, there is a cycle from C to A,

And when the DFS, starting from A, A will generate a new state B, B will generate a new state C, but when C is examined, the algorithm will try to create a new state A, but A has already been visited, so it will ignore it. Cool!

But what about trees? tree tree algorithm is not marked by visited node as visited, but trees have no cycles, how would it end up in infinite cycles?

Consider this tree with three vertices and consider the following edges

A - B - C, based on A, down. And suppose we use the DFS algorithm

A will generate a new state B, B will generate two states A and C because the trees do not have “Mark a node if it was examined”, therefore, perhaps the DFS algorithm will examine A again, a new state B, so we we get an infinite loop.

But you noticed something, we are working on non-oriented edges, that is, there is a connection between AB and BA. Of course, this is not a cycle, because a cycle means that the vertices must be> = 3, and all the vertices are different except for the first and last nodes.

ST A-> B-> A-> B-> A is not a cycle, because it violates the cycling property> = 3. But really A-> B-> C-> A - cycle> = 3 Checked nodes, the first and last node will be the same.

Again, consider the edges of the tree, A-> B-> C-> B-> A, of course, this is not a cycle, because there are two Bs, which means that not all nodes are different.

Finally, you can implement a tree search algorithm to double-examine the same node. But this has consequences.