44

次の擬似コードは、アルゴリズム設計マニュアルのオンラインプレビューバージョンの最初の章からのものです（このPDFの7ページ）。

この例は欠陥のあるアルゴリズムですが、それでも私はそれを本当に理解したいと思っています。

[...]別のアイデアは、サイクルの早期終了など、接続によって問題が発生しない最も近いエンドポイントのペアを繰り返し接続することです。各頂点は、独自の単一の頂点チェーンとして始まります。すべてをマージすると、すべてのポイントを含む単一のチェーンになります。最後の2つのエンドポイントを接続すると、サイクルが発生します。この最も近いペアのヒューリスティックの実行中の任意のステップで、マージに使用できる単一の頂点と頂点が互いに素なチェーンのセットがあります。擬似コードの場合：

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ください。tmsmtm

まず第一に、「異なる頂点チェーンから」が何を意味するのか理解できません。次に、i外側のループでカウンターとして使用されますが、iそれ自体が実際にどこでも使用されることはありません。私より賢い人がここで実際に何が起こっているのか説明してもらえますか？

4

3 に答える 3

36

アーネスト・フリードマン・ヒル（受け入れられた答え）の説明の後、これは私がそれを見る方法です：

したがって、同じ本の例（図1.4）。明確にするために頂点に名前を追加しました 図1.4

したがって、最初のステップでは、すべての頂点が単一の頂点チェーンであるため、AD、BE、およびCFのペアを接続し、それらの間のb/c距離が最小になります。

2番目のステップでは、3つのチェーンがあり、ADとBEの間の距離はBEとCFの間と同じなので、たとえばADとBEを接続し、2つのチェーン（ADEBとCF）を残します。

3番目のステップでは、それらを接続する唯一の方法はBとCを使用することです。b/ c BCはBF、AF、およびACよりも短くなります（チェーンのエンドポイントのみを考慮することを忘れないでください）。つまり、現在ADEBCFというチェーンが1つあります。

最後のステップで、2つのエンドポイント（AとF）を接続してサイクルを取得します。

于 2012-12-16T03:16:39.650 に答える
24

1）説明には、すべての頂点が常に「単一頂点チェーン」に属している（つまり、単独である）か、他の1つのチェーンに属していると記載されています。頂点は1つのチェーンにのみ属することができます。アルゴリズムは、各ステップで、それぞれが属するそれぞれのチェーンのエンドポイントであり、同じチェーンにまだ属していない2つの頂点のすべての可能なペアを選択することを示しています。シングルトンになることもあります。一方または両方がすでに重要なチェーンに属している場合があるため、2つのチェーンに参加します。

2）ループをn回繰り返して、最終的にすべての頂点を選択します。しかし、はい、実際の反復回数は何にも使用されません。重要なのは、ループを十分な回数実行することです。

于 2011-08-27T19:23:02.467 に答える
4

質問はすでに回答されていますが、これが最も近いペアのヒューリスティックのためのPython実装です。すべてのポイントをチェーンとして開始し、次にチェーンを連続して拡張して、すべてのポイントを含む1つの長いチェーンを構築します。このアルゴリズムはパスを構築しますが、そのアームの開始点が不明なロボットアームの動きのシーケンスではありません。

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 に答える