Uninformed
search
strategies
• A
search
strategy
is
defined
by
picking
the
order
of
node
expansion
• Uninformed
search
strategies
use
only
the
informa:on
available
in
the
problem
defini:on
– Breadth-‐first
search
– Depth-‐first
search
– Itera:ve
deepening
search
– Uniform-‐cost
search
Breadth-‐first
search
• Expand
shallowest
unexpanded
node
• Implementa:on:
fron%er
is
a
FIFO
queue
Example
state
space
graph
for
a
:ny
search
problem
Example from P. Abbeel and D. Klein
Breadth-‐first
search
• Expansion
order:
(S,d,e,p,b,c,e,h,r,q,a,a,
h,r,p,q,f,p,q,f,q,c,G)
Depth-‐first
search
• Expand
deepest
unexpanded
node
• Implementa:on:
fron%er
is
a
LIFO
queue
Depth-‐first
search
• Expansion
order:
(d,b,a,c,a,e,h,p,q,q,
r,f,c,a,G)
http://xkcd.com/761/
Analysis
of
search
strategies
• Strategies
are
evaluated
along
the
following
criteria:
– Completeness:
does
it
always
find
a
solu:on
if
one
exists?
– Op7mality:
does
it
always
find
a
least-‐cost
solu:on?
– Time
complexity:
number
of
nodes
generated
– Space
complexity:
maximum
number
of
nodes
in
memory
• Time
and
space
complexity
are
measured
in
terms
of
– b:
maximum
branching
factor
of
the
search
tree
– d:
depth
of
the
op:mal
solu:on
– m:
maximum
length
of
any
path
in
the
state
space
(may
be
infinite)
Proper:es
of
breadth-‐first
search
• Complete?
Yes
(if
branching
factor
b
is
finite)
• Op7mal?
Yes
–
if
cost
=
1
per
step
• Time?
Number
of
nodes
in
a
b-‐ary
tree
of
depth
d:
O(bd)
(d
is
the
depth
of
the
op:mal
solu:on)
• Space?
O(bd)
• Space
is
the
bigger
problem
(more
than
:me)
Proper:es
of
depth-‐first
search
• Complete?
Fails
in
infinite-‐depth
spaces,
spaces
with
loops
Modify
to
avoid
repeated
states
along
path
à
complete
in
finite
spaces
• Op7mal?
No
–
returns
the
first
solu:on
it
finds
• Time?
Could
be
the
:me
to
reach
a
solu:on
at
maximum
depth
m:
O(bm)
Terrible
if
m
is
much
larger
than
d
But
if
there
are
lots
of
solu:ons,
may
be
much
faster
than
BFS
• Space?
O(bm),
i.e.,
linear
space!
Itera:ve
deepening
search
• Use
DFS
as
a
subrou:ne
1. Check
the
root
2. Do
a
DFS
searching
for
a
path
of
length
1
3. If
there
is
no
path
of
length
1,
do
a
DFS
searching
for
a
path
of
length
2
4. If
there
is
no
path
of
length
2,
do
a
DFS
searching
for
a
path
of
length
3…
Itera:ve
deepening
search
Itera:ve
deepening
search
Itera:ve
deepening
search
Itera:ve
deepening
search
Proper:es
of
itera:ve
deepening
search
• Complete?
Yes
• Op7mal?
Yes,
if
step
cost
=
1
• Time?
(d+1)b0
+
d
b1
+
(d-‐1)b2
+
…
+
bd
=
O(bd)
• Space?
O(bd)
Search
with
varying
step
costs
• BFS
finds
the
path
with
the
fewest
steps,
but
does
not
always
find
the
cheapest
path
Uniform-‐cost
search
• For
each
fron:er
node,
save
the
total
cost
of
the
path
from
the
ini:al
state
to
that
node
• Expand
the
fron:er
node
with
the
lowest
path
cost
• Implementa:on:
fron%er
is
a
priority
queue
ordered
by
path
cost
• Equivalent
to
breadth-‐first
if
step
costs
all
equal
• Equivalent
to
Dijkstra’s
algorithm
in
general
Uniform-‐cost
search
example
Uniform-‐cost
search
example
• Expansion
order:
(S,p,d,b,e,a,r,f,e,G)
Another
example
of
uniform-‐cost
search
Source: Wikipedia
Proper:es
of
uniform-‐cost
search
• Complete?
Yes,
if
step
cost
is
greater
than
some
posi:ve
constant
ε
(we
don’t
want
infinite
sequences
of
steps
that
have
a
finite
total
cost)
• Op7mal?
Yes
Op:mality
of
uniform-‐cost
search
• Graph
separa7on
property:
every
path
from
the
ini:al
state
to
an
unexplored
state
has
to
start
pass
through
a
state
on
the
fron:er
– Proved
induc:vely
• Op:mality
of
UCS:
proof
by
contradic:on
frontier
– Suppose
UCS
terminates
at
goal
state
n
with
path
cost
g(n)
but
there
exists
n’’
another
goal
state
n’
with
g(n’)
<
g(n)
– By
the
graph
separa:on
property,
there
n’
must
exist
a
node
n”
on
the
fron:er
that
is
on
the
op:mal
path
to
n’
n
– But
because
g(n”)
≤
g(n’)
<
g(n),
n”
should
have
been
expanded
first!
Proper:es
of
uniform-‐cost
search
• Complete?
Yes,
if
step
cost
is
greater
than
some
posi:ve
constant
ε
(we
don’t
want
infinite
sequences
of
steps
that
have
a
finite
total
cost)
• Op7mal?
Yes
–
nodes
expanded
in
increasing
order
of
path
cost
• Time?
Number
of
nodes
with
path
cost
≤
cost
of
op:mal
solu:on
(C*),
O(bC*/
ε)
This
can
be
greater
than
O(bd):
the
search
can
explore
long
paths
consis:ng
of
small
steps
before
exploring
shorter
paths
consis:ng
of
larger
steps
• Space?
O(bC*/
ε)
Review:
Uninformed
search
strategies
Time
Space
Algorithm
Complete?
Op7mal?
complexity
complexity
Yes
If
all
step
O(bd)
O(bd)
BFS
costs
are
equal
DFS
No
No
O(bm)
O(bm)
If
all
step
O(bd)
IDS
Yes
O(bd)
costs
are
equal
UCS
Yes
Yes
Number
of
nodes
with
g(n)
≤
C*
b:
maximum
branching
factor
of
the
search
tree
d:
depth
of
the
op:mal
solu:on
m:
maximum
length
of
any
path
in
the
state
space
C*:
cost
of
op:mal
solu:on
g(n):
cost
of
path
from
start
state
to
node
n
