29 Jun
2011
29 Jun
'11
12:48 p.m.
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