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).

Sclerodermatous

Answer 1

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.

Doubleteam

Even tree-search keeps track of the visited nodes (at least, from the root to the current node), thus I don't understand how can it get stuck in an infinite loop. Besides, I now understand the difference between "infinite loop" and "redundant path" (+1), but I don't think this is related with completeness since, even if the path is redundant, it will eventually find a goal node... – Sclerodermatous

Of course, if I do not check for repeated nodes I may get in an infinite loop. How can this be if I do check for repeated nodes? – Sclerodermatous

If you do check for repeated nodes (in a depth-first tree search), you won't get into an infinite loop. That's what your textbook is saying. – Doubleteam

So tree-search with occurrences check is actually complete? I think it's a little bit confusing that the book make a differentiation between graph-search and tree-search while it is enough to say "both are complete only with occurrences check". Seems he's pointing out a difference that does not exists... – Sclerodermatous

I looked carefully at page 86 of the book, and it really seems that it's saying what I think it's saying. Yes, it is confusing to put things in those terms. When the author refers to "depth-first tree search", the assumption seems to be that it does not check for repeated nodes. He seems to view the version which checks for repeated nodes as a special case. – Doubleteam

Talking with some guys at the university we get to the conclusion that, with "graph-search" and "tree-search" the authors are addressing the algorithms written at page 77 and they are not talking about depth-first applied to graph or tree; this means that "tree-search", for how it's defined, doesn't include occurrences check, thus it's not complete. However thanks for your help :) – Sclerodermatous

I think the reason why "tree-search" is defined to not include the repeated node check, is because this adds an extra O(log N) operation to each step of the search, making the algorithm O(N log N) rather than O(N)... and that's for a balanced tree. With a badly unbalanced tree, it could even become O(N^2). – Doubleteam

You are right, what the book said about the "proliferation of redundant paths" doesn't relate to completeness. I think it does. You can still get stuck in an infinite loop because you're still not keeping track of visited nodes (you're just making sure the path you're on is loop-free). This means you could explore some path a, then some path b, then again back to path a, then b and so on. – Daric

@PeeyushKushwaha That cannot happen infinitely in a correctly implemented tree search. – Doubleteam

@AlexD how so? In graph search DFS you usually prevent this from happening by storing nodes you have visited. Say x has children a and b and x, a is on the path you are currently exploring. When you backtrack to x then take b, then backtrack again to x, how do you know you're "done" exploring all children of x? – Daric

@PeeyushKushwaha The information stored on the stack must be enough to determine which children still need to be visited. For example, if the children of each node are stored in an array, typically the "current index" of the branch being explored would be stored on the stack. After backtracking, you would increment that index to get the next branch to explore. It would be nonsensical to implement a tree search in any other way. – Doubleteam

@Alex D, The last paragraph makes a mistake, if there are two branches from the root node to the same node, it means there is a circle in a tree! So this example is actually a graph search(with circle) example but not a tree search example. – Shigella

@debug, see the above comment by Manlio. He correctly states that when the book talks about "depth-first tree search", it is referring to a specific algorithm, regardless of whether that algorithm is applied to a graph or a tree. You may argue that the book's terminology is wrong; if so, please take it up with the author. In the context of this thread, the paragraph is correct as written. – Doubleteam

The check is not necessarily linear in time complexity as a hashset can be used – Duvall

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

Hoopes

Hi :), could you elaborate a bit more. – Junko

Hi, I try to explain in detail. Wish to help you. @Rishabh Kumar – Hoopes