views:

383

answers:

2

I understand BFS, and DFS, but for the life of me cannot figure out the difference between iterative deepening and BFS. Apparently Iterative deepening has the same memory usage as DFS, but I am unable to see how this is possible, as it just keeps expanding like BFS. If anyone can clarify that would be awesome.

tree to work on if required:

    A
   / \
  B   C
 /   / \
D   E   F
+1  A: 

From What I understand iterative deepening does DFS down to depth 1 then does DFS doen to depth of 2 ... down to depth n , and so on till it finds no more levels

for exampe I think that tree would be read

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

I believe its pretty much doing a seperate DFS with depth limit for each level and throwing away the memory.

Roman A. Taycher
I agree with your analysis of how the algorithm works, but I believe "visit" means "operate on" in most algorithm books (and descriptions I've read online), which appears to be what you're using "read" to mean.
Steven Oxley
I'm thinking in terms of a recursive implementation with read being where you actually get the value and visit being whats on top of the stack.
Roman A. Taycher
Yeah, I understand what you're meaning, but I think that "visit" is the term that is usually used to mean when you actually get the value (or do some sort of operation on the node).
Steven Oxley
What do people usually use to refer to what I marked as read? and is there any popular alternative to using visited to get the value(it just sound wrong to me)?
Roman A. Taycher
+1  A: 

From my understanding of the algorithm, IDDFS (iterative-deepening depth-first search) is simply a depth-first search performed multiple times, deepening the level of nodes searched at each iteration. Therefore, the memory requirements are the same as depth-first search because the maximum depth iteration is just the full depth-first search.

Therefore, for the example of the tree you gave, the first iteration would visit node A, the second iteration would visit nodes A, B, and C, and the third iteration would visit all of the nodes of the tree.

The reason it is implemented like this is so that, if the search has a time constraint, then the algorithm will at least have some idea of what a "good scoring" node is if it reaches the time-limit before doing a full traversal of the tree.

This is different than a breadth-first search because at each iteration, the nodes are visited just like they would be in a depth-first search, not like in a breadth-first search. Typically, IDDFS algorithms would probably store the "best scoring" node found from each iteration.

Steven Oxley