Artificial Intelligence
Lecture 16
Beam Search
Muhammad Umar Farooq
Local Search
• Hill climbing
• Beam search
• Genetic algorithm
S
9
A 11 B
7.3 8.5 8 7.1 9
C D E F G
6 5 7 J 5.3 K
H I
2 0 4 3
L M N o
8 Puzzle problem using Hill climbing
1 2 4 1 4 7
5 7 2 5 8
3 6 8 3 6
Initial state final state
h1 = the number of misplaced tiles.
h1 is an admissible heuristic because it is clear that any tile that is out of place
must be moved at least once.
Weaknesses of Hill climbing search
• Local maxima or local minima:
– A state which is better than all of it’s neighbors
but not better than some other state which is not
directly connected to that state.
• Plateau
– A flat area of the search space in which all
neighboring states have same values
• Ridges
– Creating a sequence of local maxima but all of
them are not directly connected
Solution of hill climbing weaknesses
• Random initialization of starting state
• jump
Local Search
• Hill climbing
• Beam search
• Genetic algorithm
Beam Search
• Type of local search
• keeps track of k states rather than just one
• all the successors of all k states are generated.
If any one is a goal, the algorithm halts.
Otherwise, it selects the k best successors
from the complete list and repeats.
• Overcome the weaknesses of hill climbing
search
• It will also use Heuristic value
K=2 S
9
A 11 B
7.3 8.5 8 7.1 9
C D E F G
6 5 7 J 5.3 K
H I
2 0 4 3
L M N o
K=2 S
9
A 11 B
K=2 S
9
A 11 B
S
9
A 11 B
7.1
7.3 8.5 8 9 G
C D E F
S
9
A 11 B
7.1
7.3 8.5 8 9 G
C D E F
6 5 7 J 5.3 K
H I
S
9
A 11 B
7.1
7.3 8.5 8 9 G
C D E F
6 5 7 J 5.3 K
H I
2 0 4 3
L M N o
S
9
A 11 B
7.1
7.3 8.5 8 9 G
C D E F
6 5 7 J 5.3 K
H I
2 0 4 3
L M N o
S
9
A 11 B
7.1
7.3 8.5 8 9 G
C D E F
6 5 7 J 5.3 K
H I
2 0 4 3
L M N o
Beam Search
• Type of local search
• keeps track of k states rather than just one
• all the successors of all k states are generated.
If any one is a goal, the algorithm halts.
Otherwise, it selects the k best successors
from the complete list and repeats.
• Try to overcome the weaknesses of hill
climbing search
• It will also use Heuristic value
S
9
A 11 B
7.3 8.5 8 9 9
C D E F G
6 5 7 J 6 K
H I
2 0 4 4
L M N o
S
9
A 11 B
7.3 8.5 8 9 9
C D E F G
6 5 7 J 6 K
H I
2 0 4 4
L M N o
S
9
A 11 B
7.3 8.5 8 9 9
C D E F G
6 5 7 J 6 K
H I
2 0 4 4
L M N o
S
9
A 11 B
7.3 8.5 8 9 9
C D E F G
6 5 7 J 6 K
H I
2 0 4 4
L M N o
S
9
A 11 B
7.3 8.5 8 9 9
C D E F G
6 5 7 J 6 K
H I
2 0 4 4
L M N o
Stochastic beam search
• Instead of choosing the best k nodes from the
pool of candidate successors, stochastic beam
search chooses k successors at random
Heuristic value table
D Straight line distance
25
7 A 40
A 18
14 F B 32
11
10 20 C 25
C
B D 35
15 E 19
8
G
F 17
E 9 H 10
10
G 0
H
Initial state =A
Goal state=G
heuristic=Straight line distance= (𝑥1 − 𝑥2 )2 +(𝑦1 − 𝑦2 )2
Local Search
• Hill climbing
• Beam search
• Genetic algorithm
Genetic algorithm
• Inspired from Biological evolution
• We will find approximate solution
• It is a variant of stochastic beam search
– successor states are generated by combining two
parent states
Thank you
Any question ?
