Don't understand closest pair heuristic from "The Algorithm Design Manual "

Question

There is almost exactly the same question. But I still don't understand, how is this heuristic working and in what sequence vertexes are passed through. Also there is a picture in a book:

That shows comparison of nearest-neghbor heuristic and what I believe is a closest-pair heuristic. From the picture I may assume that on the top picture, 0 point was selected first, but on the bottom picture there was selected the leftmost or the rightmost one. Because there is nothing said about first point selection (also the closest-pair heuristic doesn't do any actions in that), I may assume that any algorithm results however good it is won't give you the bottom picture if it doesn't consider, what point to start with.

For now I just want to know, what steps closest-pair heuristic makes. A picture similar to the bottom one with numbers associated with each iteration along with explanation would be appreciated.

Here is the link to the book taken from that post.

Answer 1

I don't have the book, but it is showing a comparison of the nearest neighbor heuristic to the optimal solution for this data. The data shown here is (-21, -5, -1, 0, 1, 3, 11).

The confusion may be between a "local" greedy algorithm and a "global" greedy algorithm (for lack of better word). The nearest neighbor shown above is strictly local. The "robot" starts at 0 and chooses to go to 1, because it is the closest path. The robot is at 1, and finds the next closest point is -1. Then the robot is at -1 and the next closest point is 3, and so on.

The closest pair is more global. It is looking at all optimal edges at once. So, the algorithm starts at 0 and finds four that are exactly 1 unit apart (0, 1), (1, 0), (-1, 0), and (0, -1). It would add two distinct pairs creating the graph (-1, 0, 1). This could be either directed or non-directed.

Then it would repeat, and notice that (1, 3) is the next smallest edge, and so on, until it arrives at the optimal solution.

The difference is that in the nearest neighbor case, the robot can only look at the neighbors of where it is currently located. In the closest pair case, you can look at all edges to choose the smallest one.

Answer 2

I agree this is not very clear in the book (which is a bit of a downer as the reader encounters it right away - page 7 in my edition).

I think the difficulty here is not in the closest-pair heuristic itself. The key is noticing that the heuristic is not itself supposed to be the solution to the problem! Only a part (arguably the most important part) of an algorithm that is never fully described in the book (probably because this is intended as a wrong algorithm). With the heuristic, you get the pairs of vertexes that should be connected, but not the order in which they ought to be connected. For that, something more is needed.

For completeness, here is the problem statement from the book

Problem: Robot Tour Optimization

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

Now, the closest-pair heuristic, as defined in the book and quoted here, only gives you a set/list of connections, not the tour itself, and so not the required solution. To obtain the tour you would have to do something more. An overall (flawed!) solution using this strategy would look something like:

1) Initialize the output list of vertexes to visit as the empty list (call it RET). 2) Obtain the list of connections (vertex pairs) given by ClosestPair (let it be L) 3) If L is empty, jump to 12 4) Remove an arbitrary connection from L (call it C1). 5) Choose an arbitrary vertex from C1 (call it V1) 6) Append V1 to RET 7) Remove from L the other connection that contains V1 (call it C2) 8) Choose the other vertex from that connection (call it V2) 9) append V2 to RET 10) Set V1=V2 11) If L is not empty, jump back to 7 12) return RET 

Or in pseudo-code

Alg(P): # P is the input set of points     RET = []     L = ClosestPairs(P)     if(L.empty()):         return RET     C1 = L.getAndRemoveRandomElement()     V1 = C1.getRandomVertex()     RET.append(V1)     while(!L.empty()):         C2 = L.getAndRemoveElementContaining(V1)         V2 = C2.getTheOtherVertex(V1)         RET.append(V2)         V1 = V2     return RET