# What is IDDFS search?

IDDFS (Iterative Deepening Depth-First Search) is a search algorithm used in computer science and artificial intelligence to find solutions in a tree-like structure. It combines the benefits of depth-first search (DFS) and breadth-first search (BFS) algorithms.

In simple terms, imagine you have a big tree with many branches and levels. Each level represents a step or decision that you can take. The tree could be a representation of a problem, where each branch represents a possible solution. The goal is to find the best solution or answer.

With IDDFS, you start by exploring the tree at the shallowest level (level 0) and perform a depth-first search, which means you go as deep as possible in one branch before exploring other branches. If you don't find the solution at that level, you come back to the root and start again, but this time you go one level deeper (level 1). You repeat this process, going deeper and deeper with each iteration until you find the solution or exhaust the entire tree.

The advantage of IDDFS is that it gradually explores the tree, level by level, just like BFS, ensuring that all nodes at a particular depth are visited before moving to the next depth. At the same time, it takes advantage of the memory efficiency of DFS, as it only keeps track of the current path being explored rather than the entire tree.

By combining the best aspects of both BFS and DFS, IDDFS provides an efficient way to search for solutions in large trees without consuming excessive memory. It's particularly useful when you have limited memory resources and need to find an optimal or near-optimal solution in a tree-like structure.

## Who invented it?

IDDFS was introduced by Richard E. Korf, a computer scientist and AI researcher, in 1985. Korf published a paper titled "Depth-First Iterative-Deepening: An Optimal Admissible Tree Search" in the Artificial Intelligence journal, where he presented the IDDFS algorithm. His work aimed to address the limitations of previous search algorithms and provide a more memory-efficient and optimal approach for searching large state spaces. Since then, IDDFS has become a widely used search algorithm in various fields of computer science and AI.

## Pseudocode

```
function IDDFS(root):
depth_limit = 0
solution = null
while solution is null:
visited = set()
solution = DLS(root, depth_limit, visited)
depth_limit += 1
return solution
function DLS(node, depth_limit, visited):
if node is goal:
return node
if depth_limit <= 0:
return null
visited.add(node)
for each child in node.children:
if child not in visited:
result = DLS(child, depth_limit - 1, visited)
if result is not null:
return result
return null
```

In this pseudocode, IDDFS is the main function that performs the iterative deepening depth-first search. It initializes the depth limit to 0 and the solution to null. It then enters a loop that continues until a solution is found. Within each iteration, it creates an empty set called visited to keep track of visited nodes. It calls the DLS (Depth-Limited Search) function, passing the root node, the current depth limit, and the visited set.

The DLS function is a recursive depth-limited search. It first checks if the current node is the goal state and returns it if true. Then, it checks if the depth limit has been reached, in which case it returns null. If not, it adds the current node to the visited set to avoid revisiting it.

Next, it iterates through each child of the current node. If a child has not been visited, it recursively calls DLS on that child with a decreased depth limit. If the result of the recursive call is not null (meaning a solution was found), it returns that solution. If no solution is found among the child nodes, it returns null.

The IDDFS function increases the depth limit by 1 in each iteration, ensuring that the search explores the tree gradually, level by level. Once a solution is found or the entire tree has been explored, the algorithm returns the solution.

The DLS function is a recursive depth-limited search. It first checks if the current node is the goal state and returns it if true. Then, it checks if the depth limit has been reached, in which case it returns null. If not, it adds the current node to the visited set to avoid revisiting it.

Next, it iterates through each child of the current node. If a child has not been visited, it recursively calls DLS on that child with a decreased depth limit. If the result of the recursive call is not null (meaning a solution was found), it returns that solution. If no solution is found among the child nodes, it returns null.

The IDDFS function increases the depth limit by 1 in each iteration, ensuring that the search explores the tree gradually, level by level. Once a solution is found or the entire tree has been explored, the algorithm returns the solution.

## Sample Code

```
// C++ code snippet
#include < iostream>
#include < vector>
#include < unordered_set>
using namespace std;
// Tree node structure
struct Node {
int data;
vector < Node*> children;
};
// Function to perform Depth-Limited Search (DLS)
Node* DLS(Node* node, int depthLimit, unordered_set < Node*>& visited) {
if (node == nullptr)
return nullptr;
visited.insert(node);
if (node->data == /*goal value*/)
return node;
if (depthLimit <= 0)
return nullptr;
for (Node* child : node->children) {
if (visited.find(child) == visited.end()) {
Node* result = DLS(child, depthLimit - 1, visited);
if (result != nullptr)
return result;
}
}
return nullptr;
}
// Function to perform Iterative Deepening Depth-First Search (IDDFS)
Node* IDDFS(Node* root, int maxDepth) {
for (int depthLimit = 0; depthLimit <= maxDepth; depthLimit++) {
unordered_set < Node*> visited;
Node* result = DLS(root, depthLimit, visited);
if (result != nullptr)
return result;
}
return nullptr;
}
int main() {
// Create your tree structure
Node* root = new Node();
root->data = /*root value*/;
// Perform IDDFS
Node* solution = IDDFS(root, /*maximum depth*/);
// Process the solution
if (solution != nullptr) {
cout << "Solution found!" << endl;
// Additional processing of the solution
} else {
cout << "No solution found." << endl;
}
// Clean up memory (if needed)
// ...
return 0;
}
```

```
# Python code snippet
class Node:
def __init__(self, data):
self.data = data
self.children = []
def DLS(node, depth_limit, visited):
if node is None:
return None
visited.add(node)
if node.data == /*goal value*/:
return node
if depth_limit <= 0:
return None
for child in node.children:
if child not in visited:
result = DLS(child, depth_limit - 1, visited)
if result is not None:
return result
return None
def IDDFS(root, max_depth):
for depth_limit in range(max_depth + 1):
visited = set()
result = DLS(root, depth_limit, visited)
if result is not None:
return result
return None
# Create your tree structure
root = Node(/*root value*/)
# Build your tree by adding nodes and connecting them appropriately
# Perform IDDFS
solution = IDDFS(root, /*maximum depth*/)
# Process the solution
if solution is not None:
print("Solution found!")
# Additional processing of the solution
else:
print("No solution found.")
```

```
import java.util.HashSet;
import java.util.Set;
class Node {
int data;
Set
``` children;
public Node(int data) {
this.data = data;
children = new HashSet<>();
}
}
public class IDDFS {
public static Node DLS(Node node, int depthLimit, Set visited) {
if (node == null)
return null;
visited.add(node);
if (node.data == /*goal value*/)
return node;
if (depthLimit <= 0)
return null;
for (Node child : node.children) {
if (!visited.contains(child)) {
Node result = DLS(child, depthLimit - 1, visited);
if (result != null)
return result;
}
}
return null;
}
public static Node IDDFS(Node root, int maxDepth) {
for (int depthLimit = 0; depthLimit <= maxDepth; depthLimit++) {
Set visited = new HashSet<>();
Node result = DLS(root, depthLimit, visited);
if (result != null)
return result;
}
return null;
}
public static void main(String[] args) {
// Create your tree structure
Node root = new Node(/*root value*/);
// Build your tree by adding nodes and connecting them appropriately
// Perform IDDFS
Node solution = IDDFS(root, /*maximum depth*/);
// Process the solution
if (solution != null) {
System.out.println("Solution found!");
// Additional processing of the solution
} else {
System.out.println("No solution found.");
}
}
}

## Time and Space Complexity

**Time Complexity:**

The time complexity of IDDFS can be expressed as O(b^d), where "b" is the average branching factor of the search tree and "d" is the depth limit. This is because IDDFS performs a depth-first search up to a certain depth limit, and in the worst case, it needs to explore all paths up to that limit.

Since IDDFS incrementally increases the depth limit, the time complexity can be further refined as follows: O(b^0) + O(b^1) + O(b^2) + ... + O(b^d). Simplifying this expression gives O(b^d) as the overall time complexity.

**Space Complexity:**

The space complexity of IDDFS depends on the maximum depth limit reached during the search. At any given depth limit, the space complexity is O(d) because it needs to store the current path being explored. However, since IDDFS explores the search space iteratively, it only needs to keep track of the current path and does not store the entire tree. Therefore, the space complexity of IDDFS can be considered O(d), where "d" is the maximum depth limit reached.

## Advantages

1. Optimal Solutions: IDDFS guarantees finding the optimal solution if one exists. By gradually increasing the depth limit, it explores the search space in a depth-first manner while ensuring that all nodes within a particular depth are visited before moving deeper. This allows it to find the optimal solution if it exists at a shallower depth.

2. Memory Efficiency: IDDFS utilizes memory more efficiently compared to other search algorithms like breadth-first search. It only needs to store the current path being explored, rather than the entire search tree. This makes it feasible to use IDDFS in scenarios where memory resources are limited.

3. Incremental Progress: IDDFS provides incremental progress. It starts searching at a shallow depth, making it possible to find solutions at lower depths faster. This is useful when the solution space is large, as it can provide initial results while continuing the search for better solutions with increased depth limits

2. Memory Efficiency: IDDFS utilizes memory more efficiently compared to other search algorithms like breadth-first search. It only needs to store the current path being explored, rather than the entire search tree. This makes it feasible to use IDDFS in scenarios where memory resources are limited.

3. Incremental Progress: IDDFS provides incremental progress. It starts searching at a shallow depth, making it possible to find solutions at lower depths faster. This is useful when the solution space is large, as it can provide initial results while continuing the search for better solutions with increased depth limits

## Disadvantages

1. Redundant Work: IDDFS performs redundant work by revisiting nodes at different depths. This can be inefficient, especially if the branching factor is high or there are many repeated states in the search space. However, the redundancy is often outweighed by the benefits of optimality and memory efficiency in certain scenarios.

2. Time Complexity: The time complexity of IDDFS is generally higher compared to other algorithms like BFS or A*. As the depth limit increases, the search space expands exponentially, leading to longer execution times. Therefore, IDDFS may not be suitable for search spaces with extremely large depths.

3. Lack of Heuristics: IDDFS does not incorporate any heuristics or domain-specific knowledge. It treats all branches equally and explores the search space uniformly. While this can be advantageous in some cases, it may not be as efficient as algorithms that utilize heuristics to guide the search towards promising paths.

In summary, IDDFS is a trade-off between optimality and memory efficiency. It guarantees optimal solutions but may require more time compared to other algorithms. It is memory-efficient but may perform redundant work. Its suitability depends on the specific problem, the size of the search space, available memory resources, and the importance of finding the optimal solution.

2. Time Complexity: The time complexity of IDDFS is generally higher compared to other algorithms like BFS or A*. As the depth limit increases, the search space expands exponentially, leading to longer execution times. Therefore, IDDFS may not be suitable for search spaces with extremely large depths.

3. Lack of Heuristics: IDDFS does not incorporate any heuristics or domain-specific knowledge. It treats all branches equally and explores the search space uniformly. While this can be advantageous in some cases, it may not be as efficient as algorithms that utilize heuristics to guide the search towards promising paths.

In summary, IDDFS is a trade-off between optimality and memory efficiency. It guarantees optimal solutions but may require more time compared to other algorithms. It is memory-efficient but may perform redundant work. Its suitability depends on the specific problem, the size of the search space, available memory resources, and the importance of finding the optimal solution.