Iterative deepening depth-first search (IDS)

Iterative deepening depth-first search (IDS)

• Description:
  • It is a search strategy resulting when you combine BFS and DFS, thus combining the advantages of each strategy, taking the completeness and optimality of BFS and the modest memory requirements of DFS.
  • IDS works by looking for the best search depth d, thus starting with depth limit 0 and make a BFS and if the search failed it increase the depth limit by 1 and try a BFS again with depth 1 and so on – first d = 0, then 1 then 2 and so on – until a depth d is reached where a goal is found.
• Performance Measure:
  • Completeness:
    • IDS is like BFS, is complete when the branching factor b is finite.
  • Optimality:
    • IDS is also like BFS optimal when the steps are of the same cost.
  • Time Complexity:
    • One may find that it is wasteful to generate nodes multiple times, but actually it is not that costly compared to BFS, that is because most of the generated nodes are always in the deepest level reached, consider that we are searching a binary tree and our depth limit reached 4, the nodes generated in last level = 2⁴ = 16, the nodes generated in all nodes before last level = 2⁰ + 2¹ + 2² + 2³= 15
    • Imagine this scenario, we are performing IDS and the depth limit reached depth d, now if you remember the way IDS expands nodes, you can see that nodes at depth d are generated once, nodes at depth d-1 are generated 2 times, nodes at depth d-2 are generated 3 times and so on, until you reach depth 1 which is generated d times, we can view the total number of generated nodes in the worst case as:
      • N(IDS) = (b)d + (d – 1)b² + (d – 2)b³ + …. + (2)b^d-1 + (1)b^d = O(b^d)
    • If this search were to be done with BFS, the total number of generated nodes in the worst case will be like:
      • N(BFS) = b + b² + b³ + b⁴ + …. b^d + (b^{d + 1} – b) = O(b^{d + 1})
    • If we consider a realistic numbers, and use b = 10 and d = 5, then number of generated nodes in BFS and IDS will be like
      • N(IDS) = 50 + 400 + 3000 + 20000 + 100000 = 123450
      • N(BFS) = 10 + 100 + 1000 + 10000 + 100000 + 999990 = 1111100
      • BFS generates like 9 time nodes to those generated with IDS.
  • Space Complexity:
    • IDS is like DFS in its space complexity, taking O(bd) of memory.
• Conclusion:
  • We can conclude that IDS is a hybrid search strategy between BFS and DFS inheriting their advantages.
  • IDS is faster than BFS and DFS.
  • It is said that “IDS is the preferred uniformed search method when there is a large search space and the depth of the solution is not known”.