|
Boost Users : |
Subject: Re: [Boost-users] Metric_TSP_approx example
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2012-03-20 10:02:49
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 list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net