Uninformed Searching | Sahithyan's Notes

Also known as blind search. Methods for exploring state spaces without using domain-specific knowledge about the problem.

These algorithms only know how to generate successor states and recognize goal states, but don’t have information about how close they are to a solution.

Branching Factor

The average number of successors generated from each node in a search tree or graph. Finite graph implies finite branching factor. Opposite is not necessarily true.

Algorithms

Depth-First Search

Complete iff search space is finite state space. Wanders off into infinite paths for infinite graphs. Not optimal, returns the first solution it finds.

Covered in detail in DFS on Graphs.

Depth-Limited DFS

Also known as DDFS. Depth-constrained DFS. Avoids wandering off into infinite paths.

Not complete. Causes a false-negative for nodes far apart. Not optimal. Returns the first solution it finds.

Iterative Deepening DFS

Also known as IDS. Repeatedly runs DDFS with increasing depth limits. Stops when a solution is found. Complete iff finite. Wanders off into infinite for infinite graphs. Optimal iff all action costs are equal. Time complexity comparable to BFS. Space complexity is linear.

Works similar to BFS, but uses much less memory.

Breadth-First Search

Expands the shallowest nodes first. Covered in detail in BFS on Graphs.

Bidirectional Search

Expands 2 frontiers: around initial and goal states. BFS is used because it searches level by level. Stops when the frontiers meet.

Uniform Cost Search

Also known as Dijkstra’s algorithm. Fails for graphs with negative weights. Expands the node with the lowest path cost. Optimal for general action costs. Named uniform because it expands nodes in increasing order of path cost.

Comparison

Algorithm	Complete?	Optimal?	Time Complexity	Space Complexity
DFS	Yes*	No	$O(V+E)$ or $O(b^m)$	$O(V)$ or $O(bm)$
DDFS	No	No	$O(b^l)$	$O(bl)$
IDS	Yes*	Yes**	$O(b^d)$	$O(bd)$
BFS	Yes*	Yes**	$O(V+E)$ or $O(b^d)$	$O(V)$ or $O(b^d)$
Bidirectional	Yes*	Yes**	$O(b^{d/2})$	$O(b^{d/2})$
UCS	Yes*	Yes	$O(b^{1+C/ε})$ or $O((V+E)\log V)$	$O(b^{1+C/ε})$ or $O(V)$

* Iff the graph is finite.
** Iff all costs are equal.

Here:

O(V)

Here:

$b$: branching factor
$d$: depth of the shallowest solution
$m$: maximum depth of the state space
$l$: depth limit
$C$: cost of the optimal solution
$ε$: minimum action cost