Hello, I am looking at metric_tsp_approx.cpp example file to test the TSP issue. My vertex points: 0(0.68,2.72),1(1.69,1.13),2(2.78,2.29),3(1.02,2.47),4(0.83,0.71),5(2.59,0.52) 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? Also, I do not want to have the result like connecting vertex 2 and 4, so I added a larger edge_weight value, say 1000.0 between 2 and 4, but the result is the same as that of genneral vertext distance weight, how could I make the tsp tour does not go from 2 to 4? Thanks, Jeff
AMDG On 03/19/2012 10:42 PM, Jeff Wang wrote:
It could be. metric_tsp_approx is only an approximation.
Also, I do not want to have the result like connecting vertex 2 and 4, so I added a larger edge_weight value, say 1000.0 between 2 and 4,
That violates the preconditions of the algorithm. metric_tsp_approx requires the triangle inequality to hold.
but the result is the same as that of genneral vertext distance weight, how could I make the tsp tour does not go from 2 to 4?
It isn't possible. Just determining whether a graph contains a tour is NP-complete. In Christ, Steven Watanabe
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
participants (3)
-
Anders Wallin -
Jeff Wang -
Steven Watanabe