Uninformed Search

search

Examples

Breadth-First Search

Definition

Breadth-First Search

Breadth-first search is about expanding the shallowest unexpanded node. The frontier is a FIFO queue, i.e., new successors go at the end.

Link to original

Uniform-Cost Search

Definition

Uniform-Cost Search

Uniform-cost search is about expanding the least-code unexpanded node. The frontier is a priority queue sorted by path cost, lowest first.

Link to original

Depth-First Search

Definition

Depth-First Search

Depth-first search is about expanding the deepest unexpanded node. The frontier is a LIFO queue, i.e., put successors at front.

Link to original

Depth-Limited Search

Definition

Depth-Limited Search

Depth-limited search behaves like depth-first search but limited, meaning it terminates if all nodes within a certain depth are explored.

Nodes below depth $d=\underset{=2}{\underbrace{\ell }}+1$ remain unexplored.

Link to original

Iterative Deepening Search

Definition

Iterative Deepening Search

Iterative deepening search is an extension of depth-limited search that iteratively increases the limit $\ell$.

Link to original

Bidirectional Search

Definition

Bidirectional Search

Bidirectional search is a search strategy that searches from the given initial state and backward from a goal state. Thus, it needs “invertible” actions, meaning it can go from state $s$ to predecessor states $s^{\prime }$.

Link to original