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.");
}
}
}