As some of you may already be aware, I've been working on and off for the past couple months to develop a heuristic for solving the travelling salesman problem. The point of the TSP is to find the optimal Hamiltonian circuit in a Graph. A couple days ago, I finished my implementation (after finally getting some time to actually code the thing) and it finds a Hamiltonian cycle! For the graph pictured here, it actually finds the solution to the TSP! Do I have more testing to do with different Graphs? Absolutely.
Currently, I'm working on implementing the Held-Karp algorithm, which is the current best solution, having a time complexity of O(n^2 * 2^n) and finding a Hamiltonian circuit that is 99.5% optimal. Once I get that going, I will have a point of comparison. For small graphs, I can solve the TSP by hand. As they grow in size though, having a Held-Karp implementation will be a nice control.
Be warned- a tutorial introducing Hamiltonian circuits to follow!
Currently, I'm working on implementing the Held-Karp algorithm, which is the current best solution, having a time complexity of O(n^2 * 2^n) and finding a Hamiltonian circuit that is 99.5% optimal. Once I get that going, I will have a point of comparison. For small graphs, I can solve the TSP by hand. As they grow in size though, having a Held-Karp implementation will be a nice control.
Be warned- a tutorial introducing Hamiltonian circuits to follow!
7 Comments On This Entry
Page 1 of 1
AdamSpeight2008
21 May 2011 - 01:31 PM
Would you consider writing an Extension Method for the GrapheNet Library? Even though though a large chunk of the codebase is written using Nemerle, and extension could in any .net language.
Page 1 of 1
← January 2021 →
S | M | T | W | T | F | S |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
My Blog Links
Recent Entries
Recent Comments
Search My Blog
2 user(s) viewing
2 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)