BGL Traveling Salesman Approximation
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
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?
FWIW I am getting the exact same solution (tour length 120.54). The heuristic in BGL only guarantees a solution within 2x of the optimal solution. The 'smarter' Christofides heuristic would guarantee a solution within 1.5x of optimal. I ran metirc_tsp_approx on some of the tsplib problems a while ago: http://www.anderswallin.net/2011/05/tsp/ (I didn't investigate the O(N²*log(N)) vs. O(N²) issue any further...) Anders
participants (2)
-
Anders Wallin -
David Doria