Use local search on the travelling-salesman problem.
What to build
A program that improves a round trip through n cities with 2-opt moves until none helps.
Requirements
- The tour starts as
0 1 2 … n−1and returns to 0. Each step tries every reversal of positions i..j (1 ≤ i < j ≤ n − 1) and takes the one giving the shortest tour (ties: smallest i, then smallest j), only if it is strictly shorter. - Print
start: length L, then each move asreverse I-J: length L, thenfinal tour: …(ending with 0) with(length L).
Input
Line 1: n. Then n lines of the symmetric distance matrix.
Output
The start line, one line per move, and the final line.
Constraints
2 ≤ n ≤ 12; distances are whole numbers.
Example
Input:
4
0 3 1 2
3 0 2 1
1 2 0 1
2 1 1 0
Output:
start: length 8
reverse 1-2: length 6
final tour: 0 2 1 3 0 (length 6)
Why it works
Reversing a stretch of the tour swaps two roads for two others, which untangles crossings; repeating the best such swap reaches a tour no single reversal can shorten.
Examples
4 0 3 1 2 3 0 2 1 1 2 0 1 2 1 1 0
start: length 8 reverse 1-2: length 6 final tour: 0 2 1 3 0 (length 6)
3 0 4 5 4 0 6 5 6 0
start: length 15 final tour: 0 1 2 0 (length 15)
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
A move reverses the cities at positions i to j of the tour (1 ≤ i < j ≤ n − 1), so city 0 stays first.
Hint 2
Each step, compute the length after every possible reversal and take the shortest, only if it is shorter than now.
Solution
Show one correct solution (try it yourself first)
n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]
def length(tour):
return sum(d[tour[k]][tour[(k + 1) % n]] for k in range(n))
tour = list(range(n))
current = length(tour)
print(f"start: length {current}")
while True:
best, move = current, None
for i in range(1, n - 1):
for j in range(i + 1, n):
trial = tour[:i] + tour[i:j + 1][::-1] + tour[j + 1:]
if length(trial) < best:
best, move = length(trial), (i, j)
if move is None:
break
i, j = move
tour = tour[:i] + tour[i:j + 1][::-1] + tour[j + 1:]
current = best
print(f"reverse {i}-{j}: length {current}")
print(f"final tour: {' '.join(map(str, tour + [0]))} (length {current})")