Math $315$ Homework $16-$ Dynamic Programming: Travelling Salesperson

$1.$ While on holiday, a family wants to visit five sites in Wisconsin: the Milwaukee Art Museum

$($M$),$ Lambeau Field $($L$),$ the Wisconsin State Capitol $($W$),$ Bayfield Maritime Museum $($B$)$

and Grandad Bluff $($G$)$ in La Crosse. In order to save gas, they want the shortest route

between these sites. The table below indicates the distances between pairs of places:

M L W B G

M $11778368211$

L $117136276199$

W $78136324146$

B $368276324267$

G $211199146267$

The family flies into General Mitchell Airport so will start their trip by visiting the Milwaukee

Art Museum.

What is the shortest tour between these places and how far will they drive?

This is the overall aim of the travelling salesperson problem. For this homework problem,

however, you are to use the backwards recursion of dynamic programming to determine the

values for only some of the states.

The stages correspond to the different sites visited, starting at M$.$ The states in each of

stages are:

Stage $0$ Stage $1$ Stage $2$ Stage $3$ Stage $4$ Stage $5$

$($L$,\{$M$\})($B$,\{$M$,$ L$\})($W$,\{$M$,$ B$,$ L$\})($G$,\{$M$,$ B$,$ L$,$ W$\})$

$($W$,\{$M$,$ L$\})($B$,\{$M$,$ L$,$ W$\})$

$($G$,\{$M$,$ L$\})($G$,\{$M$,$ L$,$ W$\})$

$($W$,\{$M$\})($B$,\{$M$,$ W$\})($G$,\{$M$,$ B$,$ W$\})($L$,\{$M$,$ B$,$ G$,$ W$\})$

M $($G$,\{$M$,$ W$\})($B$,\{$M$,$ G$,$ W$\})($M$,\{$M$,$ L$,$ W$,$ B$,$ G$\})$

$($L$,\{$M$,$ W$\})($L$,\{$M$,$ B$,$ W$\})$

$($B$,\{$M$\})($L$,\{$M$,$ B$\})($G$,\{$M$,$ B$,$ L$\})($W$,\{$M$,$ B$,$ G$,$ L$\})$

$($G$,\{$M$,$ B$\})($L$,\{$M$,$ B$,$ G$\})$

$($W$,\{$M$,$ B$\})($W$,\{$M$,$ B$,$ G$\})$

$($G$,\{$M$\})($L$,\{$M$,$ G$\})($W$,\{$M$,$ G$,$ L$\})($B$,\{$M$,$ G$,$ L$,$ W$\})$

$($W$,\{$M$,$ G$\})($L$,\{$M$,$ G$,$ W$\})$

$($B$,\{$M$,$ G$\})($B$,\{$M$,$ G$,$ L$\})$

$($a$)$ Explain the meaning of the first state $($B$,\{$M$,$ L$\})$ in Stage $2.$

$($b$)$ Using backwards recursion so beginning with Stage $4,$ fill in the table to give the value

of V$4(,\{$M$,$ i$,$ j$,$ k$\})$ for each of the states in Stage $4$ and identify the destination.

Stage $4$

State V$4(,\{$M$,$ i$,$ j$,$ k$\})$ Destination

$($G$,\{$M$,$ B$,$ L$,$ W$\})$

$($L$,\{$M$,$ B$,$ G$,$ W$\})$

$($W$,\{$M$,$ B$,$ G$,$ L$\})$

$($B$,\{$M$,$ G$,$ L$,$ W$\})$

$($c$)$ Now use backwards recursion again to determine V$3($k$,\{$M$,$ i$,$ j$\})$ for the two indicated

states and fill in the table, including the optimal destination from each of these states.

Stage $3$

State V$3($k$,\{$M$,$ i$,$ j$\})$ Destination

$($W$,\{$M$,$ B$,$ L$\})$

$($G$,\{$M$,$ B$,$ L$\})$

$($d$)$ Use backwards recursion one more time to determine the value of V$2($B$,\{$M$,$ L$\})$ and

identify the optimal destination from this state.

Stage $2$

State V$2($j$,\{$M$,$ i$\})$ Destination

$($B$,\{$M$,$ L$\})$

$($e$)$ Identify the shortest route from $($B$,\{$M$,$ L$\})$ to the terminus $($M$,\{$M$,$ B$,$ G$,$ L$,$ W$\})$ and

state how many miles it is$.$