Subscribe to Macosxnerd101's Blog        RSS Feed

Some Fun Graph Theory Research I've Been Doing

Icon 7 Comments
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!

7 Comments On This Entry

Page 1 of 1

Dogstopper Icon

19 May 2011 - 07:18 PM
Sounds cool! Can't wait to see this heuristic!

codeprada Icon

21 May 2011 - 04:08 AM
I'm with Dogstopper

macosxnerd101 Icon

21 May 2011 - 11:55 AM
I've got a lot of testing to do with my heuristic before I unveil it. My tutorial will include a Held-Karp implementation though, and hopefully a fairly straight-forward explanation. It's been tough finding a good resource on Held-Karp that actually discusses how it works, rather than information regarding its runtime. :)

AdamSpeight2008 Icon

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.

macosxnerd101 Icon

21 May 2011 - 02:25 PM
I'm not familiar with any .NET languages. If I had time to pick up C#, I would be more than willing to. :)

AdamSpeight2008 Icon

21 May 2011 - 03:43 PM
Give C# a try it's syntax and grammar is close to Java.

macosxnerd101 Icon

21 May 2011 - 04:23 PM
Once I get my college computer, I'll get .NET set up and give C# a try. :)
Page 1 of 1

May 2018

20 212223242526

Recent Entries

Search My Blog

0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)