IDDFS combines depth-first search's space-efficiency and breadth-first search's completeness (when the branching factor is finite). It is optimal when the path cost is a non-decreasing function of the depth of the node.

Since iterative deepening visits states multiple times, it may seem wasteful, but it turns out to be not so costly, since in a tree most of the nodes are in the bottom level, so it does not matter much if the upper levels are visited multiple times.

It has exactly the same implementation as that of DLS. Additionally, iterations are required to increment the depth limit by one in every recursive call of DLS.

Implementation:

1. Initialize depth limit zero.

2. Repeat until the goal node is found.

a. Call Depth limited search with new depth limit.

b. Increment depth limit to next level.

Performance Evaluation:

Completeness: IDDFS is complete when the branching factor b is finite.

Optimality: It is optimal when path cost is non-decreasing function of the depth of the node.

Time complexity: The time complexity is O(bd).

Space complexity: Memory requirement of IDDFS are modes i.e. O(bd).