CGAL users discussion list

["Andy Hirsh" <>]

Hi Bernd

 I'm looking just now at the TSP problem you point me...

 thanks a lot for your help and for the great job you all are doing with CGAL

            Andy

On 4/7/08, Bernd Gaertner 
<>
 wrote:
> Andy Hirsh wrote:
> > for an optimization algorithm I would like to know if there is a way
> > to evaluate the minimum path along some (eg 1000) vectors using
> > CGAL...  all vectors need to be traversed only once,  I can
> > change the directions of vectors and I can also add some "jump
> > vectors" if needed...
>
> It seems that you are talking about a variant of the traveling
> salesperson problem (TSP) which is notoriously difficult even for small
> inputs, and in two dimensions. As a CGAL editor, I'm flattered that you
> consider CGAL a possible source of solutions, but I'm afraid that this
> is beyond the scope of CGAL. I throught a little bit about whether the
> flexibility of changing vector orientations makes the problem easy in
> some miraculous way, but I could not think of anything.
>
> There are reasonable heuristics for TSP, some of them even with
> approximation guarantees (see for example
> http://en.wikipedia.org/wiki/Traveling_salesman_problem); you might want
> to try some of them, and then CGAL might come handy to do certain basic
> computations.
>
> Best,
> Bernd.
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>