Iterative Deepening Search (IDS) or Iterative Deepening Depth First Search (IDDFS)

BFS and DFS are the two most prevalent strategies to traverse a graph. Both BFS and DFS are inefficient when dealing with a Tree (or Graph) of enormous height and width for the following reasons.

1. DFS explores nodes in this order: one near to the root, then the next adjacent. The difficulty with this method is that if a node is near to the root but not in the first few subtrees searched by DFS, DFS will get at that node late. DFS may also fail to discover the shortest path to a node (in terms of a number of edges).

2. BFS progresses level by level, but it takes up more room. DFS requires O(d) space, where d is the depth of the tree, but BFS requires O(n) space, where n is the number of nodes in the tree (Why?). Note that the last level of the tree can have approximately n/2 nodes, and the second last level can have around n/4 nodes, and in BFS, we must queue each level one by one).

IDDFS combines the space-efficiency of depth-first search with the speed of breadth-first search (for nodes closer to root).

What is IDDFS?

Starting with an initial value, IDDFS calls DFS for various depths. DFS is not allowed to go beyond a certain depth in any call. So, in a nutshell, we do DFS in a BFS manner.

It's worth noting that we go to top-level nodes many times. The final (or maximum depth) level is visited once, twice for the second last level, and so on. It may appear to be costly, but it turns out to be less so because the majority of nodes in a tree are found at the bottom level. As a result, it doesn't matter if the top levels are visited several times.

How does IDDFS work?

IDDFS calls DFS for different depths starting from an initial value. In every call, DFS is restricted from going beyond the given depth. So basically we do DFS in a BFS fashion.

Algorithm:

// Returns true if target is reachable from
// src within max_depth
bool IDDFS(src, target, max_depth)
for limit from 0 to max_depth
if DLS(src, target, limit) == true
return true
return false

bool DLS(src, target, limit)
if (src == target)
return true;

// If reached the maximum depth,
// stop recursing.
if (limit <= 0)
return false;

foreach adjacent i of src
if DLS(i, target, limit?1)
return true

return false

Advantages and Disadvantages of IDDFS

Advantages

• If the solution exists in the tree, IDDFS provides us hope of finding it.
• When solutions are found at lesser depths, say n, the approach shows to be efficient and time-efficient.
• IDDFS has a significant benefit in in-game tree searching, where the search operation strives to enhance the depth definition, heuristics, and scores of searching nodes in order to increase the search algorithm's efficiency.
• Another significant benefit of the IDDFS algorithm is its speed. The algorithm's early results signals are a good point. Following that, several modifications were made once each cycle was finished.
• Despite the fact that there is more work to be done here, IDDFS outperforms single BFS and DFS operations.
• The difficulties of space and time are stated as O(d), where d is the target depth.
• Let's have a look at how long IDDFS takes to run. Let's assume b>l, with b being the branching factor and l denoting the depth limit. Then we look for the desired node inside the bound k. We suggest that there may be bknodes that are only created once at depth k. Similarly, the nodes at the k-1 depth limit are twice as many as those at the k-2 depth limit. As a result, the node created at depth l is k times larger than the node generated at depth l.

Disadvantages

• The time it takes to reach the goal node is exponential.
• The main issue with IDDFS is the amount of time and calculations wasted at each depth.
• When the branching factor is determined to be large, the situation is not as awful as we may imagine.
• When the BFS fails, the IDDFS may also fail. When we use the IDDFS to find multiple answers, it only returns the success nodes and their paths once, even if they must be found again after multiple iterations. To prevent the depth bound from being extended any further.

Conclusion

The iterative deepening depth-first search algorithm is a mix of BFS and DFS. Although IDDFS isn't directly utilised in many computer science applications, it is used to search for data in infinite space by incrementally increasing the depth limit. This is quite valuable, as it has applications in AI and the rapidly growing data sciences business.

Author : Dwayne Smith

University : University of Michigan

Designation : Computer Science Professor and Programming Assignment Examiner