Don't understand closest pair heuristic from “

问题:

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.

回答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.

回答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

回答3:

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

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

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.