Iterative Deepening Search (IDS/IDDFS): A Comprehensive Guide

Explore Iterative Deepening Search (IDS), a powerful search algorithm combining the strengths of Depth-First Search (DFS) and Breadth-First Search (BFS). Learn how IDS avoids the pitfalls of infinite loops while guaranteeing completeness and optimality in finding solutions. Discover its applications in problem-solving, game playing, and pathfinding, and understand how its iterative deepening approach ensures efficient exploration of search spaces.

Iterative Deepening Search (IDS) or IDDFS: A Comprehensive Search Algorithm

Introduction

Search algorithms are fundamental in computer science and AI, used to solve various problems from game playing (chess, checkers) to pathfinding. Depth-First Search (DFS) is a popular algorithm, but it can get stuck in infinite loops if the graph contains cycles. Iterative Deepening Search (IDS) or Iterative Deepening Depth-First Search (IDDFS) addresses this issue.

What is IDS?

IDS combines the strengths of Depth-First Search (DFS) and Breadth-First Search (BFS). It explores the graph using DFS but gradually increases the search depth until the goal is found. Essentially, it repeatedly runs DFS with increasing depth limits.

This iterative approach ensures the search is both complete (finds a solution if one exists) and optimal (finds the shortest path to the goal).

IDS Pseudocode

Pseudocode

function iterativeDeepeningSearch(root, goal):
  depth = 0
  while True:
    result = depthLimitedSearch(root, goal, depth)
    if result == FOUND:
      return goal
    if result == NOT_FOUND:
      return None
    depth = depth + 1

function depthLimitedSearch(node, goal, depth):
  if node == goal:
    return FOUND
  if depth == 0:
    return NOT_FOUND
  for child in node.children:
    result = depthLimitedSearch(child, goal, depth - 1)
    if result == FOUND:
      return FOUND
  return NOT_FOUND

    

How IDS Works

iterativeDeepeningSearch repeatedly calls depthLimitedSearch, increasing the depth limit until the goal is found or the entire search space (up to the depth limit) is explored. depthLimitedSearch performs a depth-limited DFS.

IDS Python Implementation

Python Code

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def iddfs(self, start, goal, max_depth):
        for depth in range(max_depth + 1):
            visited = set()
            if self.dls(start, goal, depth, visited):
                return True
        return False

    def dls(self, node, goal, depth, visited):
        if node == goal:
            return True
        if depth == 0:
            return False
        visited.add(node)
        for neighbor in self.graph[node]:
            if neighbor not in visited:
                if self.dls(neighbor, goal, depth - 1, visited):
                    return True
        return False

# Example usage
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
start = 0
goal = 3
max_depth = 3
if g.iddfs(start, goal, max_depth):
    print("Path found")
else:
    print("Path not found")


    

Output


Path found

Advantages of IDS

Completeness: Guarantees finding a solution if one exists.
Memory Efficiency: Doesn't store the entire search space in memory, making it suitable for large graphs.
Works with Trees and Graphs: A general-purpose search algorithm.

Disadvantages of IDS

Revisited Nodes: May revisit some nodes multiple times, potentially slowing down the search (though techniques like caching can mitigate this).

Despite the potential for revisiting nodes, the completeness and optimality often outweigh this drawback. Techniques like caching can further improve efficiency.

Follow On

TutorialsArena