It is seldom obvious whether a given algorithm correctly solves a
given problem.
This is why correct algorithms usually come with a proof of correctness,
which is an explanation of *why* we know that the algorithm
correctly takes all instances of the problem to the desired result.
In this book, we will not stress formal proofs of correctness, primarily
because
they take substantial mathematical maturity to properly appreciate
and construct.
However, before we go further it is important to demonstrate why
*``it's obvious''*
never suffices as a proof of correctness
and usually is flat-out wrong.

To illustrate, let us consider a problem that often arises in manufacturing, transportation, and testing applications. Suppose we are given a robot arm equipped with a tool, say a soldering iron. In manufacturing circuit boards, all the chips and other components must be fastened onto the substrate. More specifically, each chip has a set of contact points (or wires) that must be soldered to the board. To program the robot arm to perform this soldering job, we must first construct an ordering of the contact points, so that the robot visits (and solders) the first contact point, then visits the second point, third, and so forth until the job is done. The robot arm must then proceed back to the first contact point to prepare for the next board, thus turning the tool-path into a closed tour, or cycle.

Since robots are expensive devices, we want to find the tour that minimizes the time it takes to assemble the circuit board. A reasonable assumption is that the robot arm moves with fixed speed, so that the time it takes to travel between two points is the same as its distance. In short, we must solve the following algorithm problem:

*Input:* A set *S* of *n* points in the plane.

*Output:* What is the shortest cycle tour that visits
each point in the set *S*?
You are given the job of programming the robot arm.
Stop right now and think about an algorithm to solve this problem.
I'll be happy to wait until you find one.

Several possible algorithms might come to mind to solve this problem. Perhaps the most popular idea is the

**Figure:** A good example for the nearest neighbor heuristic

NearestNeighborTSP(

P)Pick and visit an initial point from

P

i= 0While there are still unvisited points

i=i+1Select to be the closest unvisited point to

Visit

Return to from

This algorithm has a lot to recommend it. It is simple to understand and implement. It makes sense to visit nearby points before we visit faraway points if we want to minimize the total travel time. The algorithm works perfectly on the example in Figure . The nearest neighbor rule is very efficient, for it looks at each pair of points at most twice, once when adding to the tour, the other when adding . Against all these positives there is only one problem. This algorithm is completely wrong.

**Figure:** A bad example for the nearest neighbor heuristic

*Wrong?*
How can it be wrong? The algorithm always finds a tour,
but the trouble is that it
doesn't necessarily find the shortest possible tour.
It doesn't necessarily even come close.
Consider the set of points in Figure , all of which lie
spaced along a line.
The numbers describe the distance that each point lies to the left or
right of the point labeled `0'.
When we start from the point `0' and repeatedly walk to the nearest
unvisited neighbor, you will see that we keep jumping
left-right-left-right over `0'.
A much better (indeed optimal) tour for these points starts
from the leftmost point and visits each point as we walk right before
returning at the rightmost point.
Try now to imagine your
boss's delight as she watches
a demo of your robot arm hopscotching left-right-left-right during
the assembly of
such a simple board.

``But wait,'' you might be saying. ``The problem was in starting at point `0'. Instead, why don't we always start the nearest-neighbor rule using the leftmost point as the starting point ? By doing this, we will find the optimal solution on this example.''

That is 100% true, at least until we rotate our example 90 degrees. Now all points are equally leftmost. If the point `0' were moved just slightly to the left, it would be picked as the starting point. Now the robot arm will hopscotch up-down-up-down instead of left-right-left-right, but the travel time will be just as bad as before. No matter what you do to pick the first point, the nearest neighbor rule is doomed not to work correctly on certain point sets.

Maybe what we need is a different approach.
Always walking to the closest point is too restrictive,
since it seems to
trap us into making moves we didn't want.
A different idea would be to repeatedly
connect the closest pair of points whose connection
will not cause a cycle or a three-way branch
to be formed.
Eventually, we will end up with a single chain containing
all the points in it.
At any moment during the execution of this *closest-pair heuristic*,
we will have a set of partial paths to merge,
where each vertex begins as its own partial path.
Connecting the final two endpoints gives us a cycle.
In pseudocode:

ClosestPairTSP(

P)Let

nbe the number of points in setP.

For

i=1 ton-1doFor each pair of endpoints (,

t) of distinct partial pathsif then , , and

d=dist(,t)Connect by an edge

Connect the two endpoints by an edge

This closest-pair rule does the right thing on the example in Figure .
It starts by connecting `0' to its immediate neighbors,
the points *1* and *-1*.
Subsequently, the next closest pair will alternate left-right,
growing the central path
by one link at a time.
The closest-pair heuristic is somewhat more complicated and less efficient
than the previous one, but at least it gives the right answer.
On this example.

**Figure:** A bad example for the closest-pair heuristic.

But not all examples.
Consider what the algorithm does on the point set in Figure (a).
It consists of two rows of equally spaced points, with the rows slightly
closer together (distance *1-e*) than the neighboring points are spaced
within each row (distance *1+e*).
Thus the closest pairs of points stretch across the gap,
not around the boundary.
After we pair off these points, the closest remaining pairs will connect
these pairs alternately around the boundary.
The total path length of the closest-pair tour
is .
Compared to the tour shown in Figure (b),
we travel over 20% farther than necessary when .
Examples exist where the penalty is considerably worse than this.

Thus this second algorithm is also wrong. Which one of these algorithms performs better? You can't tell just by looking at them. Clearly, both heuristics can end up with very bad tours on very innocent-looking input.

At this point, you might wonder what a correct algorithm for the
problem looks like.
Well, we could try all enumerating *all*
possible orderings of the set of points, and then select the ordering
that minimizes the total length:

OptimalTSP(P)

For each of the

n! permutations of pointsPIf then and

Return

Since all possible orderings are considered, we are guaranteed to end up with the shortest possible tour. This algorithm is correct, since we pick the best of all the possibilities. The problem is that it is also extremely slow. The fastest computer in the world couldn't hope to enumerate all 20! = 2,432,902,008,176,640,000 orderings of 20 points within a day. For real circuit boards, where , forget about it. All of the world's computers working full time wouldn't come close to finishing your problem before the end of the universe, at which point it presumably becomes moot.

The quest for an efficient algorithm to solve this so-called *traveling
salesman problem* will take us through much of this book.
If you need to know how the story ends, check out the catalog entry for the
traveling salesman problem in Section .

Hopefully, this example has opened your eyes to some of the subtleties of algorithm correctness. Ensuring the optimal answer on all possible inputs is a difficult but often achievable goal. Seeking counterexamples that break pretender algorithms is a tricky business, but it is an important part of the algorithm design process.

Mon Jun 2 23:33:50 EDT 1997