Computational Intelligence - Problems for Chapter 4 -- Solution to part (b)

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