Completeness of depth-first search

Question

I quote from Artificial Intelligence: A Modern Approach:

The properties of 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 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 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 get the difference between "infinite loops" and "redundant paths"...

May someone explain this to me?

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

Answer 1

The main difference is between the Tree search and graph Search:

In case of Tree Search every possible path is explored separately, even if two paths lead to the same place. Which can lead to infinite loops or redundant paths. As it doesn’t track visited nodes, so it can keep exploring the same states multiple times. e.g: Loop infinitely in cycles (e.g., A → B → A → B → ...). Explore redundant paths (e.g., Path 1: A → B → C and Path 2: A → D → B → C).

While in Graph Search , it keeps track of visited nodes (explored set) to avoid revisiting them. Handling cycles and redundant paths.

Example: Redundant Path Elimination Imagine searching for a path from A to G in this graph

    A  
   / \  
  B   C  
  \ /  
   D  
   |  
   G 

Possible paths: A → B → D → G and A → C → D → G.

Graph search will:

• Expand A, generating B and C.
• Suppose it expands B first, generating D and adding D to the frontier.
• When expanding C, it generates D again, but discards it because D is already in the frontier or explored set.

Only one path to G is explored: A → B → D → G.

Answer 2

DFS is incomplete(in tree-search). However, if you keep track of visited nodes, it turns to be complete(in graph search).

1. let's be clear about what completeness means.

If an algorithm is complete, it means that if at least one solution exists then the algorithm is guaranteed to find a solution in a finite amount of time.

2. We need to distinguish between tree-search and graph-search. As shown in section 3.3 or page 77 in Artificial Intelligence: A Modern Approach, the only difference is that graph-search has a set to store the explored nodes.

3. Finally, we can figure out the answer.

• In tree-search(not store explored nodes), since we don't know whether the current node is explored or not, DFS may explore it again(and again...), which will loop forever. -> Infinite time, not complete
• In graph-search(store explored nodes), any search algorithms will end. -> Finite time, complete

Answer 3

Depth-first tree search can get stuck in an infinite loop, which is why it is not "complete". Graph search keeps track of the nodes it has already searched, so it can avoid following infinite loops.

"Redundant paths" are different paths which lead from the same start node to the same end node. Graph search will still explore all these redundant paths, but once it reaches a node which it has visited before, it will not go any further, but will back up and look for more paths which it hasn't tried yet.

This is different from an "infinite loop" which is a path which leads from a node back to itself.

In response to your comment, look at the quote which you just posted:

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.

So while depth-first tree search does keep track of the path from the root to the current node, to avoid infinite loops, it needs to do a linear search over that path each time it visits a new node. If you wrote an implementation of depth-first tree search which didn't do that check, it could get into an infinite loop.

You are right, what the book said about the "proliferation of redundant paths" doesn't relate to completeness. It is just pointing out a difference between graph and tree search. Because tree search just keeps track of the current path, it can run over the same path more than once in the same search (even if doing the check I just mentioned).

Say your root node has 2 branches. Each of those branches leads to the same single node, which has a long path leading out from it. Tree search will follow that long path twice, once for each of the 2 branches which leads to it. That is what the author is pointing out.