以下伪代码来自 《算法设计手册》 在线预览版的第一章(此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。
sm
tm
s``m
t``m
首先,我不明白“来自不同的顶点链”的含义。其次,i它用作外循环中的计数器,但i它本身从未在任何地方使用!能比我聪明的人解释一下这里到底发生了什么吗?
i
1)描述中指出,每个顶点总是属于“单个顶点链”(即,它是单独的)或属于另一个链;一个顶点只能属于一个链。该算法说,在每个步骤中,您都选择两个顶点的每个可能对,这两个顶点分别是它们所属的链的端点,并且尚未属于同一链。有时他们会单身。有时其中一个或两个都已经属于非平凡链,因此您将加入两个链。
2)您重复循环 n 次,以便最终选择每个顶点;但是,是的,实际的迭代计数没有任何用。重要的是您要运行循环足够的时间。