Created on Jan 24th 2006
Updated on July, 16th 2006
Another algo based on the Graham Scan
Soon...
New algo in O(n log(n))
This one first creates a convex hull and
then collapses the edges. In some specific cases, I obtain very good results, in others, average, about the same
results as the algorithm described below.
Intro
Basic algorithm in O(n) + O(n^2)
Try it
tsp.jnlp Version 1.2 - a Java Web Start application ~ 92 Kb
(You might need to install the JRE 5.0 ~ 16 Mb)
Or download tsp-obf.jar and in a console type (to check you are running 1.5):
thierry-janaudys-powerbook-g4-17:~/Perso/Dev/tsp/ftp thierryjanaudy$ java -version
java version "1.5.0_05"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_05-83)
Java HotSpot(TM) Client VM (build 1.5.0_05-48, mixed mode, sharing)
Then
thierry-janaudys-powerbook-g4-17:~/Perso/Dev/tsp/ftp thierryjanaudy$ java -classpath tsp-obf.jar org.janaudy.tsp.ui.Main
You can generate a random graph, or choose an existing problem, then 'run all' in the Algorithm menu.
Random graphs can be saved then re-loaded. Problems are embedded in the distribution.
What's left?
- Finish the algorithm :-) (i.e.: add 2 heuristics that I have in mind)
- Bug fixing
- Allow to draw/save/load your own graphs
- Implement Genetic Algorithm version for fun
- I have a much better idea for the envelope - I just realized how important the impact is depending on how good the envelope is
Problems
- xqf131: solution found is 16% worse than optimal (564) (was 24% with version 1.0)
- xqg237: solution found is 18% worse than optimal (1019) (was 34% with version 1.0)
- pka379: solution found is 17% worse than optimal (1332) (was 27% with version 1.0)
- pbl395: solution found is 29% worse than optimal (1281) (was 43% with version 1.0)
My goal is to keep the algorithm generic, not specific to a specific graph
configuration, and bring down the %
External Links
Contact
thierry at janaudy dot com
