Now the nearest town to home is B, the nearest unvisited town to B is A,
then the salesman goes to C and returns home. The total distance is
90 115 275 180 660. Of course, this example was constructed to il-
lustrate how greed can be one’s downfall; the proximity of B to home
lured us into taking a path that is significantly shorter than the best path.
If we go first to A, then to B, then to C, and return home, the total dis-
tance is 95 115 14 0 180 530, a considerable improvement. This also
shows that the nearest neighbor algorithm doesn’t always give us the
shortest overall trip.
The traveling salesman problem is considerably simpler than the
scheduling problem, in the sense that all one needs are the intracity dis-
tances—none of this stuff about digraphs and whether tasks are ready
and lists. There is a fairly obvious way to improve on the nearest neighbor
algorithm using a technique called “look-ahead.” Instead of greedily grab-
bing the shortest distance, we can use a little foresight and look for the
route that minimizes the total distance traveled to the next two towns we
visit, rather than just the distance to the next town.
We have to pay a price for this improvement. If there are N towns, we
can visit the first two towns in N(N1) ways, then the next two towns
in (N2)(N3), the next two towns in (N4) (N5) towns, and so on.
The total number of distances we must examine is therefore N(N1)
(N2)(N3)(N4)(N5). Each of the products in these
expressions contains a monomial term N^2 , and there are approximately
N/2 such products, so the total number of distances we must examine is
on the order of N^3 /2. A similar argument shows that if we “look ahead” by
computing the shortest distance for the next k towns we visit, the compu-
tational overhead is on the order of Nk^1.
When You’ve Solved One, You’ve Solved Them All
Part of the appeal of mathematics is that the solution of one problem fre-
quently turns out to be the solution of others. Calculus is replete with
such situations—one such example is that finding the slope of the tan-
gent to a curve turns out to solve the problem of determining the instan-
taneous velocity of a moving object when we know its position as a
function of time.
In this chapter, we’ve taken a close look at three problems: schedule con-
struction, the traveling salesman problem, and the card-sorting problem.
We’ve shown the last of these is tractable, but we have yet to determine
the status of the other two—although, as Han Solo said in Star Wars just
162 How Math Explains the World