Solving Problems by
Searching
Terminology
State
State Space
Goal
Action
Cost
State Change Function
Problem-Solving Agent
State-Space Search
2
Formal State-Space Model
Problem = (S, s, A, f, g, c)
S = state space
s = initial state
A = actions
f = state change function
g = goal test function
c = cost function
x
f: S x A -> S
g: S -> {true,false}
c: S x A x S -> R
How do we define a solution?
How about an optimal solution?
3
3 Coins Problem
A Very Small State Space Problem
There are 3 (distinct) coins: coin1, coin2, coin3.
The initial state is
The legal operations are to turn over exactly one coin.
1 (flip coin1), 2 (flip coin2), 3 (flip coin3)
There are two goal states:
What are S, s, A, f, g, c ?
H
T
H
T
H
T
State-Space Graph
2
HHT
THT
3
HTT
3
THH
1
HHH
TTT
3
HTH
TTH
1
What are some solutions?
What if the problem is changed to allow only 3 actions?
Modified State-Space Problem
How would you define a state for the new
problem?
How do you define the operations (1, 2, 3)
with this new state definition?
What do the paths to the goal states look
like now?
6
How do we build a search tree for
the modified 3 coins problem?
initial
state
1
The 8-Puzzle Problem
one
initial
state
7 2 4
5 B 6
8 3 1
B 1 2
goal 3 4 5
state 6 7 8
B=blank
1. Formalize a state as a data structure
2. Show how start and goal states are represented.
3. How many possible states are there?
4. How would you specify the state-change function?
5. What is the goal test?
6. What is the path cost function?
7. What is the complexity of the search?
8
Search Tree Example:
Fragment of 8-Puzzle Problem Space
Another Example: N Queens
Input:
Set of states
Q
Q
Q
Operators [and costs]
Start state
Goal state (test)
Output
10
Example: Route Planning
Input:
Set of states
Operators [and costs]
Start state
Goal state (test)
Output:
11
Search Strategies
Blind Search (Ch 3)
Depth first search
Breadth first search
Depth limited search
Iterative deepening search
Informed Search (Ch 4)
Constraint Satisfaction (Ch 5)
12
Depth First Search
Maintain stack of nodes to visit
Evaluation
Complete?
Not for infinite spaces
Time Complexity?
O(b^d)
Space ?
O(d)
e
d
13
Breadth First Search
Maintain queue of nodes to visit
Evaluation
Complete?
Yes
Time Complexity?
O(b^d)
Space?
O(b^d)
14
The Missionaries and Cannibals Problem
(from text problem 3.9)
Three missionaries and three cannibals are on one side
of a river, along with a boat that can hold one or two
people.
If there are ever more cannibals than missionaries on
one side of the river, the cannibals will eat the
missionaries. (We call this a dead state.)
Find a way to get everyone to the other side, without
anyone getting eaten.
15
Missionaries and Cannibals Problem
16
Missionaries and Cannibals Problem
Left Bank
Right Bank
River
17
Missionary and Cannibals Notes
Define your state as (M,C,S)
M: number of missionaries on left bank
C: number of cannibals on left bank
S: side of the river that the boat is on
When the boat is moving, we are in
between states. When it arrives, everyone
gets out.
18
When is a state considered DEAD?
1. There are more cannibals than missionaries
on the left bank.
(Bunga-Bunga)
2. There are more cannibals than missionaries
on the right bank. (Bunga-Bunga)
3. There is an ancestor state of this state that is
exactly the same as this state. (Why?)
19
Assignment
Implement and solve the problem with a depthfirst search using a stack and/or recursion.
Find and print all 4 solutions. (See web page.)
Keep track of the total number of states searched.
When you get to a dead state, count it and then back
up to its parent.
You may use the computer language of your
choice for this assignment.
Java
C++
20
Is memory a limitation in
search?
Suppose:
2 GHz CPU
1 GB main memory
100 instructions / expansion
5 bytes / node
200,000 expansions / sec
Memory filled in 100 sec < 2
minutes
21
Iterative Deepening Search
DFS with limit; incrementally
grow limit
Evaluation
a b e
Complete?
Yes
c f
d i
Time Complexity?
O(b^d)
Space Complexity?
O(d)
22
Cost of Iterative Deepening
b
ratio ID to DFS
1.5
10
1.2
25
1.08
100
1.02
23
sta
rt
Forwards vs. Backwards
en
24
vs. Bidirectional
25
Problem
All these methods are too slow for real
applications (blind)
Solution
add guidance
informed search
26
