The Traveling Salesman Problem (TSP) looks for a tour or Hamiltonian cycle of minimum weight in a complete weighted graph G. A special case is the Euclidean TSP, where the (non-negative) edge costs satisfy the triangle inequality, e.g. when the vertices correspond to points in the plane and the edge costs correspond to the (Euclidean) distance between two points.

TSP is an intractable problem, meaning that in practice there is no efficient (i.e. polynomial-time) algorithm to find an optimal tour. In practice therefore, algorithms for TSP try to find a short tour, i.e. an approximation of an optimal tour.

A simple greedy approach starts in an arbitrary vertex v, starts a path containing the smallest-weight edge from v, and then continuously extends this path by appending the smallest-weight edge from the last vertex on the path to an unvisited vertex, until all vertices have been visited. Finally the path is closed to a cycle by adding the edge from the last vertex on the path to the start vertex v.

Assignment

Write a Python-function greedyTSP that takes a filename as parameter. The file contains the coordinates of a set of points in the plane, each line having x- and y-coordinate for a point. For this set of points, it builds the distance matrix, containing for each pair of points the Euclidean distance between the points. This represents a complete graph with vertices i, numbered from 0 to n-1 (where n is the number of points) and edge weights w(i,j) the distance between points p_i and p_j. Then it applies the above greedy algorithm, starting from vertex 0, to obtain a short tour in the graph. The tour is returned as a list of vertices.

Example

In the example below we assume that the file data15_2.txt¹ is in the current directory.

>>> greedyTSP("data15_2.txt")
[0, 3, 6, 10, 2, 7, 5, 9, 12, 14, 8, 13, 1, 11, 4, 0]