From: James Edward Gray II <james@...>
Date: 2007-10-07T05:57:37+09:00
Subject: Re: [QUIZ] Itinerary for a Traveling Salesman (#142)

On Oct 6, 2007, at 3:05 PM, Eric Mahurin wrote:

> On 10/5/07, Ruby Quiz <james@grayproductions.net> wrote:
>> Second, let's relax the requirement that the itinerary be truly  
>> minimal. Let's
>> only require that it be nearly minimal, say, within 5%. Now you  
>> can tackle the
>> problem with one of several heuristic optimization algorithms  
>> which run in
>> polynomial time.  In particular, you could use a genetic algorithm  
>> (GA).
>
> As far as I know, a genetic algorithm isn't going to guarantee any
> approximation factor (within 1.05 of optimal as suggested above),
> right?

Genetic algorithms don't guarantee the solution, that's correct.  But  
it's pretty easy to get one working reasonably well for this.

James Edward Gray II