Re: [Boost-users] Metric_TSP_approx example

Subject: Re: [Boost-users] Metric_TSP_approx example
From: Jeff Wang (cutenc2010_at_[hidden])
Date: 2012-03-20 12:01:31

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_at_[hidden]> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>