�ݺ�ߣ

Now would be a good time to
kill your cell phone, and
disconnect from the internet.
For next time, print Heuristic
Search.ppt slides

Due to the graphic nature of
the following slides, user
discretion is advised.

Due to the graphic nature of
the following slides, user
discretion is advised.
All grads are considered
guilty until proven innocent
in a court of law.

F W D C
W D C
F
D C
F W
W C
F D
W D
F C
F W C
D
F W D C
W
F D C
F W C
D
W C
F D
C
F W D
F C
W D
F D C
W
D
F W C
F W D
C
F W
D C
F W C
D
W D
F C
W
F D C
C
F W D
D C
F W
D
F W C
F D C
W
F W D
C
F D
W C
F W D C
D
F W C
Goal StateRepeated StateIllegal StateSearch Tree for “Farmer, Wolf, Duck, Corn”
Last time we saw

A farm hand was
sent to a nearby
pond to fetch 8
gallons of water. He
was given two pails -
one 11, the other 6
gallons. How can he
measure the
requested amount of
water?
Sliding Tile Puzzle
You can slide any of the
numbered tiles into the blank
space.
Can you arrange the numbers into
order?
Can you place 8 queens
on a chessboard such
that no piece is
attacking another?
Find a route from LAX
to the Golden Gate
bridge that minimizes
the driving time, ...that
minimizes the mileage,
...that minimizes the
number of Taco Bells
you must pass.
Which tree shows the correct relationship
between gorilla, chimp and man?
When you have just 3 animals, there are
only three possible trees...
Last time we saw…

Problem Solving using Search
A Problem Space consists of
• The current state of the world (initial state)
• A description of the actions we can take to transform one
state of the world into another (operators).
• A description of the desired state of the world (goal state),
this could be implicit or explicit.
•A solution consists of the goal state*, or a path to the goal
state.
* Problems were the path does not matter are known as “constraint satisfaction”
problems.

1 2 3
4 5 6
7 8
Initial State Goal StateOperators
�ݺ�ߣ blank square left.
�ݺ�ߣ blank square right.
….
FWDC FWDC
Move F
Move F with W
….
( ) XXX =+
2
1 Distributive property
Associative property
...
XX =
Add a queen such that it
does not attack other,
previously placed queens.
A 4 by 4 chessboard
with 4 queens placed on
it such that none are
attacking each other
2 1 3
4 7 6
5 8
4 Queens

Representing the states
A state space should describe
• Everything that is needed to solve the problem.
• Nothing that is not needed to solve the problem.
In general, many possible
representations are possible,
choosing a good representation
will make solving the problem
much easier.
For the 8-puzzle
• 3 by 3 array
• 5, 6, 7
8, 4, BLANK
3, 1, 2
• A vector of length nine
• 5,6,7,8,4, BLANK,3,1,2
• A list of facts
•Upper_left = 5
•Upper_middle = 6
•Upper_right = 7
•Middle_left = 8
•….
Choose the representation that make the operators easiest to
implement.

Operators I
• Single atomic actions that can transform one state into another.
• You must specify an exhaustive list of operators, otherwise
the problem may be unsolvable.
• Operators consist of
• Precondition: Description of any conditions that must be true before
using the operator.
• Instruction on how the operator changes the state.
• In general, for any given state, not all operators are possible.
Examples:
In FWDC, the operator Move_Farmer_Left is not possible if the farmer
is already on the left bank.
In this 8-puzzle,
The operator Move_6_down is possible
But the operator Move_7_down is not.
2 1 3
4 7 6
5 8

Operators II
Example: For the eight puzzle we could have...
• Move 1 left
• Move 1 right
• Move 1 up
• Move 1 down
• Move 2 left
• Move 2 right
• Move 2 up
• Move 2 down
• Move 3 left
• Move 3 right
• Move 3 up
• Move 3 down
• Move 4 left
• …
There are often many ways to specify the operators, some
will be much easier to implement...
• Move Blank left
• Move Blank right
• Move Blank up
• Move Blank down
Or
2 1 3
4 7 6
5 8

A complete example: The Water Jug Problem
• Two jugs of capacity 4 and 3 units.
• It is possible to empty a jug, fill a jug,
transfer the content of a jug to the other
jug until the former empties or the latter
fills.
• Task: Produce a jug with 2 units.
A farm hand was sent to a
nearby pond to fetch 2
gallons of water. He was
given two pails - one 4, the
other 3 gallons. How can he
measure the requested
amount of water?
Abstract away
unimportant
details
State representation (X , Y)
• X is the content of the 4 unit jug.
• Y is the content of the 3 unit jug.
Initial State (0 , 0)
Goal State (2 , n)
Operators
• Fill 3-jug from faucet (a, b) ⇒ (a, 3)
• Fill 4-jug from faucet (a, b) ⇒ (4, b)
• Fill 4-jug from 3-jug (a, b) ⇒ (a + b, 0)
• ...
Define a state representation
Define an initial state
Define an goal state(s)
May be a description rather than explicit state
Define all operators

F W D C
W D C
F
D C
F W
W C
F D
W D
F C
F W C
D
F W D C
W
F D C
F W C
D
W C
F D
C
F W D
F C
W D
F D C
W
D
F W C
F W D
C
F W
D C
F W C
D
W D
F C
W
F D C
C
F W D
D C
F W
D
F W C
F D C
W
F W D
C
F D
W C
F W D C
D
F W C
Once we have defined the problem space (state representation,
the initial state, the goal state and operators) are we are done?
We start with the initial state and keep using the operators to
expand the parent nodes till we find a goal state.
…but the search
space might be
large…
…really large…
So we need some
systematic way to
search.

• The average number of new nodes we create when expanding
a new node is the (effective) branching factor b.
• The length of a path to a goal is the depth d.
A
B C
ED
H I J K L M N O
GF
A Generic Search Tree
b
b2
bd
So visiting every the
every node in the search
tree to depth d will take
O(bd
) time.
Not necessarily O(bd
)
space.
Fringe (Frontier)
Set of nonterminal nodes without children
I.e nodes waiting to be expanded.

Branching factors for some problems
The eight puzzle has a branching factor of 2.13, so a
search tree at depth 20 has about 3.7 million nodes.
(note that there only 181,400 different states).
Rubik’s cube has a branching factor of 13.34. There
are 901,083,404,981,813,616 different states. The
average depth of a solution is about 18. The best time
for solving the cube in an official championship was 17.04
sec, achieved by Robert Pergl in the 1983 Czechoslovakian
Championship.
Chess has a branching factor of about 35, there are
about 10120
states (there are about 1079
electrons in the
universe).
2 1 3
4 7 6
5 8

F W D C
W D C
F
D C
F W
W C
F D
W D
F C
F W C
D
F W D C
W
F D C
F W C
D
W C
F D
C
F W D
F C
W D
F D C
W
D
F W C
F W D
C
F W
D C
F W C
D
W D
F C
W
F D C
C
F W D
D C
F W
D
F W C
F D C
W
F W D
C
F D
W C
F W D C
D
F W C
Detecting repeated states is hard….

A
B C
ED
H I J K L M N O
GF
We are going to consider different techniques to search the
problem space, we need to consider what criteria we will use to
compare them.
• Completeness: Is the technique
guaranteed to find an answer (if there is
one).
• Optimality: Is the technique guaranteed
to find the best answer (if there is more
than one). (operators can have different costs)
• Time Complexity: How long does it
take to find a solution.
• Space Complexity: How much memory
does it take to find a solution.

General (Generic) Search Algorithm
function general-search(problem, QUEUEING-FUNCTION)
nodes = MAKE-QUEUE(MAKE-NODE(problem.INITIAL-STATE))
loop do
if EMPTY(nodes) then return "failure"
node = REMOVE-FRONT(nodes)
if problem.GOAL-TEST(node.STATE) succeeds then return node
nodes = QUEUEING-FUNCTION(nodes, EXPAND(node, problem.OPERATORS))
end
A nice fact about this search algorithm is that we can use a single algorithm to
do many kinds of search. The only difference is in how the nodes are placed in
the queue.

Breadth First Search
Enqueue nodes in FIFO (first-in, first-out) order.
• Complete? Yes.
• Optimal? Yes.
• Time Complexity: O(bd
)
• Space Complexity: O(bd
), note that every node in the fringe is kept in the queue.
Intuition: Expand all nodes at depth i before
expanding nodes at depth i + 1

Uniform Cost Search
Enqueue nodes in order of cost
• Complete? Yes.
• Optimal? Yes, if path cost is nondecreasing function of depth
)
• Space Complexity: O(bd
), note that every node in the fringe keep in the queue.
Intuition: Expand the cheapest node. Where
the cost is the path cost g(n)
25 25
1 7
25
1 7
4 5
Note that Breadth First search can be seen as a special case of Uniform Cost Search, where the path cost is just the depth.

Depth First Search
Enqueue nodes in LIFO (last-in, first-out) order.
• Complete? No (Yes on finite trees, with no loops).
• Optimal? No
• Time Complexity: O(bm
), where m is the maximum depth.
• Space Complexity: O(bm), where m is the maximum depth.
Intuition: Expand node at the deepest level
(breaking ties left to right)

Depth-Limited Search
Enqueue nodes in LIFO (last-in, first-out) order. But limit depth to L
• Complete? Yes if there is a goal state at a depth less than L
• Optimal? No
• Time Complexity: O(bL
), where L is the cutoff.
• Space Complexity: O(bL), where L is the cutoff.
Intuition: Expand node at the deepest level,
but limit depth to L
L is 2 in this example
Picking the right value for L
is a difficult, Suppose we
chose 7 for FWDC, we will
fail to find a solution...

Iterative Deepening Search I
Do depth limited search starting a L = 0, keep incrementing L by 1.
• Complete? Yes
• Optimal? Yes
), where d is the depth of the solution.
• Space Complexity: O(bd), where d is the depth of the solution.
Intuition: Combine the Optimality and
completeness of Breadth first search, with the
low space complexity of Depth first search

Iterative Deepening Search II
1+10+100+1000+10,000+100,000 = 111,111
1
1+10
1+10+100
1+10+100+1000
1+10+100+1000+10,000
1+10+100+1000+10,000+100,000
= 123,456
Consider a problem with a branching factor of
10 and a solution at depth 5...
Iterative deepening looks wasteful because
we reexplore parts of the search space many
times...

Bi-directional Search
Intuition: Start searching from both the initial
state and the goal state, meet in the middle.
• Complete? Yes
• Optimal? Yes
• Time Complexity: O(bd/2
• Space Complexity: O(bd/2
Notes
• Not always possible to search
backwards
• How do we know when the trees
meet?
• At least one search tree must be
retained in memory.

�ݺ�ߣ

1 blind search

More Related Content

1 blind search