awardofsky/held-karp

A Java implementation of the Held Karp algorithm.

Held-Karp

A Java implementation of the Held Karp algorithm.

Algorithm:

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.
The core algorithm was based on the following Python port.

As of now, the program does not implement any kind of heuristics and will always return the optimal path.

How to use:

This project comes with a executable jar file, which you can run in a command line/prompt by typing:
java -jar HeldKarp.jar

Notes:
1. The program can be quite memory hungry for computations with over 20 cities,
remember to allocate more memory to the jar execution if needed.
2. If you have a 64 bits JRE, you can run the program with the flag -d64 to boost performance in 64 bit machines.

Example command: java -d64 -Xmx4096m -Xms4096m -jar HeldKarp.jar

Benchmarks:

All test were done on a Intel Core i7 6700 @3.4Ghz - 16GB DDR4 RAM - Windows 10 (64 bits).

23 cities: 28.428 seconds
22 cities: 11.909 seconds
21 cities: 5.451 seconds
20 cities: 2.371 seconds
19 cities: 1.029 seconds
18 cities: 309.666 milliseconds
17 cities: 106.951 milliseconds
16 cities: 62.438 milliseconds
15 cities: 27.893 milliseconds
14 cities: 12.631 milliseconds
13 cities: 3.994 milliseconds
12 cities: 1.379 milliseconds
11 cities: 529.427 microseconds
10 cities: 238.574 microseconds

To be Implemented:

1. Read input matrix from file.
2. Memory overflow detection.