Traveling salesman problem

Question

Consider the traveling salesman problem with five cities. The cities are called $\text{A,}$ $\text{B,}$ $\text{C,}$ $\text{D,}$ and $\text{E}$. Here is the mileage chart for the cities. $$\begin{array}{|r|r|r|r|r|} \hline & \text{A} & \text{B}\phantom{|} & \text{C}\phantom{|} & \text{D}\phantom{|} & \text{E}\phantom{|s} \\ \hline \text{A} & & 185 & 119 & 152 & 133\phantom{|} \\ \hline \text{B} & & & 121 & 150 & 200\phantom{|} \\ \hline \text{C} & & & & 174 & 120\phantom{|} \\ \hline \text{D} & & & & & 199\phantom{|} \\ \hline \text{E} & \\ \hline \end{array}$$ $(\text{a})$ Complete the chart.
$(\text{b})$ Start at city $\text{A}$ and use the greedy algorithm to find a cycle. The length of the cycle should be $\phantom{..w}773$.
$(\text{c})$ Start at city $\text{B}$ and use the greedy algorithm to find a cycle $(722)$. Explain why this gives a$\phantom{..o}$cycle starting at $\text{A}$.
$(\text{d})$ Repeat the previous questions using city $\text{C}$, city $\text{D}$, and city $\text{E}$ as starting points.
$(\text{e})$ What is the shortest cycle you have found? (It should be $722$).
$(\text{f})$ Find a cycle whose length is $676$.

I got the answers from $(\text{a})$-$(\text{e})$ but the last one stumped me. Is there a cycle with length $676$? How would you find it? Also on $(\text{c})$, what does it mean to explain why this gives a cycle starting at $\text{A}$?

Answer 1

For the last part you need to search through the distance matrix for five distinct numbers that sum to 676 (one from each column, and no value of 0, so each city is visited). You can do this by eye, or a simple computer search and find these distances work:

{152, 121, 120, 150, 133}

These distances correspond to the path: $A \to E \to C \to B \to D \to A$ (and "rotations" of this path... i.e., starting at different cities).

---

Mathematica code:

adjacency = {{0, 185, 119, 152, 133}, 
             {185, 0, 121, 150, 200}, 
             {119, 121, 0, 174, 120}, 
             {152, 150, 174, 0, 199}, 
             {133, 200, 120, 199, 0}};

   Select[Tuples[adjacency], Total[#] == 676 && ! MemberQ[#, 0] &]

(*

{{152, 121, 120, 150, 133}, {133, 150, 121, 152, 120}}

*)