Iterative Deepening Depth First Search (IDDFS)

Hello people! In this post we will talk about another search algorithm Iterative deepening depth first search (IDDFS) or Iterative deepening search (IDS). This algorithm is used when you have a goal directed agent in an infinite search space (or search tree).

Why do Breadth First Search (BFS) and Depth First Search (DFS) fail in the case of an infinite search space?

• In DFS, you would recursively look at a node’s adjacent vertex. DFS may not end in an infinite search space. Also, DFS may not find the shortest path to the goal. DFS needs O(d) space, where d is depth of search.
• BFS consumes too much memory. BFS needs to store all the elements in the same level. In the case of a tree, the last level has N / 2 leaf nodes, the second last level has N / 4. So, BFS needs O(N) space.

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.

Let us take an example to understand this –

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.

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 (DLS). As Depth Limited Search (DLS) is important for IDDFS, let us take time to understand it first.

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

A B E F C G D H

Can you do it for DEPTH = {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 –

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 –

IDDFS(tree):
    for depth = 0 to infinity:
        if (DLS(tree, depth)):
            return true

    return false

Before you race off to code, here are a few things –

• IDDFS is used to check if the goal is reachable from start node. So its return type is boolean.
• IDDFS is only used to check, not return the path from start node to goal. So we don’t maintain anything like parent array (like in DFS).
• IDDFS is meant to run DLS from 0 → ∞, but we will write our IDDFS program to run DLS from 0 → MAX_DEPTH. Because in real world we never run anything up to ∞.
• First code the DLS method, then add the IDDFS method which calls the DLS method.
• IDDFS is meant to run in an infinite space tree. So, you can use a binary tree if you want, but in my opinion using an N-ary tree makes more sense. So, in my code below I use N-ary tree, the code taken from my article on N-ary tree.

You should be capable of writing the code for Iterative deepening depth first search now. Try it, I’m sure you can 😉 You can refer to my code if you get stuck –

In the output, the tree is printed first, then the IDDFS traversals. Purposefully, I took the goal node as a node which is not reachable by depth = 3 but is reachable by depth = 4. As you have noticed from the output above, we visit the nodes at depth = 0 a lot, the nodes at depth = 2 a little fewer but we visit them multiple times too, and we visit the nodes at depth = DEPTH_MAX only once. This may seem inefficient, but it is actually not. This is because, there are very few nodes at depth = 0, but a lot of nodes at depth = DEPTH_MAX. If ‘d‘ is depth, and ‘b‘ is the branching factor in the search tree (this would be N for an N-ary tree), then mathematically –

The time complexity remains O(b^d) but the constants are large, so IDDFS is slower than BFS and DFS (which also have time complexity of O(b^d)).

Iterative deepening depth first search may not be directly used in practical applications but the technique of iteratively progressing your search in an infinite search space is pretty useful and can be applied in many AI applications.

Congrats, your AI just got better! Keep practicing! Happy coding! 😀