Don't understand closest pair heuristic from "The Algorithm Design Manual "
algorithm, graph-theory
Solution
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.
Problem
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.