Iterative Deepening is a graph search algorithm that combines the benefits of both breadth-first search (BFS) and depth-first search (DFS) algorithms. It is particularly useful when the search space is large and the depth of the solution is not known in advance.

The main idea behind Iterative Deepening is to repeatedly perform DFS with an increasing depth limit. It starts with a depth limit of 0 and gradually increases the limit until a solution is found. This allows the algorithm to perform a depth-first search in a controlled manner, avoiding the drawbacks of a traditional unbounded DFS.

Here’s a step-by-step explanation of how Iterative Deepening works:

1. Set the initial depth limit to 0.
2. Perform a depth-limited search (DFS) with the current depth limit.

2. Start the DFS from the source vertex or node.
3. Explore the graph by recursively visiting adjacent vertices up to the current depth limit.
4. If the solution is found during the search, return it.

3. If the solution is not found at the current depth limit, increment the depth limit by 1.
4. Repeat steps 2 and 3 until a solution is found or a termination condition is met (e.g., reaching a predefined maximum depth).
5. Return the solution if found; otherwise, indicate that no solution exists.

Iterative Deepening guarantees that all nodes within a certain depth limit are explored before moving to the next depth level. It provides a balance between BFS and DFS by avoiding the memory overhead of BFS and the risk of getting stuck in an infinite path of DFS.

One key advantage of Iterative Deepening is that it finds the optimal solution, assuming the path cost is non-decreasing with depth. It explores the search space in a way that ensures the shortest path is found.

The time complexity of Iterative Deepening is similar to DFS, which is O(b^d), where b is the branching factor and d is the depth of the solution. However, the repeated depth-limited searches can result in redundant exploration of nodes, making it less efficient than some other search algorithms in certain cases.

Iterative Deepening Search (IDS) or Iterative Deepening Depth First Search (IDDFS)

An integral component of computer science and artificial intelligence are search algorithms. They are used to solve a variety of issues, from playing games like chess and checkers to locating the shortest route on a map. The Depth First Search (DFS) method, one of the most popular search algorithms, searches a network or tree by travelling as far as possible along each branch before turning around. However, DFS has a critical drawback: if the graph contains cycles, it could become trapped in an endless loop. Utilizing Iterative Deepening Search (IDS) or Iterative Deepening Depth First Search is one technique to solve this issue (IDDFS).

What is IDS?

A search algorithm known as IDS combines the benefits of DFS with Breadth First Search (BFS). The graph is explored using DFS, but the depth limit steadily increased until the target is located. In other words, IDS continually runs DFS, raising the depth limit each time, until the desired result is obtained. Iterative deepening is a method that makes sure the search is thorough (i.e., it discovers a solution if one exists) and efficient (i.e., it finds the shortest path to the goal).

The pseudocode for IDS is straightforward:

1. function iterativeDeepeningSearch(root, goal):  
2.     depth = 0  
3.     while True:  
4.         result = depthLimitedSearch(root, goal, depth)  
5.         if result == FOUND:  
6.             return goal  
7.         if result == NOT_FOUND:  
8.             return None  
9.         depthdepth = depth + 1  
10.   
11. function depthLimitedSearch(node, goal, depth):  
12.     if node == goal:  
13.         return FOUND  
14.     if depth == 0:  
15.         return NOT_FOUND  
16.     for child in node.children:  
17.         result = depthLimitedSearch(child, goal, depth – 1)  
18.         if result == FOUND:  
19.             return FOUND  
20.     return NOT_FOUND  

How does IDS work?

The iterativeDeepeningSearch function performs iterative deepening search on the graph using a root node and a goal node as inputs until the goal is attained or the search space is used up. This is accomplished by regularly using the depthLimitedSearch function, which applies a depth restriction to DFS. The search ends and returns the goal node if the goal is located at any depth. The search yields None if the search space is used up (all nodes up to the depth limit have been investigated).

The depthLimitedSearch function conducts DFS on the graph with the specified depth limit by taking as inputs a node, a destination node, and a depth limit. The search returns FOUND if the desired node is located at the current depth. The search returns NOT FOUND if the depth limit is reached but the goal node cannot be located. If neither criterion is true, the search iteratively moves on to the node’s offspring.

Program:

Code

1. from collections import defaultdict  
2.   
3. class Graph:  
4.     def __init__(self):  
5.         self.graph = defaultdict(list)  
6.   
7.     def add_edge(self, u, v):  
8.         self.graph[u].append(v)  
9.   
10.     def iddfs(self, start, goal, max_depth):  
11.         for depth in range(max_depth+1):  
12.             visited = set()  
13.             if self.dls(start, goal, depth, visited):  
14.                 return True  
15.         return False  
16.   
17.     def dls(self, node, goal, depth, visited):  
18.         if node == goal:  
19.             return True  
20.         if depth == 0:  
21.             return False  
22.         visited.add(node)  
23.         for neighbor in self.graph[node]:  
24.             if neighbor not in visited:  
25.                 if self.dls(neighbor, goal, depth-1, visited):  
26.                     return True  
27.         return False  
28.   
29. # Example usage  
30. g = Graph()  
31. g.add_edge(0, 1)  
32. g.add_edge(0, 2)  
33. g.add_edge(1, 2)  
34. g.add_edge(2, 0)  
35. g.add_edge(2, 3)  
36. g.add_edge(3, 3)  
37.   
38. start = 0  
39. goal = 3  
40. max_depth = 3  
41. if g.iddfs(start, goal, max_depth):  
42.     print(“Path found”)  
43. else:  
44.     print(“Path not found”)  

Output

Path found

Advantages

• IDS is superior to other search algorithms in a number of ways. The first benefit is that it is comprehensive, which ensures that a solution will be found if one is there in the search space. This is so that all nodes under a specific depth limit are investigated before the depth limit is raised by IDS, which does a depth-limited DFS.
• IDS is memory-efficient, which is its second benefit. This is because IDS decreases the algorithm’s memory needs by not storing every node in the search area in memory. IDS minimises the algorithm’s memory footprint by only storing the nodes up to the current depth limit.
• IDS’s ability to be utilised for both tree and graph search is its third benefit. This is due to the fact that IDS is a generic search algorithm that works on any search space, including a tree or a graph.

Disadvantages

• IDS has the disadvantage of potentially visiting certain nodes more than once, which might slow down the search. The benefits of completeness and optimality frequently exceed this disadvantage. In addition, by employing strategies like memory or caching, the repeated trips can be minimised.