A C implementation of the Held Karp algorithm to solve small TSP instances.
Held Karp is a dynamic programming algorithm used to effciently solve the Travelling Salesman Problem.
By applying the divide-and-conquer principle, Held Karp calculates the path cost of subsets of increasing length.
For a more detailed explanation of the algorithm check the
Wikipedia Page.
Also check the Java version.
As of now, the program does not implement any kind of heuristics and will always return the optimal path.
As it's supposed to be a proof of concept, the matrix of distances is randomly generated before the computation for a given number of cities.
This implementation makes use of multithreading to compute different iterations over city subsets of a given length.
The project comes with a Linux object (compiled with GCC from the Makefile provided).
Just download the object file, open up a terminal and type
./heldkarp.
All test were performed on a Intel Core i7 6700 @3.4Ghz - 16GB DDR4 RAM - Ubuntu 16.04 (64 bits).
23 cities: 2.482568 seconds
22 cities: 1.013295 seconds
21 cities: 0.464445 seconds
20 cities: 0.224266 seconds
19 cities: 0.105034 seconds
18 cities: 0.038902 seconds
17 cities: 0.016815 seconds
16 cities: 0.008512 seconds
15 cities: 0.004797 seconds
14 cities: 0.002704 seconds
13 cities: 0.001716 seconds
12 cities: 0.001120 seconds
11 cities: 0.000853 seconds
10 cities: 0.000689 seconds
1. Read input matrix from (.cvs)file.
2. Improved thread management.
3. Improved UI