Depth-First Search (DFS)
In DFS, we start from a node and go down a path until we reach a node that has no children. Whenever we run out of moves, we backtrack and explore the sibling of the node. And if there are no siblings, we go for the sibling of the grandparent and so on.
- No matter how deep we go, DFS will always go deeper if there's a child.
- However, DFS fails to terminate if there's an infinite path. So, it's not optimal for most problems.
Depth-Limited Search
It's the same as DFS, but the nodes with a depth equal to a fixed maximum (let's say M) aren't expanded.
- M-Limited DFS will find a solution if it exists at a depth M or less.
- If there's a solution at a depth greater than M, we won't be able to find it.
Iterative Deepening
This one performs depth-limited DFS repeatedly with an increasing depth limit until we find a solution.
- We never end up exploring infinite dead-end paths, as the length of each path is capped by some length at each step.
- It finds the shortest possible path to the destination node.
- It runs in O(b^d) time but uses only O(d) space.
Alright, I hope I was able to help you out with the proofreading and correction of the text. Let me know if you need any further assistance.