What is the difference between graph search and tree search?

Question

What is the difference between graph search and tree search versions regarding DFS, A* searches in artificial intelligence?

Answer 1

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

The Problem Is Always a Graph

The distinction between tree search and graph search is not rooted in the fact whether the problem graph is a tree or a general graph. It is always assumed you're dealing with a general graph. The distinction lies in the traversal pattern that is used to search through the graph, which can be graph-shaped or tree-shaped.

If you're dealing with a tree-shaped problem, both algorithm variants lead to equivalent results. So you can pick the simpler tree search variant.

Difference Between Graph and Tree Search

Your basic graph search algorithm looks something like the following. With a start node start, directed edges as successors and a goal specification used in the loop condition. open holds the nodes in memory, which are currently under consideration, the open list. Note that the following pseudo code is not correct in every aspect (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 obtain different variants of search algorithms, like depth-first search (DFS) (pick newest element), breadth first search (BFS) (pick oldest element) or uniform cost search (pick element with lowest path cost), the popular A-star search by choosing the node with lowest cost plus heuristic value, and so on.

The algorithm stated above is actually called tree search. It will visit a state of the underlying problem graph multiple times, if there are multiple directed paths to it rooting in the start state. It is even possible to visit a state an infinite number of times if it lies on a directed loop. But each visit corresponds to a different node in the tree generated by our search algorithm. This apparent inefficiency is sometimes wanted, as explained later.

Graph Search

As we saw, tree search can visit a state multiple times. And as such it will explore the "sub tree" found after this state several times, which can be expensive. Graph search fixes this by keeping track of all visited states in a closed list. If a newly found successor to next is already known, it won't 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 graph search requires more memory, as it keeps track of all visited states. This may compensated by the smaller open list, which results in improved search efficiency.

Optimal solutions

Some methods of implementing select can guarantee to return optimal solutions - i.e. a shortest path or a path with minimal cost (for graphs with costs attached to edges). This basically holds whenever nodes are expanded in order of increasing cost, or when the cost is a nonzero positive constant. A common algorithm that implements this kind of select is uniform cost search, or if step costs are identical, BFS or IDDFS. IDDFS avoids BFS's aggressive memory consumption and is generally recommended for uninformed search (aka brute force) when step size is constant.

A*

Also the (very popular) A* tree search algorithm delivers an optimal solution when used with an admissible heuristic. The A* graph search algorithm, however, only makes this guarantee when it used with a consistent (or "monotonic") heuristic (a stronger condition than admissibility).

(2) Flaws of pseudo-code

For simplicity, the presented code does not:

• handle failing searches, i.e. it only works if a solution can be found