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:
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?
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
Thanks for reply. Is there any other algrithms to slove this kind of issue?
The nodes are at most 1000,and no routine between some nodes, and have to
visit all nodes.
On Mar 20, 2012 7:03 AM, "Steven Watanabe"
AMDG
On 03/19/2012 10:42 PM, Jeff Wang wrote:
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?
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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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
participants (3)
-
Anders Wallin -
Jeff Wang -
Steven Watanabe