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.

CriterionDFS
CompleteNo 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
OptimalNo

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.

CriterionDLS
CompleteYes, if
Time
Space
OptimalNo

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
CriterionIDS
CompleteYes
Time
Space
OptimalYes, 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.