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

  • Z时代
  • 2024-01-10
  • 分类：问答

以下伪代码来自 《算法设计手册》

在线预览版的第一章（此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

请注意，sm和tm应该是s``m和t``m。

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

回答：

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

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

以上是 在最近的邻居算法中“来自不同的顶点链”是什么意思？ 的全部内容， 来源链接： utcz.com/qa/410064.html

回到顶部