AI: Shorten a tour with 2-opt

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−1 and 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 as reverse I-J: length L, then final 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

Example 1 · Input
4
0 3 1 2
3 0 2 1
1 2 0 1
2 1 1 0
Expected output
start: length 8
reverse 1-2: length 6
final tour: 0 2 1 3 0 (length 6)
Example 2 · Input
3
0 4 5
4 0 6
5 6 0
Expected output
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})")

Lesson: Local search and optimization →