Go backward to Solution to part (a)
Go up to 2 Searching on a simple graph
Go forward to Solution to part (c)
Solution to part (b)
Dynamic programming builds the following distance map to sp
|
Node | Distance |
|
SP | 0 |
|
DT | 2 |
|
KB | 4 |
|
JB | 8 |
|
MP | 8 |
|
BBY | 10 |
|
UBC | 11 |
|
KD | 11 |
|
RM | 11 |
|
AP | 14 |
|
SRY | 32
|
To get from UBC to SP,
you need to compare going via JB (with distance 3+8) with going via KD
(distance 3+11). Thus the first step is to JB. From JB, you need to
compare going via KB (distance 8), via KD (distance 15) and UBC
(distance 14) and choose KB. From KB, you choose DT and then SP.
The
final route is:
UBC -> JB -> KB -> DT -> SP
Computational
Intelligence online
material, ©David Poole, Alan Mackworth and Randy Goebel, 1999