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.
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.