 |
|
| |
[ Pobierz całość w formacie PDF ]
cost of the cycle (the sum of the costs of its edges) is as small as possible.
This problem is one of the most important in the area of combinatorial optimization,
the field dealing with finding the best possible design in various combinatorial situations,
like finding the optimal tree discussed in the previous section. It is called the Travelling
Salesman Problem, and it appears in many disguises. Its name comes from the version
of the problem where a travelling salesman has to visit all towns in the region and then
return to his home, and of course he wants to minimize his travel costs. It is clear that
mathematically, this is the same problem. It is easy to imagine that one and the same
mathematical problem appears in connection with designing optimal delivery routes for
mail, optimal routes for garbage collection etc.
The following important question leads to the same mathematical problem, except on
an entirely different scale. A machine has to drill a number of holes in a printed circuit
board (this number could be in the thousands), and then return to the starting point. In
this case, the important quantity is the time it takes to move the drilling head from one
hole to the next, since the total time a given board has to spend on the machine determines
the number of boards that can be processed in a day. So if we take the time needed to
move the head from one hole to another as the cost of this edge, we need to find a cycle
with the holes as nodes, and with minimum cost.
The Travelling Salesman Problem is much more difficult than the problem of finding
the cheapest tree, and there is no algorithm to solve it that would be anywhere nearly as
simple, elegant and efficient as the optimistic algorithm discussed in the previous section.
There are methods that work quite well most of the time, but they are beyond the scope
of this book.
But we want to show at least one simple algorithm that, even though it does not give
the best solution, never looses more than a factor of 2. We describe this algorithm in the
case when the cost of an edge is just its length, but it would not make any difference to
96
consider any other measure (like time, or the price of a ticket), at least as long as the costs
c(ij) satisfy the triangle inequality:
c(ij)+c(jk) e" c(ik)
(Air fares sometimes don t satisfy this inequality: it may be cheaper to fly from New York
to Chicago to Philadelphia then to fly from New York to Philadelphia. But in this case, of
course, we might consider the flight New York Chicago Philadelphia as one edge , which
does not count as a visit in Chicago.)
We begin by solving a problem we know how to solve: find a cheapest tree connecting
up the given nodes. We can use any of the algorithms discussed in the previous section for
this. So we find the cheapest tree T , with total cost c.
Now how does this tree help in finding a tour? One thing we can do is to walk around
the tree just like we did when constructing the planar code of a tree in the proof of
theorem 10.6 (see figure 26). This certainly gives a walk through each town, and returns
to the starting point. The total cost of this walk is exactly twice the cost c of T , since we
used every edge twice.
Of course this walk may pass through some of the towns more than once. But this is
just good for us: we can make shortcuts. If the walk takes us from i to j to k, and we have
seen j alread, we can proceed directly from i to k. The triangle inequality guarantees that
we have only shortened our walk by doing so. Doing such shortcuts as long as we can, we
end up with a tour through all the towns whose cost is not more than twice the cost of the
cheapest spanning tree (Figure 29).
But we want to relate the cost of the tour we obtained to the cost of the optimum tour,
not to the cost of the optimum spanning tree! Well, this is easy now: the cost of a cheapest
spanning tree is always less than the cost of the cheapest tour. Why? Because we can omit
any edge of the cheapest tour, to get a spanning tree. This is a very special kind of tree (a
path), and as a spanning tree it may or may not be optimal. However, its cost is certainly
[ Pobierz całość w formacie PDF ]
zanotowane.pldoc.pisz.plpdf.pisz.plcs-sysunia.htw.pl
|
| |
|
|
|
| Podobne |
| |
|
| |
|