Solve the traveling salesman problem by enumeration if \(n = 4\) and the cost \(c_{ij}\) is given in the following matrix: \[\begin{bmatrix}- & 1 & 8 & 11\\16 & - & 3 & 6\\4 & 9 & - & 11\\8 & 3 & 2 & -\end{bmatrix}\]
| Order | Total cost |
|---|---|
| 1 2 3 4 1 | 1 + 3 + 11 + 8 = 23 |
| 1 2 4 3 1 | 1 + 6 + 2 + 4 = 13 |
| 1 3 2 4 1 | 8 + 9 + 6 + 8 = 31 |
| 1 3 4 2 1 | 8 + 11 + 3 + 16 = 38 |
| 1 4 2 3 1 | 11 + 3 + 3 + 4 = 21 |
| 1 4 3 2 1 | 11 + 2 + 9 + 16 = 38 |
| 2 1 3 4 2 | 16 + 8 + 11 + 3 = 38 |
| 2 1 4 3 2 | 16 + 11 + 2 + 9 = 38 |
| 2 3 1 4 2 | 3 + 4 + 11 + 3 = 21 |
| 2 3 4 1 2 | 3 + 11 + 8 + 1 = 23 |
| 2 4 1 3 2 | 6 + 8 + 8 + 9 = 31 |
| 2 4 3 1 2 | 6 + 2 + 4 + 1 = 13 |
| 3 1 2 4 3 | 4 + 1 + 6 + 2 = 13 |
| 3 1 4 2 3 | 4 + 11 + 3 + 3 = 21 |
| 3 2 1 4 3 | 9 + 16 + 11 + 2 = 38 |
| 3 2 4 1 3 | 9 + 6 + 8 + 8 = 31 |
| 3 4 1 2 3 | 11 + 8 + 1 + 3 = 23 |
| 3 4 2 1 3 | 11 + 3 + 16 + 8 = 38 |
| 4 1 2 3 4 | 8 + 1 + 3 + 11 = 23 |
| 4 1 3 2 4 | 8 + 8 + 9 + 6 = 31 |
| 4 2 1 3 4 | 3 + 16 + 8 + 11 = 38 |
| 4 2 3 1 4 | 3 + 3 + 4 + 11 = 21 |
| 4 3 1 2 4 | 2 + 4 + 1 + 6 = 13 |
| 4 3 2 1 4 | 2 + 9 + 16 + 11 = 38 |
So there are four permutations that give the same minumum cost of 13:
Upon closer inspection they’re rotations of the same ordering.