Correctness

 

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 nearest-neighbor heuristic. Starting from some point , we walk first to its nearest neighbor . From , we walk to its nearest unvisited neighbor, thus excluding only as a candidate. We now repeat this process until we run out of unvisited points, at which time we return to to close off the tour. In pseudocode, the nearest-neighbor heuristic looks like this:  

  
Figure: A good example for the nearest neighbor heuristic

NearestNeighborTSP(P)

		Pick and visit an initial point    from P

		  

		i = 0

		While there are still unvisited points

				 i = i+1

				 Select    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 n be the number of points in set P.

		  

		For i=1 to n-1 do

				 For each pair of endpoints (,t) of distinct partial paths

				 		 if    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 points P

				 If    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.