Chapter 3
3.3 Searching for solutions
Finding out a solution is done by
searching through the state space
All problems are transformed
as a search tree
generated by the initial state and
successor function
Search tree
Initial state
The root of the search tree is a search node
Expanding
applying successor function to the current state
thereby generating a new set of states
leaf nodes
the states having no successors
Fringe/Frontier : Set of search nodes that have
not been expanded yet.
Refer to next figure
Tree search example
Tree search example
Search tree
The essence of searching
in case the first choice is not correct
choosing one option and keep others for later
inspection
Hence we have the search strategy
which determines the choice of which state to
expand
good choice fewer work faster
Important:
state space ≠ search tree
Search tree
State space
has unique states {A, B}
while a search tree may have cyclic paths:
A-B-A-B-A-B- …
A good search strategy should avoid
such paths
Search tree
A node is having five components:
STATE: which state it is in the state space
PARENT-NODE: from which node it is generated
ACTION: which action applied to its parent-node
to generate it
PATH-COST: the cost, g(n), from initial state to
the node n itself
DEPTH: number of steps along the path from the
initial state
Measuring problem-solving performance
The evaluation of a search strategy
Completeness:
isthe strategy guaranteed to find a solution when
there is one?
Optimality:
doesthe strategy find the highest-quality solution
when there are several different solutions?
Time complexity:
how long does it take to find a solution?
Space complexity:
how much memory is needed to perform the search?
Measuring problem-solving performance
In AI, complexity is expressed in
b, branching factor, maximum number of
successors of any node
d, the depth of the shallowest goal node.
(depth of the least-cost solution)
m, the maximum length of any path in the state
space
Time and Space is measured in
numberof nodes generated during the search
maximum number of nodes stored in memory
Measuring problem-solving performance
For effectiveness of a search algorithm
we can just consider the total cost
The total cost = path cost (g) of the solution
found + search cost
search cost = time necessary to find the solution
Tradeoff:
(long time, optimal solution with least g)
vs. (shorter time, solution with slightly larger
path cost g)
3.4 Uninformed search strategies
3.4 Uninformed search strategies
Uninformed search
no information about the number of steps
or the path cost from the current state to
the goal
search the state space blindly
Informed search, or heuristic search
a cleverer strategy that searches toward
the goal,
based on the information from the current
state so far
Uninformed search strategies
Breadth-first search
Uniform cost search
Depth-first search
Depth-limited search
Iterative deepening search
Bidirectional search
Breadth-first search
The root node is expanded first (FIFO)
All the nodes generated by the root
node are then expanded
And then their successors and so on
Breadth-first search
S
A D
B D A E
C E E B B F
11
D F B F C E A C G
14 17 15 15 13
G C G F
19 19 17
G 25
Breadth-First Strategy
New nodes are inserted at the end of FRINGE
1
2 3 FRINGE = (1)
4 5 6 7
Breadth-First Strategy
New nodes are inserted at the end of FRINGE
1
2 3 FRINGE = (2, 3)
4 5 6 7
Breadth-First Strategy
New nodes are inserted at the end of FRINGE
1
2 3 FRINGE = (3, 4, 5)
4 5 6 7
Breadth-First Strategy
New nodes are inserted at the end of FRINGE
1
2 3 FRINGE = (4, 5, 6, 7)
4 5 6 7
Breadth-first search (Analysis)
Breadth-first search
Complete – find the solution eventually
Optimal, if step cost is 1
The disadvantage
if the branching factor of a node is large,
for even small instances (e.g., chess)
thespace complexity and the time complexity
are enormous
Properties of breadth-first search
Complete? Yes (if b is finite)
Time? 1+b+b2+b3+… +bd = b(bd-1) = O(bd+1)
Space? O(bd+1) (keeps every node in memory)
Optimal? Yes (if cost = 1 per step)
Space is the bigger problem (more than time)
Breadth-first search (Analysis)
assuming 10000 nodes can be processed per second, each
with 1000 bytes of storage
Uniform cost search
Breadth-first finds the shallowest goal state
butnot necessarily be the least-cost solution
work only if all step costs are equal
Uniform cost search
modifies breadth-first strategy
by always expanding the lowest-cost node
The lowest-cost node is measured by the path
cost g(n)
Uniform cost search
the first found solution is guaranteed to be the cheapest
least in depth
But restrict to non-decreasing path cost
Unsuitable for operators with negative cost
Uniform-cost search
Expand least-cost unexpanded node
Implementation:
fringe = queue ordered by path cost
Equivalent to breadth-first if step costs all equal
Complete? Yes, if step cost ≥ ε
Time? # of nodes with g ≤ cost of optimal solution, O(bceiling(C*/ ε))
where C* is the cost of the optimal solution
Space? # of nodes with g ≤ cost of optimal solution, O(bceiling(C*/ ε))
Optimal? Yes – nodes expanded in increasing order of g(n)
let
ε is possitive constant (every action cost)
C* be the cost of optimal solution.
Depth-first search
Always expands one of the nodes at the
deepest level of the tree
Only when the search hits a dead end
goes back and expands nodes at shallower levels
Dead end leaf nodes but not the goal
Backtracking search
only one successor is generated on expansion
rather than all successors
fewer memory
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
Expand deepest unexpanded node
fringe = LIFO queue, i.e., put successors at front
Implementation:
Depth-first search
S
A D
B D A E
C E E B B F
11
D F B F C E A C G
14 17 15 15 13
G C G F
19 19 17 G 25
Depth-first search (Analysis)
Not complete
because a path may be infinite or looping
then the path will never fail and go back try
another option
Not optimal
it doesn't guarantee the best solution
It overcomes
the time and space complexities
Properties of depth-first search
Complete? No: fails in infinite-depth spaces, spaces
with loops
Modify to avoid repeated states along path
complete in finite spaces
Time? O(bm): terrible if m is much larger than d
but if solutions are dense, may be much faster than
breadth-first
Space? O(bm), i.e., linear space!
Optimal? No
Depth-Limited Strategy
Depth-first with depth cutoff k (maximal
depth below which nodes are not
expanded)
Three possible outcomes:
Solution
Failure (no solution)
Cutoff (no solution within cutoff)
Depth-limited search
It is depth-first search
with a predefined maximum depth
However, it is usually not easy to define
the suitable maximum depth
too small no solution can be found
too large the same problems are
suffered from
Anyway the search is
complete
but still not optimal
Depth-limited
S
search
depth = 3
A D 3
6
B D A E
C E E B B F
11
D F B F C E A C G
14 17 15 15 13
G C G F
19 19 17
G 25
Iterative deepening search
No choosing of the best depth limit
It tries all possible depth limits:
first
0, then 1, 2, and so on
combines the benefits of depth-first and
breadth-first search
Iterative deepening search
Iterative deepening search
(Analysis)
optimal
complete
Time and space complexities
reasonable
suitable for the problem
having a large search space
and the depth of the solution is not known
Properties of iterative deepening
search
Complete? Yes
Time? (d+1)b0 + d b1 + (d-1)b2 + … + bd
= O(bd)
Space? O(bd)
Optimal? Yes, if step cost = 1
Iterative lengthening search
IDS is using depth as limit
ILS is using path cost as limit
an iterative version for uniform cost search
has the advantages of uniform cost search
while avoiding its memory requirements
but ILS incurs substantial overhead
compared to uniform cost search
Bidirectional search
Run two simultaneous searches
one forward from the initial state another
backward from the goal
stop when the two searches meet
However, computing backward is difficult
A huge amount of goal states
at the goal state, which actions are used to
compute it?
can the actions be reversible to computer its
predecessors?
Bidirectional Strategy
2 fringe queues: FRINGE1 and FRINGE2
Time and space complexity = O(bd/2) << O(bd)
Bidirectional
S search
Forward
A D Backwards
B D A E
C E E B B F
11
D F B F C E A C G
14 17 15 15 13
G C G F
19 19 17
G 25
Comparing search strategies
Avoiding repeated states
for all search strategies
There is possibility of expanding states
that
have already been encountered and expanded
before, on some other path
may cause the path to be infinite loop forever
Algorithms that forget their history
are doomed to repeat it
Avoiding repeated states
Three ways to deal with this possibility
Do not return to the state it just came from
Refusegeneration of any successor same as its
parent state
Do not create paths with cycles
Refuse
generation of any successor same as its
ancestor states
Do not generate any generated state
Not
only its ancestor states, but also all other
expanded states have to be checked against
Avoiding repeated states
We then define a data structure
closed list:
a set storing every expanded node so far
If the current node matches a node on the
closed list, discard it.