Solutions
Mid-Term
Search Methods in AI- AI3022
Q
Given the three conditions
following ** is it guaranteed
the
that algorithm will terminate with
shortest path
? Justify your answer
,
9 Branching factor is finite
by cost of each edge is
greater than .
zero
& The heuristic function untestimates the
distance to the .
goal
Ans
-
No the cost of each edge must be
,
greater
than some small constant E ,
· therwise it can gettrapped in an infinite
path with a finite cost values ,
fur example ,
with edge costs 11
tit ,
---would add
up
to
2 .
Que
what improvement does the Beam stack search *
algorithm make over the A algorithm ?
Describe the key features of the algorithm
at level
a
high .
Tree 1, AlphaBeta Algorithm
60
41 45 60
41 77 66 45 88 65 60 69
! ! !
41 12 30 77 66 13 27 45 21 88 65 15 60 60 50 69
" " " " "
41 90 52 12 70 30 80 77 60 66 67 20 13 14 15 55 27 45 99 21 22 88 97 65 70 15 66 44 60 40 60 50 28 69 80 40 11 77
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Order
Tree 1, SSS* Algorithm
60
Or 77
60
60
Values
65 60 69
30 65 60 69
10 11 12 13 14 16 15
41 90 52 12 70 30 80 77 60 66 67 20 13 14 15 55 27 45 99 21 22 88 97 65 70 15 66 44 60 40 60 50 28 69 80 40 11 77
1 2 3 4 5 6 7 8 9 Initial clusters
Order
Tree 2, AlphaBeta Algorithm
66
66 55 65
"
"
70 77 66 55 65
41 12 70 77 66 20 13 55 45 65 15 40
" " " " "
41 90 52 12 70 75 80 77 60 66 67 20 13 14 15 55 27 45 99 21 22 88 97 65 70 15 66 44 75 40 60 50 28 69 80 40 11 77
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Order
Tree 2, SSS*Algorithm
66
Or 77 66
Values
70 70 66
70 70 66 40
11 12 14 13 15 17 16 10
41 90 52 12 70 75 80 77 60 66 67 20 13 14 15 55 27 45 99 21 22 88 97 65 70 15 66 44 75 40 60 50 28 69 80 40 11 77
1 2 3 4 5 6 7 8 9 Initial clusters
Order