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

user_260894 0
Viewed 5499

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: enter image description here

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.

graph-theory algorithm
4 Answers

I was going through the same problem of understand this heuristic, my answer might help the others facing the same problem.

What does the robot need is a closed path which visits all the points and cycle backs to its original position. There is a statement mentioning premature termination which insists that the path should be full (visiting all points i.e.. we should not join some pair of vertices such that they create a smaller closed path).

Now going through the example below

Figure 1.3

here the by using the closest-pair heuristic we will find a path which connects all the points in a line and then connects the remaining end points with each other (-21 , 11). So whether robot starts with 0 or -21 or 11, it will be travelling the same distance (it will circle back to its starting position for next iteration). This distance will be the optimal distance.

But the above approach fails in the case below

Figure 1.4

here the closest pair path turns out to be the image on the left, while the optimal path should be the image on the right, hence the heuristic fails to give the correct solution.

user_97997620

TL;DR - As I understand it, the "bad" approach connects increasingly distant unvisited points to each other directly, wasting more solder in multiple arcs and eventually connecting the last point back to the 1st point '0'.

The "better" approach moves outward from the center 1 point at a time in either direction, so still back & forth, but only laying solder between directly neighboring points along the 'number line'.

The illustrations & explanations really aren't clear in a single static image. He doesn't explain what the dotted line means (is it soldered? Is it just motion? Seems inconsistent). Agree this is frustrating to encounter so early in what's supposed to be the "clear" algorithms book ...

Both the "closest neighbor" AND "closest pair" examples seem to "hopscotch" back & forth over point 0, which is the reason given for the 1st approach being bad. He even says the 2nd approach should also alternate left-right, so how is it any better? Because you only connect directly neighboring points to each other, building up the complete line incrementally.

The "bad" example (as I understand it): 

1. 0 connects to 1
2. 1 jumps over 0 & connects to -1
3. -1 jumps over 0 & connects to 3
4. 3 jumps over 0 & connects to -5
5. -5 jumps over 0 & connects to 11
6. 11 jumps over 0 & connects to -21
7. -21 connects back to 0, completing the cycle.

These "hopscotch" back & forth over 0, but don't connect the points in a straight line. You wind up w/6 distinct 'lines' of soldered connections.

The "better" closest pair example:

1. 0 connects to 1.
2. 0 connects to -1
3. 1 connects to 3
4. -1 connects to -5
5. 3 connects to 11
6. -5 connects to -21
7. -21 connects to 11 
8. Unstated, the robot arm apparently travels back to 0 afterward?

These also go back & forth over 0, but incrementally extend the existing straight line by one point at a time at each step. Instead of 6 arcs of solder, you have a single line for most of it, and then the 2nd connection of the outermost endpoints.

user_32169700
Related