Challenge I: Path planning - Deadline 14.11. 9:00 AM

PhD Luukkainen is one of the well known Finnish pop opera baritones. He is planning a tour for the summer 2012, and needs your help for getting the tour planned. As he does not like traveling during his work time, the travel distance must be as short as possible.

The tours must always start from the location identified with 0, and end in the same location. The locations are identified as integers 0...N-1, where N is the number of locations. Roads always connect two locations, but there are several locations that have no connecting roads. Each road is bidirectional, e.g. if there exists a road from 0 to X, there exists a road from X to 0 as well. Each road has a length.

The algorithm input is as follows

number_of_locations
number_of_roads
location_id another_location_id road_length
location_id another_location_id road_length
...
location_id another_location_id road_length

There exists an example input file at: http://www.cs.helsinki.fi/u/jgpyykko/200.txt

The output format for your algorithm must be as follows:

0
location_id
another_location_id
...
another_location_id
0
 

Task:

Design and implement an algorithm for figuring out PhD Luukkainen’s tour. The algorithm must plan a path that is as short as possible, but visits all locations. You can use the roads as many times as you wish, as well as visit locations several times.
Note that the tour must always start and end in location with id 0. You have to also visit each location at least once: make sure your submission contains each location.

There are several input files for which you have to submit a solution

http://www.cs.helsinki.fi/u/mikalait/map.100 (you have to get better than 15 000)
http://www.cs.helsinki.fi/u/jgpyykko/200.txt (you have to get better than 220 000)
http://www.cs.helsinki.fi/u/jgpyykko/500.txt (you have to get better than 1 300 000)
http://www.cs.helsinki.fi/u/jgpyykko/1000.txt (you have to get better than 3 000 000)
http://www.cs.helsinki.fi/u/pjmikkol/map.5000 (you need to get better than 2 000 000)
http://www.cs.helsinki.fi/u/pjmikkol/map.327 (you need to get better than 100 000)

It is ok if you submit a score to only 5 out of the 6 data files.

Material for the problem:

Book: Clever Algorithms (there's a free PDF!)
Buzzwords: Greedy Algorithm, Local Search (and k-opt), Simulated Annealing, Genetic Algorithm, Ant colony optimization, Brute-force (even though it most likely won't work, try it out!), Constraint Satisfaction Problem, Traveling Salesman problem, Tabu Search, Bees Algorithm

Reference implementation (Dummy Java code that does reading, writing, random paths and some validation.): http://www.cs.helsinki.fi/u/avihavai/pathgen.zip