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" <watanabesj@gmail.com> wrote:
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