This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
This question is from the 1997/98 G5BAIM (Artificial Intelligence Methods Examination). It formed part of question 1 (part b) and was worth 16 of the 25 marks available. Although this question is from G5BAIM it is still applicable to G5AIAI (Introduction to Artificial Intelligence) as this part of the course (heuristic search) is now part of G5AIAI and not G5BAIM.
You should attempt this question and keep the answers to hand when you attempt the self assessment for this part of the course as you may be asked questions relating to this question.
Consider the following map
Using the A* algorithm work out a route from town A to town M. Use the following
cost functions.
Provide the search tree for your solution and indicate the order in which you
expanded the nodes. Finally, state the route you would take and the cost of
that route.
|
A
|
223
|
E
|
165
|
I
|
100
|
M
|
0
|
|
B
|
222
|
F
|
136
|
J
|
60
|
|
|
|
C
|
166
|
G
|
122
|
K
|
32
|
|
|
|
D
|
192
|
H
|
111
|
L
|
102
|
|
|
This table was not past of the exam question but is given in case you have trouble reading and/or printing the diagram above. It shows the distances between towns A thru M. Note that the distances are symmetric.
|
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
M
|
| A |
|
36
|
61
|
|
|
|
|
|
|
|
|
|
|
| B |
|
|
|
31
|
|
|
|
|
|
|
|
|
|
| C |
|
|
|
32
|
|
31
|
|
|
|
|
|
80
|
|
| D |
|
|
|
|
52
|
|
|
|
|
|
|
|
|
| E |
|
|
|
|
|
|
43
|
|
|
|
|
|
|
| F |
|
|
|
|
|
|
|
|
|
122
|
112
|
|
|
| G |
|
|
|
|
|
|
|
20
|
|
|
|
|
|
| H |
|
|
|
|
|
|
|
|
40
|
|
|
|
|
| I |
|
|
|
|
|
|
|
|
|
45
|
|
|
|
| J |
|
|
|
|
|
|
|
|
|
|
36
|
|
|
| K |
|
|
|
|
|
|
|
|
|
|
|
|
32
|
| L |
|
|
|
|
|
|
|
|
|
|
|
|
102
|
| M |
|
|
|
|
|
|
|
|
|
|
|
|
0
|
Last Updated : 15 Sep 2001