TSP 2-Opt Improvement Step

Problem

Apply the single best 2-opt improvement to a closed TSP tour. dist is a symmetric n by n matrix and tour lists all n cities (the final edge closes back to tour[0]).

For every pair i < j with j >= i + 2, reversing tour[i+1..j] replaces edges (i, i+1) and (j, j+1) with (i, j) and (i+1, j+1), using cyclic indices. Choose the swap with the smallest negative delta and return the resulting tour; if no swap improves the tour, return it unchanged.

Hint

Reversing a segment only changes the two edges at its ends, so compare each delta in O(1).

Test cases

case 1

in: [[[0,1,4,5],[1,0,2,3],[4,2,0,1],[5,3,1,0]],[0,2,1,3]]

expected: [0,1,2,3]

case 2

in: [[[0,1,4,5],[1,0,2,3],[4,2,0,1],[5,3,1,0]],[0,1,2,3]]

expected: [0,1,2,3]

case 3

in: [[[0,3,4,5,2],[3,0,2,6,3],[4,2,0,1,5],[5,6,1,0,4],[2,3,5,4,0]],[0,2,1,3,4]]

expected: [0,1,2,3,4]

case 4

in: [[[0,3,4,5,2],[3,0,2,6,3],[4,2,0,1,5],[5,6,1,0,4],[2,3,5,4,0]],[0,3,1,2,4]]

expected: [0,3,2,1,4]

Starter codePython

def tsp_two_opt_step(dist, tour):
    # Your code here
    pass

4 test cases · run your code against them in the editor