Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Depth-First Search (DFS)
DFS expands the deepest unexpanded node first, using a LIFO stack for the frontier. It only backtracks when a node has no more successors to expand.
| Criterion | DFS |
|---|---|
| Complete | No for infinite depth spaces; No for finite spaces with loops; Yes with repeated state checking or with finite depth and no loops |
| Time | , can be much faster than BFS if solutions are dense |
| Space | , only the current path and its siblings are stored |
| Optimal | No |
Here is the maximum depth of the state space, which can be much larger than (or infinite).
Depth-Limited Search (DLS)
DLS is DFS with a cutoff on path depth, which avoids searching forever down an infinite branch. If the goal is deeper than , it is never found.
| Criterion | DLS |
|---|---|
| Complete | Yes, if |
| Time | |
| Space | |
| Optimal | No |
Iterative Deepening Search (IDS)
IDS fixes the problem of choosing by running DLS with limit 0, 1, 2, ... until a solution is found.
function ITERATIVE-DEEPENING-SEARCH(problem):
for depth = 0 to infinity:
result = DEPTH-LIMITED-SEARCH(problem, depth)
if result succeeds: return result
return failure| Criterion | IDS |
|---|---|
| Complete | Yes |
| Time | |
| Space | |
| Optimal | Yes, when step costs are equal |
The shallow levels are regenerated each round, but since most nodes are at the deepest level this repeated work is small. IDS gets BFS's completeness and optimality with DFS's small memory, so it is the usual choice for uninformed search on large spaces.
None of these use any idea of where the goal is. Adding a heuristic gives Greedy Best-First Search.