[Solved]: IDDFS explained

Problem Detail: 

I am trying to understand how IDDFS works by reading a wikipedia article on it. (If someone has a better literature on the subject, don't hesitate to post). Pseudocode is as follows:

IDDFS(root, goal) {   depth = 0   for(i=1, i<10, i++)   {     DFS(limit=i)   } } 

First of all, what is 10 here? Is it an arbitray number we choose? What is the connection between depth and "10"?

In the graph given as an example in that wikipedia article, in step 2 vistied nodes are:
2: A, B, D, F, C, G, E, F

Why is node F visited twice? Doesn't a DFS keep track of already visited nodes?

I am totally confused on this issue and any help is greatly appreciated.

Asked By : Maggie

Answered By : David Richerby

10 is indeed an arbitrary constant, which you would choose appropriate to your application. In fact, you might not choose it: in a chess program, for example, you'd be likely to decide how much time you want to give to the current position and then just search deeper and deeper until you've used up that time.

As is hinted below the diagram in the Wikipedia page, iterative deepening doesn't generally keep track of which nodes have been visited. You tend to use it for huge trees that aren't actually held in memory – going back to the chess example, you have a typical branching factor of 30-40 and you might want to search interesting lines down to depth 15-20. There's no way you can keep all of that in memory so, no, you can't remember which nodes have been visited. In DFS, you need to keep track of visited nodes so you don't end up in infinite loops when the graph contains cycles; with iterative deepening, the depth cut-off already avoids infinite loops. You trade the time wasted going round loops for the space saved by not storing the visited nodes. (Actually, in our running chess example, you'd typically have a hash table of positions that have already been seen. If the hash table already contains a sufficiently good evaluation of the current node, you use that, rather than exploring the tree more.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19032