Our solution to the Traveling Salesperson 2D problem on Kattis (oldkattis:tsp), as part of the course DD2440 Advanced Algorithms at KTH.

See below for the full problem statement.

Your program should take as input a single TSP instance. It will be run several times, once for every test case. The time limit is per test case.

The first line of standard input contains an integer $1 \le N \le 1000$, the number of points. The following $N$ lines each contain a pair of real numbers $x$, $y$ giving the coordinates of the $N$ points. All numbers in the input have absolute value bounded by $10^6$.

The distance between two points is computed as the Euclidean distance between the two points, rounded to the nearest integer.

Standard output should consist of $N$ lines, the $i$'th of which should contain the (0-based) index of the $i$'th point visited.

Let $Opt$ be the length of an optimal tour, $Val$ be the length of the tour found by your solution, and $Naive$ be the length of the tour found by the algorithm below. Define $x = (Val - Opt)/(Naive - Opt)$. (In the special case that $Naive = Opt$, define $x = 0$ if $Val = Opt$, and $x = \infty$ if $Val > Opt$.)

The score on a test case is $0.02^x$. Thus, if your tour is optimal, you will get $1$ point on this test case. If your score is halfway between $Naive$ and $Opt$, you get roughly $0.14$ points. The total score of your submission is the sum of your score over all test cases. There will be a total of $50$ test cases. Thus, an implementation of the algorithm below should give a score of at least $1$ (it will get $0.02$ points on most test cases, and $1.0$ points on some easy cases where it manages to find an optimal solution).

The algorithm giving the value $Naive$ is as follows:

GreedyTour
   tour[0] = 0
   used[0] = true
   for i = 1 to n-1
      best = -1
      for j = 0 to n-1
         if not used[j] and (best = -1 or dist(tour[i-1],j) < dist(tour[i-1],best))
            best = j
      tour[i] = best
      used[best] = true
   return tour

The sample output gives the tour found by GreedyTour on the sample input. The length of the tour is 323.

10
95.0129 61.5432
23.1139 79.1937
60.6843 92.1813
48.5982 73.8207
89.1299 17.6266
76.2097 40.5706
45.6468 93.5470
1.8504 91.6904
82.1407 41.0270
44.4703 89.3650

0
8
5
4
3
9
6
2
1
7