TSP Nearest Insertion

Problem

Build a TSP tour with the nearest-insertion heuristic. dist is a symmetric n by n distance matrix.

Start with the subtour [0, second] where second is the city closest to 0, then repeatedly pick the remaining city with the smallest distance to any tour city (ties by smallest index) and insert it into the position minimizing the length increase. Return [tour, total_length].

Hint

Insertion heuristics grow a single cycle instead of extending a path.

Test cases

case 1

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

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

case 2

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]]]

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

case 3

in: [[[0,3],[3,0]]]

expected: [[0,1],6]

Starter codePython

def tsp_nearest_insertion(dist):
    # Your code here
    pass

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