betical order). If there are N towns (other than home), it’s easy to see that
we have to f ind the smallest of N numbers to find the nearest neighbor, then
the smallest of N1 numbers to find the nearest unvisited neighbor to the
first town, then the smallest of N2 numbers to find the nearest unvisited
number to the second town, etc. So the worst that could happen is that we
had to examine a total of N(N1)(N2) 1 N(N 1)/2 num-
bers. Like the card-by-card comparison algorithm when we dropped the
Rolodex, this is an algorithm such that the time taken is on the order of
N^2 , where N is the number of towns.
The nearest neighbor algorithm is an example of what is known as a
“greedy” algorithm. There’s a technical definition of “greedy algorithm,”^2 but
it’s pretty clear here what’s going on; it’s an attempt to construct a path doing
the least possible work while still doing some work (simply grabbing the first
number available would do the least possible work). Greedy algorithms some-
times give reasonable solutions, but often greed, like crime, doesn’t pay.
On our first trip to the garage, we discovered that there are situations in
which upgrading all the equipment actually results in a longer comple-
tion time. There’s an analogous situation for the traveling salesman prob-
lem using the nearest neighbor algorithm; it is possible to shorten all the
intracity distances and end up with a longer overall trip.
Let’s look at a distance table with three towns other than the hometown.
Home A B C
Home 0 100 105 200
A 100 0 120 300
B 105 120 0 150
C 200 300 150 0This is a mileage chart similar to the ones found on road maps that used
to be available at gas stations. The nearest town to home is A, the nearest
unvisited town to A is B, then the salesman must go to C and then home.
The total distance for this trip is 100 120 150 200 570. Suppose we
have a slightly different mileage chart in which all intracity distances
have been reduced.
Home A B C
Home 0 95 90 180
A 95 0 115 275
B 90 115 0 140
C 180 275 140 0Murphy’s Law 161