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.
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