Hill Climbing Algorithm
Hill Climbing Algorithm
Hill Climbing Algorithm
Chapter 3
Outline
Generate-and-test
Hill climbing
Best-first search
Problem reduction
Constraint satisfaction
Means-ends analysis
Generate-and-Test
Algorithm
1. Generate a possible solution.
2. Test to see if this is actually a solution.
3. Quit if a solution has been found.
Otherwise, return to step 1.
Generate-and-Test
Acceptable for simple problems.
Inefficient for problems with large space.
Generate-and-Test
Exhaustive generate-and-test.
Heuristic generate-and-test: not consider
Plan generate-test:
Generate-and-Test
Example: coloured blocks
Arrange four 6-sided cubes in a row, with each
side of
each cube painted one of four colours, such that on
all four
sides of the row one block face of each colour is
showing.
Generate-and-Test
Example: coloured blocks
Heuristic: if there are more red faces than other
colours
then, when placing a block with several red faces,
use few
of them as possible as outside faces.
Hill Climbing
Searching for a goal state = Climbing to the top
of a hill
Hill Climbing
Generate-and-test + direction to move.
Heuristic function to estimate how close a
given state is to a goal state.
10
11
12
13
15
16
17
18
19
Goal
A
Blocks World
20
A
D
Goal
D
C
A
Blocks World
Local heuristic:
+1 for each block that is resting on the thing it is
supposed to be resting on.
1 for each block that is resting on a wrong thing.
21
22
D
C
B
A
0
0
D
C
D
23
A
D
Goal
D
C
A
Blocks World
Global heuristic:
For each block that has the correct support structure:
+1 to
every block in the support
structure.
For each block that has a wrong support structure: 1
to
24
D
C
B
A
2
D
C
B
1
A
D
25
26
Simulated Annealing
A variation of hill climbing in which, at the
beginning of the process, some downhill
moves may be made.
27
Simulated Annealing
Physical Annealing
28
Simulated Annealing
Algorithm
1. Evaluate the initial state.
2. Loop until a solution is found or there are no new
operators left to be applied:
Best-First Search
Depth-first search: not all competing branches
having to be expanded.
30
Best-First Search
A
A
B
3
C
5
D
1
B
3
C
5
A
B
G
6
H
5
C
5
D
E
4
F
6
A
D
E
4
B
F
6
G
6
H
5
C
5
I
2
D
E
J
1
F
6
31
Best-First Search
OPEN: nodes that have been generated, but
have not examined.
32
Best-First Search
Algorithm
1. OPEN = {initial state}.
2. Loop until a goal is found or there are no nodes
left in OPEN:
33
Best-First Search
Greedy search:
34
Best-First Search
Uniform-cost search:
35
Best-First Search
Greedy search:
36
Best-First Search
Greedy search:
Uniform-cost search:
37
Best-First Search
Algorithm A* (Hart et al., 1968):
f(n) = g(n) + h(n)
h(n) = cost of the cheapest path from node n
to a
goal state.
g(n) = cost of the cheapest path from the
initial state
to node n.
38
Best-First Search
Algorithm A*:
f*(n) = g*(n) + h*(n)
h*(n) (heuristic factor) = estimate of h(n).
g*(n) (depth factor) = approximation of g(n)
found by
A* so far.
39
Problem Reduction
Goal: Acquire TV set
Goal: Steal TV set Goal: Earn some money Goal: Buy TV set
AND-OR Graphs
40
A 6
9
B
3
A 9
B
3
C
4
C
4
D
5
A 11
D 10
E
4
F
4
B 6
G
5
12
H
7
C
4
D 10
E
4
F
4
41
A 14
C 10
E 6
F 3
G 5
Necessary backward
propagation
B 13
D 5
C 15
E 6
F 3
G 10
H 9
42
Constraint Satisfaction
Many AI problems can be viewed as problems
of constraint satisfaction.
Cryptarithmetic puzzle:
SEND
MORE
MONEY
43
Constraint Satisfaction
As compared with a straightforard search
44
Constraint Satisfaction
Operates in a space of constraint sets.
Initial state contains the original constraints
given in the problem.
45
Constraint Satisfaction
Two-step process:
1. Constraints are discovered and propagated as
far as possible.
2. If there is still not a solution, then search
begins, adding new constraints.
46
Initial state:
No two letters have
the same value.
The sum of the
digits
must be as shown.
M=1
S = 8 or 9
O=0
N=E+1
C2 = 1
N+R>8
E9
SEND
MORE
MONEY
E=
2
N=3
R = 8 or 9
2 + D = Y or 2 + D = 10 + Y
C1 =
0
2+D=Y
N + R = 10 + E
R=9
S =8
C1 = 1
2 + D = 10 + Y
D=8+Y
D = 8 or 9
D=
8 Y=0
D=
9
Y=1
47
Constraint Satisfaction
Two kinds of rules:
1. Rules that define valid constraint propagation.
2. Rules that suggest guesses when necessary.
48
Homework
Exercises
Reading
Algorithm A*
(http://en.wikipedia.org/wiki/A
%2A_algorithm)
49