July 25, 2022
What is ID-DFS Algorithm (Iterative deepening depth first Search)?
- The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search algorithm finds out the best depth limit and does it by gradually increasing the limit until a goal is found.
- This algorithm performs depth-first search up to a certain "depth limit", and it keeps increasing the depth limit after each iteration until the goal node is found.
- This Search algorithm combines the benefits of Breadth-first search's fast search and depth-first search's memory efficiency.
- The iterative search algorithm is useful uninformed search when search space is large, and depth of goal node is unknown.
Why do we need ID-DFS Algorithm?
- As a general rule of thumb, we use iterative deepening when we do not know the depth of our solution and have to search a very large state space.
- Iterative deepening may also be used as a slightly slower substitute for BFS if we are constrained by memory or space.
The architecture of ID-DFS algorithm
Algorithm of ID-DFS:
- Consider making a breadth-first search into an iterative deepening search.
- We can do this by having aside a DFS which will search up to a limit. It first does searching to a pre-defined limit depth to depth and then generates a route length1.
- This is done by creating routes of length 1 in the DFS way. Next, it makes way for routes of depth limit 2, 3 and onwards.
- It even can delete all the preceding calculation all-time at the beginning of the loop and iterate. Hence at some depth eventually the solution will be found if there is any in the tree because the enumeration takes place in order.
ID-DFS – Example
Implementation:
Here in the given tree, the starting node is A and the depth initialized to 0. The goal node is R where we have to find the depth and the path to reach it. The depth from the figure is 4. In this example, we consider the tree as a finite tree, while we can consider the same procedure for the infinite tree as well. We knew that in the algorithm of IDDFS we first do DFS till a specified depth and then increase the depth at each loop. This special step forms the part of DLS or Depth Limited Search. Thus the following traversal shows the IDDFS search.
Advantages of ID-DFS:
- It combines the benefits of BFS and DFS search algorithm in terms of fast search and memory efficiency.
- IDDFS gives us the hope to find the solution if it exists in the tree.
- When the solutions are found at the lower depths say n, then the algorithm proves to be efficient and in time.
- The great advantage of IDDFS is found in-game tree searching where the IDDFS search operation tries to improve the depth definition, heuristics, and scores of searching nodes so as to enable efficiency in the search algorithm.
- Another major advantage of the IDDFS algorithm is its quick responsiveness. The early results indications are a plus point in this algorithm. This followed up with multiple refinements after the individual iteration is completed.
- Though the work is done here is more yet the performance of IDDFS is better than single BFS and DFS operating exclusively.
- Space and time complexities are expressed as: O(d) and here d is defined as goal depth.
- Let us consider the run time of IDDFS. Let say b>l where b is branching factor and l is the depth limit. Then next we search the goal node under the bound k. On the depth k, we say there may be bknodes that are only generated once. Similarly, the nodes at the depth limit k-1 is twice and thrice for k-2 depth. Thus the node generated at depth l is k times.
Disadvantages of ID-DFS:
- The main drawback of IDDFS is that it repeats all the work of the previous phase.
- The time taken is exponential to reach the goal node.
- The main problem with IDDFS is the time and wasted calculations that take place at each depth.
- The situation is not as bad as we may think of especially when the branching factor is found to be high.
- The IDDFS might fail when the BFS fails. When we are to find
multiple answers from the IDDFS, it gives back the success nodes and its
path once even if it needs to be found again after multiple iterations.
To stop the depth bound is not increased further.
Performance Measurement
- Completeness: This algorithm is complete is ifthe branching factor is finite.
- Time Complexity: Let's suppose b is the branching factor and depth is d then the worst-case time complexity is O(bd).
- Space Complexity:The space complexity of IDDFS will be O(bd).
- Optimal: IDDFS algorithm is optimal if path cost is a non- decreasing function of the depth of the node.
