I ran my implementation of the greedy TSP algorithm and the brute-force TSP
algorithm and here is my output. I ran these algorithms on the first
`n` cities in miles.dat for `n`
ranging from 4 through 15. The brute-force algorithm became too slow after
`n` = 15.
The first two lines of each output contain the greedy tour and the cost of the
greedy tour. The remaining lines pertain to the brute-force algorithm; the output
shows instances of base cases in which encountered a cheaper tour.
You can see how the tour returned by the brute-force algorithm is always
cheaper than the greedy tour.

3 2 1 0 4 cities. The cost of the greedy tour is 6944.0 Base case. Tour cost is 4603.0 0 1 3 2 4 cities. The cost of the optimal tour is 4603.0 ------------------------ 4 3 2 1 0 5 cities. The cost of the greedy tour is 5724.0 Base case. Tour cost is 4720.0 0 1 3 2 4 5 cities. The cost of the optimal tour is 4720.0 ------------------------ 4 5 1 3 2 0 6 cities. The cost of the greedy tour is 6009.0 Base case. Tour cost is 4992.0 0 1 3 2 4 5 6 cities. The cost of the optimal tour is 4992.0 ------------------------ 4 5 1 6 3 2 0 7 cities. The cost of the greedy tour is 6621.0 Base case. Tour cost is 6327.0 Base case. Tour cost is 6230.0 Base case. Tour cost is 5604.0 Base case. Tour cost is 5503.0 0 5 3 2 4 6 1 7 cities. The cost of the optimal tour is 5503.0 ------------------------ 7 6 1 5 4 3 2 0 8 cities. The cost of the greedy tour is 6381.0 Base case. Tour cost is 6137.0 Base case. Tour cost is 6075.0 Base case. Tour cost is 4874.0 0 1 6 7 3 2 4 5 8 cities. The cost of the optimal tour is 4874.0 ------------------------ 7 6 1 5 4 3 2 8 0 9 cities. The cost of the greedy tour is 5472.0 Base case. Tour cost is 5372.0 Base case. Tour cost is 5239.0 Base case. Tour cost is 5177.0 Base case. Tour cost is 4549.0 0 8 2 3 4 6 7 1 5 9 cities. The cost of the optimal tour is 4549.0 ------------------------ 9 5 3 4 6 7 1 0 2 8 10 cities. The cost of the greedy tour is 6311.0 Base case. Tour cost is 6244.0 Base case. Tour cost is 6000.0 Base case. Tour cost is 5336.0 Base case. Tour cost is 4981.0 Base case. Tour cost is 4915.0 Base case. Tour cost is 4387.0 Base case. Tour cost is 4287.0 0 8 2 3 4 6 7 1 9 5 10 cities. The cost of the optimal tour is 4287.0 ------------------------ 9 5 10 3 4 6 7 1 0 2 8 11 cities. The cost of the greedy tour is 6338.0 Base case. Tour cost is 5783.0 Base case. Tour cost is 5413.0 Base case. Tour cost is 4742.0 0 8 2 3 10 5 4 6 7 1 9 11 cities. The cost of the optimal tour is 4742.0 ------------------------ 11 10 3 4 2 7 6 1 5 9 8 0 12 cities. The cost of the greedy tour is 6986.0 Base case. Tour cost is 6901.0 Base case. Tour cost is 6634.0 Base case. Tour cost is 6588.0 Base case. Tour cost is 6471.0 Base case. Tour cost is 5714.0 Base case. Tour cost is 5611.0 Base case. Tour cost is 5425.0 Base case. Tour cost is 5337.0 Base case. Tour cost is 4957.0 Base case. Tour cost is 4396.0 0 8 2 3 10 11 1 7 6 4 5 9 12 cities. The cost of the optimal tour is 4396.0 ------------------------ 11 10 3 2 4 12 7 6 1 5 9 8 0 13 cities. The cost of the greedy tour is 7271.0 Base case. Tour cost is 6969.0 Base case. Tour cost is 6702.0 Base case. Tour cost is 6565.0 Base case. Tour cost is 6454.0 Base case. Tour cost is 6232.0 Base case. Tour cost is 6130.0 Base case. Tour cost is 5836.0 Base case. Tour cost is 5818.0 Base case. Tour cost is 5798.0 Base case. Tour cost is 5632.0 Base case. Tour cost is 5441.0 Base case. Tour cost is 5255.0 Base case. Tour cost is 5025.0 Base case. Tour cost is 4464.0 0 8 2 3 10 11 1 7 6 12 4 5 9 13 cities. The cost of the optimal tour is 4464.0 ------------------------ 11 10 3 2 4 12 13 7 6 1 5 9 8 0 14 cities. The cost of the greedy tour is 9077.0 Base case. Tour cost is 9013.0 Base case. Tour cost is 8618.0 Base case. Tour cost is 8570.0 Base case. Tour cost is 8513.0 Base case. Tour cost is 8303.0 Base case. Tour cost is 8189.0 Base case. Tour cost is 8166.0 Base case. Tour cost is 8119.0 Base case. Tour cost is 7939.0 Base case. Tour cost is 7885.0 Base case. Tour cost is 7684.0 Base case. Tour cost is 7648.0 Base case. Tour cost is 7594.0 Base case. Tour cost is 7416.0 Base case. Tour cost is 7258.0 Base case. Tour cost is 7246.0 Base case. Tour cost is 7158.0 Base case. Tour cost is 6964.0 Base case. Tour cost is 6819.0 Base case. Tour cost is 6587.0 Base case. Tour cost is 6485.0 Base case. Tour cost is 6458.0 Base case. Tour cost is 6301.0 Base case. Tour cost is 5848.0 0 8 2 4 5 9 1 7 6 12 3 10 11 13 14 cities. The cost of the optimal tour is 5848.0 ------------------------ 11 10 3 4 2 13 7 6 1 5 9 8 0 12 14 15 cities. The cost of the greedy tour is 9695.0 Base case. Tour cost is 9440.0 Base case. Tour cost is 9428.0 Base case. Tour cost is 9399.0 Base case. Tour cost is 9071.0 Base case. Tour cost is 8815.0 Base case. Tour cost is 8696.0 Base case. Tour cost is 8593.0 Base case. Tour cost is 8372.0 Base case. Tour cost is 8125.0 Base case. Tour cost is 8122.0 Base case. Tour cost is 8011.0 Base case. Tour cost is 7831.0 Base case. Tour cost is 7777.0 Base case. Tour cost is 7757.0 Base case. Tour cost is 7441.0 Base case. Tour cost is 7429.0 Base case. Tour cost is 7121.0 Base case. Tour cost is 7104.0 Base case. Tour cost is 6833.0 Base case. Tour cost is 6614.0 Base case. Tour cost is 6484.0 Base case. Tour cost is 6031.0 0 8 2 4 5 9 1 7 6 12 3 10 11 13 14 15 cities. The cost of the optimal tour is 6031.0 ------------------------