See On Github

Wikipedia Description

In computer science, Iterative deepening depth-first search (IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches, the depth of the shallowest goal state. IDDFS is equivalent to breadth-first search, but uses much less memory; on each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first. IDDFS combines depth-first search 's space-efficiency and breadth-first search 's completeness (when the branching factor is finite). It is optimal when the path cost is a non-decreasing function of the depth of the node. The space complexity of IDDFS is, where is the branching factor and is the depth of shallowest goal. is required in case of Iterative-DFS. However, it can be reduced to by using recursive-dfs, since backtracking is taken care by the function call stack. https://en.wikipedia.org/wiki/Iterative_deepenin...

Tags
graph traversal, pathfinding

Implementations