44

以下伪代码来自《算法设计手册》在线预览版的第一章（本 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

请注意smandtm应该是smand tm。

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

4

3 回答 3

36

在解释了 Ernest Friedman-Hill（已接受的答案）之后，这就是我的看法：

所以来自同一本书的例子（图 1.4）。我为顶点添加了名称以使其清楚 图 1.4

所以第一步所有的顶点都是单顶点链，所以我们连接AD、BE和CF对，它们之间的b/c距离最小。

在第二步，我们有 3 条链，AD 和 BE 之间的距离与 BE 和 CF 之间的距离相同，所以我们将 AD 与 BE 连接起来，我们留下两条链 - ADEB 和 CF

在第三步，连接它们的唯一方法是通过 B 和 C，b/c BC 比 BF、AF 和 AC 短（记住我们只考虑链的端点）。所以我们现在有一条链ADEBCF。

在最后一步，我们连接两个端点（A 和 F）以获得一个循环。

于 2012-12-16T03:16:39.650 回答
24

1) 描述说明每个顶点要么属于“单顶点链”（即它是单独的），要么属于另一个链；一个顶点只能属于一个链。该算法表示，在每一步中，您选择每对可能的两个顶点，它们都是它们所属的相应链的端点，并且不属于同一个链。有时他们会是单身人士；有时一个或两个已经属于一个非平凡的链，所以你会加入两个链。

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

于 2011-08-27T19:23:02.467 回答
4

虽然问题已经得到解答，但这里是最接近对启发式的 python 实现。它以每个点为一条链开始，然后依次延伸链以构建包含所有点的长链。该算法确实构建了一条路径，但它不是机器人手臂运动的序列，因为该手臂起点是未知的。

import matplotlib.pyplot as plot
import math
import random


def draw_arrow(axis, p1, p2, rad):
    """draw an arrow connecting point 1 to point 2"""
    axis.annotate("",
              xy=p2,
              xytext=p1,
              arrowprops=dict(arrowstyle="-", linewidth=0.8, connectionstyle="arc3,rad=" + str(rad)),)


def closest_pair(points):
    distance = lambda c1p, c2p:  math.hypot(c1p[0] - c2p[0], c1p[1] - c2p[1])
    chains = [[points[i]] for i in range(len(points))]
    edges = []
    for i in range(len(points)-1):
        dmin = float("inf")  # infinitely big distance
        # test each chain against each other chain
        for chain1 in chains:
            for chain2 in [item for item in chains if item is not chain1]:
                # test each chain1 endpoint against each of chain2 endpoints
                for c1ind in [0, len(chain1) - 1]:
                    for c2ind in [0, len(chain2) - 1]:
                        dist = distance(chain1[c1ind], chain2[c2ind])
                        if dist < dmin:
                            dmin = dist
                            # remember endpoints as closest pair
                            chain2link1, chain2link2 = chain1, chain2
                            point1, point2 = chain1[c1ind], chain2[c2ind]
        # connect two closest points
        edges.append((point1, point2))
        chains.remove(chain2link1)
        chains.remove(chain2link2)
        if len(chain2link1) > 1:
            chain2link1.remove(point1)
        if len(chain2link2) > 1:
            chain2link2.remove(point2)
        linkedchain = chain2link1
        linkedchain.extend(chain2link2)
        chains.append(linkedchain)
    # connect first endpoint to the last one
    edges.append((chains[0][0], chains[0][len(chains[0])-1]))
    return edges


data = [(0.3, 0.2), (0.3, 0.4), (0.501, 0.4), (0.501, 0.2), (0.702, 0.4), (0.702, 0.2)]
# random.seed()
# data = [(random.uniform(0.01, 0.99), 0.2) for i in range(60)]
edges = closest_pair(data)
# draw path
figure = plot.figure()
axis = figure.add_subplot(111)
plot.scatter([i[0] for i in data], [i[1] for i in data])
nedges = len(edges)
for i in range(nedges - 1):
    draw_arrow(axis, edges[i][0], edges[i][1], 0)
# draw last - curved - edge
draw_arrow(axis, edges[nedges-1][0], edges[nedges-1][1], 0.3)
plot.show()
于 2015-04-20T20:49:27.080 回答