最近对伪代码示例

Question

我一直在阅读算法设计手册.我有同样的问题,这个最近邻算法中"来自不同的顶点链"是什么意思？但我无法按照那里的答案.

一个不同的想法可能是重复连接最接近的端点对,这些端点的连接不会产生问题,例如过早终止循环.每个顶点都以其自己的单个顶点链开始.在将所有内容合并在一起之后,我们将最终得到一个包含其中所有点的链.连接最后两个端点为我们提供了一个循环.在执行此最近对启发式过程中的任何步骤中,我们将有一组可用于合并的单顶点和顶点不相交链.在伪代码中:

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.

我无法遵循上述逻辑.请证实了这是在给定的简单例子计算书:-21, -5, -1, 0, 1, 3, and 11.逐步显示计算,以便人们可以轻松地遵循上述代码.

Answer 1

第一个例子

在下面的表示法中,我使用括号来表示链.每个顶点都以其第一个链开始.内循环遍历所有链端点对,即所有具有紧邻它们的括号写入的节点对,但仅限于两个端点来自不同链的那些对.该内环的结果是一对最小化距离的端点d.我假设对是排序的s < t,而且这些对是按字典顺序遍历的.在这种情况下,d由于?代码中的原因,将返回与最小值匹配的最右边的对.

(-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

因此,在此示例中,代码按预期工作.

第二个例子

图1.4将给出一个示例,其中此代码不起作用,即将产生次优结果.像这样标记顶点

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

在这种情况下,你会得到

(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

这不是最佳解决方案.