# Iterative Deepening Search

Published
 Completeness - Complete if the branching factor is finite. Optimality - Optimal if the costs of all actions are equal. Time Complexity - O(bd) Space Complexity - O(b × d)

## Visual Example level Current Node Frontier
1 A
2 A B, C
2 B C
2 C
3 A B, C
3 B D, E, C
3 D E, C
3 E C
3 C F, G
3 F G
Goal Node Found
1. Run algorithm, with level = 1.
1. We start from the root node A.
2. We check to see if A is a goal node. It's not, so we continue.
3. There are no more nodes, so we increase the level and re-run the algorithm.
2. Run the algorithm, with level = 2.
1. We start from the root node A.
2. We check to see if A is a goal node. It's not, so we add it's children, nodes B and C, to the frontier.
3. We check to see if B is a goal node. It's not, so we continue.
4. We check to see if C is a goal node. It's not, so we continue.
5. There are no more nodes, so we increase the level and re-run the algorithm.
3. Run the algorithm, with level = 3.
1. We start from the root node A.
2. We check to see if A is a goal node. It's not, so we add it's children, nodes B and C, to the frontier.
3. We remove node B from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes D and E, to the frontier.
4. We remove node D from the frontier, we check if it's a goal node. It's not, so we continue.
5. We remove node E from the frontier, we check if it's a goal node. It's not, so we continue.
6. We remove node C from the frontier, we check if it's a goal node. It's not, so we add it's children, nodes F and G, to the frontier.
7. We remove node F from the frontier, we check if it's a goal node. It is, so we're done.
Nodes H, I, J, and K are never visited because our level value never reaches 4.

## Algorithm Notes

• Abbreviated as IDS.
• IDS is DLS, but it differs from DLS in that IDS increases the level and re-runs the algorithm every time it fails to find a goal node.
• This is generally the preferred uninformed search method if the search space is large and the depth (level) of the goal is unknown.
• The main disadvantage of IDS is that some nodes are visited many times. However, this is not usually an issue.