1

I have been reading Algorithm design manual. I have the same question as What is the meaning of "from distinct vertex chains" in this nearest neighbor algorithm? but I am not able to follow the answers there.

A different idea might be to repeatedly connect the closest pair of endpoints whose connection will not create a problem, such as premature termination of the cycle. Each vertex begins as its own single vertex chain. After merging everything together, we will end up with a single chain containing all the points in it. Connecting the final two endpoints gives us a cycle. At any step during the execution of this closest-pair heuristic, we will have a set of single vertices and vertex-disjoint chains available to merge. In pseudocode:

ClosestPair(P)
    Let n be the number of points in set P.
    For i = 1  to n − 1 do
        d = ∞
        For each pair of endpoints (s, t) from distinct vertex chains
            if dist(s, t) ≤ d then sm = s, tm = t, and d = dist(s, t)
        Connect (sm, tm) by an edge
    Connect the two endpoints by an edge
Please note that sm and tm should be sm and tm.

I am not able to follow above logic. Please demonstrate the computation for the simple example which is given in the book: -21, -5, -1, 0, 1, 3, and 11. Show the computations step by step, so that one can follow above code easily.

Community
  • 1
  • 1
venkysmarty
  • 11,099
  • 25
  • 101
  • 184

1 Answers1

8

First example

In the following notation, I use parentheses to denote chains. Each vertex starts out as its first chain. The inner loop iterates over all pairs of chain endpoints, i.e. all pairs of nodes which have a parenthesis written immediately next to them, but only those pairs where the two endpoints come from different chains. The results of this inner loop are a pair of endpoints which minimize the distance d. I'll assume that pairs are sorted s < t, and furthermore that pairs are traversed in lexicographical order. In that case, the rightmost pair matching that minimal d will be returned, due to the ≤ in the code.

(-21), (-5), (-1), (0), (1), (3), (11)    d =  1, sm =   0, tm =  1
(-21), (-5), (-1), (0 ,  1), (3), (11)    d =  1, sm =  -1, tm =  0
(-21), (-5), (-1 ,  0 ,  1), (3), (11)    d =  2, sm =   1, tm =  3
(-21), (-5), (-1 ,  0 ,  1 ,  3), (11)    d =  4, sm =  -5, tm = -1
(-21), (-5 ,  -1 ,  0 ,  1 ,  3), (11)    d =  8, sm =   3, tm = 11
(-21), (-5 ,  -1 ,  0 ,  1 ,  3 ,  11)    d = 16, sm = -21, tm = -5
(-21 ,  -5 ,  -1 ,  0 ,  1 ,  3 ,  11)    d = 32 to close the loop

So in this example, the code works as intended.

Second example

Figure 1.4 will give an example where this code does not work, i.e. will yield a suboptimal result. Labeling the vertices like this

  A <--(1+e)--> B <--(1+e)--> C
  ^             ^             ^
  |             |             |
(1-e)         (1-e)         (1-e)
  |             |             |
  v             v             v
  D <--(1+e)--> E <--(1+e)--> F

In this case you'll get

(A), (B), (C), (D), (E), (F)  d = 1-e, sm = C, tm = F
(C, F), (A), (B), (D), (E)    d = 1-e, sm = B, tm = E
(C, F), (B, E), (A), (D)      d = 1-e, sm = A, tm = D
(C, F), (B, E), (A, D)        d = 1+e, sm = E, tm = F
(B, E, F, C), (A, D)          d = 1+e, sm = A, tm = B
(D, A, B, E, F, C)            d = sqrt((2+2e)^2+(1-e)^2) to close

which is not the optimal solution.

MvG
  • 57,380
  • 22
  • 148
  • 276
  • Thanks for help. As you mentioned end points, can you please eloborate here what end points here? One more question what does author mean by connect the two end points by an edge in above pseudo code. – venkysmarty Oct 30 '12 at 11:45
  • Endpoints are those points at the end of a chain. E.g. in the second-to-last line of the second example, `B, C, A, D` would be endpoints, whereas `E, F` would not be endpoints, as they are inside `(B, E, F, C)`. Connecting points with an edge means forming a longer chain from two shorter ones. – MvG Oct 30 '12 at 11:49
  • Sorry to bother with another question what do you mean by pairs are traveersed by lexicogrphical order? – venkysmarty Oct 30 '12 at 11:53
  • @venkysmarty, the inner loop iterates over each pair of endpoints, but doesn't specify an order. So I assumed the pairs to be sorted by their first member, using the second member to break ties. See http://en.wikipedia.org/wiki/Lexicographical_order. – MvG Oct 30 '12 at 11:58
  • Thanks! so I understood correctly for (0,-21), (0, -5), (0, -1), (0,1), (0,3) and (0, 11) am I right for inner loop for i = 1 one more how do you get in first example d = 2, sm = -5, tm = -1 – venkysmarty Oct 30 '12 at 12:01
  • In text above algorithm is not best solution as given in Fig1.2 when we start at point 0 as we are moving left and right and not giving right answer as we will get right answer only if we start at -21? – venkysmarty Oct 30 '12 at 12:21
  • @venkysmarty, you're looking for cyclic tours, so it doesn't matter where you start. Furthermore, the order in which we start *building* our tour is not the order in which we *follow* the tour. The complete chain in the last line is the result of the planning phase, and as you can see, you'll really be starting at -21 in that case. The `d=2` in the first example was an error, will correct that. – MvG Oct 30 '12 at 13:42
  • I am having a tough time with this explanation in the book. Please correct me if I am wrong about the comparisons in the 1st iteration: (-21, -5) <= infinity; d becomes 16, (-5, -1) <= 16; d becomes 4, (-1, 0) <= 4; d becomes 1, (0 , 1) <= 1; d stays 1 but s=0, t =1, (1, 3) <= 1; d stays 1, (3, 11) < =1; d stays 1 So at the end of 1st iteration, d =1, (s, t) = (0,1) – ChrisOdney Apr 19 '14 at 06:17
  • Thanks. However, I am unable to apply the same logic to the second example: (A,B) <= infinity; d becomes 1+e, (B,C) <= 1+ e; d becomes 1 + e, (C, D) <= 1+ e; d stays 1+e, (D, E) <= 1+ e; d becomes 1+e; (E,F) <= 1+e; d becomes 1+e with s=e and t=f. How did we end up with (C,F) though? – ChrisOdney Apr 19 '14 at 07:05
  • 1
    @ChrisOdney: You have to iterate over all pairs, not just adjacent pairs. In that sense, your interpretation of the first example is incomplete as well, upon second thought. It's more like (-21,-5), (-21,-1), (-21,0), (-21,1), … (-21,11), (-5,-1), … and in the second example you get (A,B), (A,C), (A,D), (A,E), (A,F), (B,C), (B,D), … – MvG Apr 19 '14 at 07:11
  • Thanks :). I actually considered this but then discarded it looking at how inefficient it is. O(n square) is too bad. – ChrisOdney Apr 19 '14 at 07:22