Properties of Depth First Search: Let us now examine some properties of the DFS algorithm. The algorithm takes exponential time. If N is the maximum depth of a node in the search space, in the worst case the algorithm will take time O(bd). However the space taken is linear in the depth of the search tree, O(bN). Note that the time taken by the algorithm is related to the maximum depth of the search tree. If the search tree has infinite depth, the algorithm may not terminate. This can happen if the search space is infinite. It can also happen if the search space contains cycles. The latter case can be handled by checking for cycles in the algorithm. Thus Depth First Search is not complete.
Depth Limited Search: A variation of Depth First Search circumvents the above problem by keeping a depth bound. Nodes are only expanded if they have depth less than the bound. This algorithm is known as depth-limited search.
Depth-First Iterative Deepening (DFID): First do DFS to depth 0 (i.e., treat start node as having no successors), then, if no solution found, do DFS to depth 1, etc.
Advantage
• Linear memory requirements of depth-first search
• Guarantee for goal node of minimal depth
Procedure: Successive depth-first searches are conducted – each with depth bounds increasing by 1
Properties: For large d the ratio of the number of nodes expanded by DFID compared to that of DFS is given by b/(b-1). For a branching factor of 10 and deep goals, 11% more nodes expansion in iterative-deepening search than breadth-first search The algorithm is
Depth First Iterative Deepening combines the advantage of BFS (i.e., completeness) with the advantages of DFS (i.e., limited space and finds longer paths more quickly) This algorithm is generally preferred for large state spaces where the solution depth is unknown. There is a related technique called iterative broadening is useful when there are many goal nodes. This algorithm works by first constructing a search tree by expanding only one child per node. In the 2nd iteration, two children are expanded, and in the ith iteration I children are expanded.