Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] path optimization

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] path optimization


Chronological Thread 
  • From: "Andy Hirsh" <>
  • To:
  • Subject: Re: [cgal-discuss] path optimization
  • Date: Mon, 7 Apr 2008 15:31:14 +0200
  • Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=IhUwo0Qwru/99WWarTfGKcAugRWrrEe5rEAxV+jEEAsv1JL8FCx4gQ/FZ9LovDMRYQMx8ZkFNSBaKOF4eDSDdqRRyn08/xo6TC0SeZ/qfpjSAoSRQDULLLrFuIm4ht30wUkE7rAoXTGLFoButAkU7PLsQLENZQzXoDQxVkJdYQ0=

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
>



Archive powered by MHonArc 2.6.16.

Top of Page