Completeness of depth-first search

Question

I quote from Artificial Intelligence: A Modern Approach:

The properties of the depth-first search depend strongly on whether the graph-search or tree-search version is used. The graph-search version, which avoids repeated states and redundant paths, is complete in the finite state spaces because it will eventually expand every node. The tree-search version, on the other hand, is not complete [...]. Depth-first tree search can be modified at no extra memory cost so that it checks new states against those on the path from the root to the current node; this avoids infinite loops in the finite state spaces but does not avoid the proliferation of redundant paths.

I don't understand how can graph-search be complete and tree-search be not, being a tree a particular graph.

Besides, I don't clearly understand the difference between "infinite loops" and "redundant paths"...

Can someone explain this to me?

ps. For those who have the book, it's page 86 (3rd edition).

Answer 1

It depends on the search space. If the search space of your algorithm is finite, then Depth-First Search is complete. However, if there are infinitely many alternatives, it might not find a solution. For example, suppose you were coding a path-search problem on city streets, and every time your partial path came to an intersection, you always searched the left-most street first. Then you might just keep going around the same block indefinitely.

Sometimes there are ways to bound the search to get completeness even when the search space is unbounded. For example, for the path-search problem above, if we prune the search whenever a path returns to a previous location on the path, then DFS will always find a solution if one exists.

There are variants of DFS that are complete. One is iterative deepening: you set a maximum search depth for DFS, and the only search that far down the search tree. If you don’t find a solution, then you increase the bound and try again. (Note, however, that this method might run forever if there is no solution.)

Now answering your second question, Basically, redundant links/paths are used to prevent nasty network failure. These are used to provide redundancy, i.e back up when a link fails, i.e a frame can be forwarded out through another path but it can cause problems also.

Whereas an infinite loop (sometimes called an endless loop ) is a piece of coding that lacks a functional exit so that it repeats indefinitely. In computer programming, a loop is a sequence of instruction s that is continually repeated until a certain condition is reached.

If you wish to know about Uninformed Search Algorithms and types of Uniformed Search Algorithms ( Breadth-first search, depth-first search, depth limited search, iterative deepening depth-first search, uniform cost search, bidirectional search ) then visit this Artificial Intelligence Course.