The three rules of Ruby Q.:
-
Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message. -
Support Ruby Q. by submitting ideas as often as you can:
- Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion. Please reply to the original quiz
message,
if you can.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
by Morton G.
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 Q. 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.
