Search code examples
artificial-intelligencedepth-first-searchbreadth-first-searchiterative-deepening

How to apply Iterative Deepening Depth First Search(IDDFS) on Graphs

enter image description here

I tried to apply IDDFS on this graph by first making it in tree form and the result was this :

 At level 1: d,e,p
 At level 2: d,b,e,c,e,h,r,p,q
 At level 3: d,b,a,e,h,c,a,e,h,q,p,r,f,p,q
 At level 4: d,b,a,e,h,p,q,c,a,e,h,q,p,q,r,f,c,GOAL

I am confused about those repeated nodes in the path, can we eliminate them or they will appear in the final path ?

Is this the correct approach of traversing the graph to reach the GOAL ? And how we come to know which node to visit next in graph(e.g as in tree we start from left to right).

And what would be the path if we apply DFS and BFS on same graph ?

Will there be any difference in DFS result and IDDFS ? It seems to be similar

Solution

    1. Yes, you can and SHOULD get rid of repeated nodes when you implement DFS, by keeping track of which nodes you've already visited. If you don't, your code won't terminate when it finds a cycle. Don't forget to clear the set of visited nodes with each new level. So leave out the visited nodes from your listing, unless it's important to include nodes that are being considered but not re-visited.

    2. If you write out the expansion for BFS and DFS, you'll see that IDDFS starts out looking like BFS and ends up looking more and more like DFS the more you crank up the level. When level = length-of-longest-path, voila, you get DFS, which is not surprising, since IDDFS is DFS, only with paths cut off at a given number; in that particular case, the number has no effect, because there aren't any paths long enough to be cut off.

    3. The order in a graph is not well defined. You choose one order or another yourself. If you choose a next node at random, you get non-deterministic algorithms. If you choose them, dunno, alphabetically, then you get some determinism. Sometimes the distinction doesn't matter, but determinism is good for debugging your code, etc. Now, when you do this exercise, you do it to see patterns, so it's best to leave out the randomness.

    Your question really does look like homework. ;)