From: Ruby Quiz <james@...>
Date: 2007-10-05T22:28:17+09:00
Subject: [QUIZ] Itinerary for a Traveling Salesman (#142)

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.  Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Morton Goldberg

A salesman wants to call on his customers, each of which is located in a
different city.  He asks you to prepare an itinerary for him that will minimize
his driving miles.  The itinerary must take him to each city exactly once and
return him to his starting point. Can you write a Ruby program to generate such
an itinerary?

This problem is famous and known to be NP-complete. So how can you be expected
to solve it as a weekend Ruby Quiz project?  It's unreasonable isn't it?  Yes,
it is, unless the conditions are relaxed somewhat.

First, let's restrict the problem to a space for which the solution is known: a
grid of points as defined by the following Ruby code: 

	# Square grid (order n**2, where n is an integer > 1). Grid points are
	# spaced on the unit lattice with (0, 0) at the lower left corner and
	# (n-1, n-1) at the upper right.
	
	class Grid
	   attr_reader :n, :pts, :min
	   def initialize(n)
	      raise ArgumentError unless Integer === n && n > 1
	      @n = n
	      @pts = []
	      n.times do |i|
	         x = i.to_f
	         n.times { |j| @pts << [x, j.to_f] }
	      end
	      # @min is length of any shortest tour traversing the grid.
	      @min = n * n
	      @min += Math::sqrt(2.0) - 1 if @n & 1 == 1
	   end
	end

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).

	Genetic Algorithm (GA)

From one point of view a GA is a stochastic technique for solving an
optimization problem--for finding the extremum of a function.  From another
point of view it is applied Darwinian evolution.

To see how a GA works, let's look at some pseudocode.  

	Step 1.  Generate a random initial population of itineraries.
	Step 2.  Replicate each itinerary with some variation.
	Step 3.  Rank the population according to a fitness function.
	Step 4.  Reduce the population to a prescribed size,
	         keeping only the best ranking itineraries.
	Step 5.  Go to step 2 unless best itinerary meets an exit criterion.

Simple, isn't it? But perhaps some discussion will be useful.

Step 1.  You can get the points you need to generate a new random itinerary by
calling *pts* on an instance *grid* of the Grid class shown above.

Step 2.  GAs apply what are called *genetic operators* to replicas of the
population to produce variation.  Genetic operators are usually referred to by
biological sounding names such *mutation*, *recombination*, or *crossover*. 
Recombination means some kind of permutation.  In my GA solution of the problem
proposed here, I used two recombination operators, *exchange* and *reverse*. 
Exchange means cutting an itinerary at three points (yielding four fragments)
and swapping the middle two fragments.  Reverse means cutting an itinerary at
two points (yielding three fragments) and reversing the order of the middle
fragment.

Step 3.  The fitness function for the traveling salesman problem can be the
total distance traversed when following an itinerary (including the return to
the starting point), or it can be a related function that reaches its minimum
for exactly the same itineraries as does the total distance function.

A GA can be rather slow, but has the advantage of being easy to implement.  My
experience with problem I have proposed is that a GA can produce a solution
meeting the 5% criterion reasonably quickly and that it can find an exact
solution if given enough time.

	An Exact Solution

To give you an idea of how a solution looks when plotted, here is a picture of a
minimal tour on a 7 X 7 grid.

	*--*--*--*  *--*--*
	|        |  |     |
	*  *--*  *--*  *--*
	|  |  |        |   
	*  *  *--*--*--*  *
	|  |            / |
	*  *--*--*--*--*  *
	|                 |
	*--*  *--*--*--*  *
	   |  |        |  |
	*--*  *  *--*--*  *
	|     |  |        |
	*--*--*  *--*--*--*

This exact solution was found by my Ruby GA solver in about two minutes.

	Wikipedia Links

Two Wikipedia pages have a great deal of relevant information on the topic of
this quiz.  

	http://en.wikipedia.org/wiki/Traveling_salesman_problem

	http://en.wikipedia.org/wiki/Genetic_algorithm