20 Mar
2012
20 Mar
'12
8:55 p.m.
The metric_tsp_approx_tour give the result: 0,3,1,2,4,5,0. I think 0,3,1,2,5,4,0 is better than the previous result, am I wrong?
It could be. metric_tsp_approx is only an approximation.
the algorithm in metric_tsp_approx ensures a tour which is at most twice the length of the optimal tour. I ran it on a few of the TSPLIB datasets, and in practice the results seem to cluster around 1.4-times the optimal tour length. http://www.anderswallin.net/wp-content/uploads/2011/05/tsp_on_i71.png The Christofides heuristic would guarantee guarantees a tour at most 1.5x the optimal tour. That requires a minimum weight perfect matching algorithm. Anders