# Uninformed Search

Just do it.

## Overview

An uninformed (a.k.a. blind, brute-force) search algorithm generates the search tree without using any domain specific knowledge.

The two basic approaches differ as to whether you check for a goal when a node is generated or when it is expanded.

Checking at generation time:

if start_state is a goal state return the empty action list
fringe := [make_node(start_state, null, null)]
while fringe is not empty
n := select and remove some node from the fringe
for each action a applicable to n.state
s := succ(n.state, a)
n' := make_node(s, a, n)
if s is a goal state, return n'.actionListFromRoot()
return failure


Checking at expansion time:

fringe := [make_node(start_state, null, null)]
while fringe is not empty
n := select and remove some node from the fringe
if n.state is a goal state return n.actionListFromRoot()
for each action a applicable to n.state
add make_node(succ(n.state, a), a, n) to fringe
return failure


Strategy: expand the shallowest unexpanded node. Implementation: The fringe is a FIFO queue.

For this search tree

The queue evolves like this

    A
B C D
C D E F
D E F G H I
E F G H I J
F G H I J K L
G H I J K L M
H I J K L M
I J K L M N O
J K L M N O
K L M N O P Q
L M N O P Q
M N O P Q
N O P Q
O P Q
P Q R S T
Q R S T
R S T U
S T U
T U V
U V
V


That is, the order of generation is ABCDEFGHIJKLMNOPQRSTUV and the order of expansion is the same.

If the goal nodes were M, V, and J, Breadth-First search would find J, the shallowest.

BFS

• is complete (if $b$ is finite)
• is optimal if all path costs are the same (because it always finds the shallowest node first)
• Time complexity (worst case, goal at rightmost end of level $d$):
• Test at generation: $1 + b + b^2 + ... + b^d = O(b^d)$
• Test at expansion: $1 + b + b^2 + ... + b^d + (b^d-1)b = O(b^{d+1})$
• Space complexity is same as time complexity because every node has to say in memory. (Why?) That’s right: EXPONENTIAL SPACE.

## Depth-First Search

Strategy: expand the deepest unexpanded node. Implementation: The fringe is a LIFO queue (stack)

For the search tree above:

A
B C D
E F C D
K L F C D
L F C D
F C D
M C D
C D
G H I D
H I D
N O I D
O I D
R S T I D
S T I D
V T I D
T I D
I D
D
J
P Q
Q
U

Exercise: Give the order of generation and the order of expansion for this example.

If the goal nodes were M, V, and J, the Depth-First search above would find M.

DFS

• is not complete (because of infinite depth and loops)
• is not optimal
• Time complexity (worst case: solution is at m): O(bm) — regardless of whether we test at generation or expansion time. (Why?)
• If $m \geq d$, that sucks
• Can be better than BFS for dense solution space
• Space complexity is $O(bm)$ — linear space

## Depth-Limited Search

This is just a depth-first search with a cutoff depth. Here is the algorithm (for the test-at-expansion-time case)

fringe := [make_node(start_state, null, null)]
reached_limit := false
while fringe is not empty
n := fringe.pop()
if n.state is a goal state return n.actionListFromRoot()
if n.depth == limit
reached_limit := true
else
for each action a applicable to n.state
fringe.push(make_node(succ(n.state, a), a, n))
return reached_limit ? cutoff : failure


DLS

• Won’t run forever unless $b$ is infinite
• is not complete because a goal may be below the cutoff
• is not optimal
• Time complexity (worst case: every path reaches cutoff): $O(b^c)$ — regardless of whether we test at generation or expansion time. (Why?)
• Space complexity is $O(bc)$ — linear space.

## Depth-First Iterative Deepening

Algorithm:

for i in 1..infinity
run DLS to level i
if found a goal at level i, return it immediately


DFID

• is complete for finite b
• is optimal in terms of the solution depth (and optimal in general if path cost is non-decreasing function of depth)
• has asymptotic time complexity $O(b^d)$ in the worst case, ironically better than that of plain depth-first search!
• has very modest memory requirements $O(bd)$ if expansion-based or $O(d)$ if backtracking-based.
• generates fewer nodes than the version of BFS that checks for goals at expansion time
• is asymptotically optimal in terms of time and space among brute-force tree searches that find optimal solutions!
Exercise: Show that the number of nodes generated by DFID is less than $b^d(\frac{1}{(1-\frac{1}{b})^2})$.

## Uniform Cost Search

Strategy: Expand the lowest cost node. Implementation: the fringe is a priority queue: lowest cost node has the highest priority. In order to be optimal, must test at expansion, not generation, time.

## Backwards Chaining

Run the search backwards from a goal state to a start state. Obiously this works best when the actions are reversible, and the set of goal states is small.

## Bidirectional Search

Run a search forward from the start state and simulatneously. Motivation is that $b^{\frac{d}{2}} + b^{\frac{d}{2}}$ is much, much less than $b^d$. Works best when the backwards search is feasible. Problem is space complexity: one of the trees has to be kept in memory so we can test membership for a node generated in the other tree.