Depth-first search (DFS)

Depth-first search (DFS)

• Description:
• DFS progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it hasn’t finished exploring.
• Order in which nodes are expanded
  
• Performance Measure:
  • Completeness: 
    • DFS is not complete, to convince yourself consider that our search start expanding the left sub tree of the root for so long path (may be infinite) when different choice near the root could lead to a solution, now suppose that the left sub tree of the root has no solution, and it is unbounded, then the search will continue going deep infinitely, in this case we say that DFS is not complete.
  • Optimality:
    • Consider the scenario that there is more than one goal node, and our search decided to first expand the left sub tree of the root where there is a solution at a very deep level of this left sub tree, in the same time the right sub tree of the root has a solution near the root, here comes the non-optimality of DFS that it is not guaranteed that the first goal to find is the optimal one, so we conclude that DFS is not optimal.
  • Time Complexity:
    • Consider a state space that is identical to that of BFS, with branching factor b, and we start the search from the root.
    • In the worst case that goal will be in the shallowest level in the search tree resulting in generating all tree nodes which are O(b^m).
  • Space Complexity:
    • Unlike BFS, our DFS has a very modest memory requirements, it needs to story only the path from the root to the leaf node, beside the siblings of each node on the path, remember that BFS needs to store all the explored nodes in memory.
    • DFS removes a node from memory once all of its descendants have been expanded.
    • With branching factor b and maximum depth m, DFS requires storage of only bm + 1 nodes which are O(bm) compared to the O(b^d+1) of the BFS.
• Conclusion:
  • DFS may suffer from non-termination when the length of a path in the search tree is infinite, so we perform DFS to a limited depth which is called Depth-limited Search.