TSP Farthest Insertion

Problem

Build a TSP tour with the farthest-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 whose nearest tour city is farthest away (ties by smallest index) and insert it at the position minimizing the length increase. Return [tour, total_length].

Hint

Farthest insertion builds a robust skeleton early by inserting distant cities first.

Test cases

case 1

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

expected: [[0,2,3,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_farthest_insertion(dist):
    # Your code here
    pass

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