Ex1 eng

AlgKons

APPROXIMATION OF TSP

3 problem instances for the travelling salesman problem are available at the bottom of this page. Each of the instances consists of n cities, and the first line in each file contains the integer, n, while the next n lines gives the x- and y-coordinates for each city as floating point numbers.

The goal of this exercise is to approximate an optimal TSP-tour using this scheme (and possibly extending it later on):

a) Start out by implementing the basic approximation to TSP given in the lectures: Find an MST, and traverse the tree to find a tour.

b) Try to do smart things in order to shorten the tour.

One possible thing to consider is that an optimal tour can never cross itself (can be proven with the triangle inequality). It may also be a good idea to look for better approximation algorithms on the internet.

The exercise will be handed in through programming playground, as usual, and the only problem instance we will judge is the biggest one. A tour for this problem is to be submitted as a txt-file. The file should contain one city number on each line (0-indexed), in the order you suggest to visit the cities. Note that it is possible to find software that will give the optimal solution to this problem instance, but it is not allowed to use such things in this exercise. Students who have handed in an optimal solution will be asked to provide their own code, otherwise they will be deleted from the "hall of fame".

Here as an example problem instance with 4 cities.

4
1.0 1.0
2.0 3.0
5.0 2.0
1.0 2.0

And here is an example tour:

"tur.txt":

0
1
2
3
0

(this tour has a length of 10.40, but is not optimal.)

Files

[100 cities] [500 cities] [2500 cities] [Judge] [Brett.java]

java Judge Byfil.inn [1] < file.with.a.tour

Use 1 as a parameter if you want a nice drawing of your tour. You will need Brett.java in order to compile.