Depth-First Search(DFS)

In DFS, we begin at some node and goes down a path until it reaches a node that has no children. Any time DFS runs out of moves, it backtracks and expands a sibling of the node. If the node had no siblings, then DFS looks for sibling of the grandparent and so on.

  • No matter how deep the current node is, DFS will always go deeper if it has a child.
  • DFS will fail to terminate if there is an infinite path. In other words, DFS is not optimal for most problems.

Same as DFS, except nodes of depth equal to a fixed maximum (say M) are not expanded.

  • M-Limited DFS will find a solution if a solution exists at depth M or less.
  • If a solution exists at a depth greater than M then it won’t be able to find the solution.

Iterative Deepening

Performs depth-limited DFS repeatedly with an increasing depth limit until a solution is found.

  • Never end up exploring infinite dead-end paths, as length of each path is capped by some length at each step.
  • Find shortest possible path to the destination node.
  • Run in O(b^d) time but only uses O(d) space.