Iterative deepening depth first search (IDDFS) is a hybrid of BFS and DFS. In IDDFS, we perform DFS up to a certain “limited depth,” and keep increasing this “limited depth” after every iteration.<\/p>\n
Let us take an example to understand this –<\/p>\n
As stated earlier, in IDDFS, we perform DFS up to a certain depth and keep incrementing this allowed depth. Performing DFS upto a certain allowed depth is called Depth Limited Search<\/strong> (DLS). As Depth Limited Search (DLS) is important for IDDFS, let us take time to understand it first.<\/p>\n Let us understand DLS, by performing DLS on the above example. In Depth Limited Search, we first set a constraint on how deep (or how far from root) will we go. Let’s say our limit (DEPTH<\/em>) is 2. Now, in the above diagram, place your hand to cover the nodes at depth 3 and 4. Now, by looking at the rest of the nodes, can you tell the order in which a normal DFS would visit them? It would be as follows –<\/p>\n Can you do it for DEPTH<\/em> = {0, 1, 2, 3, 4} ? Just cover the nodes you don’t need with your hand and try to perform DFS in you mind. You should get answers like this –<\/p>\n Now that you have got an idea of Depth Limited Search, Iterative deepening depth first search is just one loop away! The pseudo-code for IDDFS is as below –<\/p>\n Before you race off to code, here are a few things –<\/p>\n You should be capable of writing the code for Iterative deepening depth first search now. Try it, I’m sure you can \ud83d\ude09 You can refer to my code if you get stuck –<\/p>\n![\"\"](\"https:\/\/i0.wp.com\/theoryofcoding.com\/wp-content\/uploads\/2018\/01\/iddfs-1-1.jpg?ssl=1\")
<\/a>Our starting node (A) is at a depth of 0. Our goal node (R) is at a depth of 4. The above example is a finite tree, but think of the above tree as an infinitely long tree and only up to depth = 4 is shown in the diagram.<\/p>\n\nA B E F C G D H\n<\/pre>\n
\n\n
\n DEPTH<\/em><\/td>\n DLS traversal<\/td>\n<\/tr>\n \n 0<\/td>\n A<\/td>\n<\/tr>\n \n 1<\/td>\n A B C D<\/td>\n<\/tr>\n \n 2<\/td>\n A B E F C G D H<\/td>\n<\/tr>\n \n 3<\/td>\n A B E I F J K C G L D H M N<\/td>\n<\/tr>\n \n 4<\/td>\n A B E I F J K O P C G L R D H M N S<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n \nIDDFS(tree):\n for depth = 0 to infinity:\n if (DLS(tree, depth)):\n return true\n\n return false\n<\/pre>\n
\n