[Boost-users] BGL Traveling Salesman Approximation

Subject: [Boost-users] BGL Traveling Salesman Approximation
From: David Doria (daviddoria_at_[hidden])
Date: 2011-06-28 17:11:06

Using the example here:
http://www.boost.org/doc/libs/1_44_0/libs/graph/test/metric_tsp_approx.cpp

I constructed this path:
http://homepages.rpi.edu/~doriad/Upload/contour.png

on these points:
http://homepages.rpi.edu/~doriad/Upload/points.png

Is this the best I can hope to do with this approximate algorithm?
(There is "clearly" (to a human) a much shorter path without all of
the overlapping edges on the lower part of the left side of the
rectangle).

The graph.txt file I used is here:
http://homepages.rpi.edu/~doriad/Upload/graph.txt

and the solution it gave was:

0 1 2 3 5 7 9 11 13 15 16 18 20 21 23 25 26 28 30 32 35 37 40 39 38 36
34 33 31 29 27 24 22 4 6 8 10 12 14 17 19 0

Is there anyway I can "fix" this solution?

Thanks,

David