When should the iterative deepening search and the depth-limited search be used?

Question

When should the iterative deepening search (IDS), also called iterative deepening depth-first search (IDDFS), and the depth-limited search be used?

Answer 1

If your search tree's branching factor is finite but its depth is unbounded, then DFS isn't "complete". What that means is that it may not ever find the goal node even if it exists. You would use these techniques precisely when this situation arises.

To understand this, let's say you're at the node A in the following tree:

     A
    / \
   /   \
  B     C
 / \   / \
.   . .   .

You choose to explore subtree rooted at B. Now if there are no goal nodes in that subtree, but the goal nodes were in the subtree rooted at C, then we're stuck. Because we will keep searching there because we don't know beforehand that there are no goal nodes there, next node we explore could always be a goal node. But this essentially means that we'll never finish searching the subtree rooted at B in finite time, and never backtrack to explore the subtree rooted at C.

So to overcome this you would want to iterative deepening depth-first search or depth-limited search.

In depth-limited search you set a limit on the depth you'll explore. Let's say you choose $d$ as the depth limit because you know that the solution lies within that depth limit.

And let's say the branching factor for your tree is $b$. Going back to our example, you have finite elements in the subtree rooted at B (at most $b^d$, can you reason why?), so we'll be able to look at all of them and eventually backtrack and start exploring subtree rooted at C, and we'll be able to find our answer.

Now if you don't know the depth $d$ which goal nodes lie at, then you'll use iterative deepening DFS, which essentially does depth limited search but keeps increasing the value of $d$ on each iteration, so you're guaranteed to find a goal node, if it exists.

Answer 2

In practice, you can consider that IDS is a cheap way to implement a breadth-first search (BFS).

When the branching factor is high, both algorithms have similar computational costs $O(B^P)$, where $P$ is the length of the solution path and $B$ the branching factor, but IDS requires less memory, typically $O(P)$, while BFS uses $O(B^P)$.