一尘不染

在最近的邻居算法中“来自不同的顶点链”是什么意思?

algorithm

以下伪代码来自 《算法设计手册》
在线预览版的第一章(此PDF第7页)。

这个例子是一个有缺陷的算法,但是我仍然很想理解它:

[…]一个不同的想法可能是重复连接最接近的一对端点,这些端点的连接不会造成问题,例如周期的提前终止。每个顶点都以其自己的单个顶点链开始。将所有内容合并在一起后,我们将得到一个包含所有点的单链。最后两个端点的连接给了我们一个循环。在执行该最接近对启发式方法的任何步骤中,我们将具有一组可合并的单个顶点和不相交的链。用伪代码:

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

请注意,smtm应该是s``mt``m

首先,我不明白“来自不同的顶点链”的含义。其次,i它用作外循环中的计数器,但i它本身从未在任何地方使用!能比我聪明的人解释一下这里到底发生了什么吗?


阅读 421

收藏
2020-07-28

共1个答案

一尘不染

1)描述中指出,每个顶点总是属于“单个顶点链”(即,它是单独的)或属于另一个链;一个顶点只能属于一个链。该算法说,在每个步骤中,您都选择两个顶点的每个可能对,这两个顶点分别是它们所属的链的端点,并且尚未属于同一链。有时他们会单身。有时其中一个或两个都已经属于非平凡链,因此您将加入两个链。

2)您重复循环 n 次,以便最终选择每个顶点;但是,是的,实际的迭代计数没有任何用。重要的是您要运行循环足够的时间。

2020-07-28