Solving Problems by Searching

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

Solving Problems by Searching

Uploaded by

Copyright:

Available Formats

Solving Problems by Searching

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Solving Problems by Searching

Uploaded by

Copyright:

Available Formats

Solving Problems by

Formal State-Space Model

How do we define a solution?

The legal operations are to turn over exactly one coin.

There are two goal states:

Modified State-Space Problem

How do we build a search tree for

The 8-Puzzle Problem

1. Formalize a state as a data structure

Search Tree Example:

Another Example: N Queens

Operators [and costs]

Example: Route Planning

Depth first search

Informed Search (Ch 4)

Depth First Search

Not for infinite spaces

Breadth First Search

The Missionaries and Cannibals Problem

Missionaries and Cannibals Problem

Missionaries and Cannibals Problem

Missionary and Cannibals Notes

When the boat is moving, we are in

When is a state considered DEAD?

You may use the computer language of your

200,000 expansions / sec

Iterative Deepening Search

Cost of Iterative Deepening

Forwards vs. Backwards

You might also like