26

ほぼ同じ質問があります。しかし、このヒューリスティックがどのように機能し、頂点がどのような順序で通過するのか、まだわかりません。また、本に次の写真があります。ここに画像の説明を入力

これは、最近傍ヒューリスティックと、私が最近傍ペア ヒューリスティックであると信じているものとの比較を示しています。写真から推測すると、上の写真では最初に 0 ポイントが選択されましたが、下の写真では左端または右端のポイントが選択されました。最初のポイントの選択については何も言われていないため (また、最も近いペアのヒューリスティックはその中で何のアクションも実行しません)、アルゴリズムの結果がどれほど優れていても、そうでない場合は下の画像が得られないと思います。どの点から始めるべきかを検討してください。

今のところ、最も近いペアのヒューリスティックがどのような手順を実行するかを知りたいだけです。説明とともに、各反復に関連付けられた番号が付いた下の図に似た図をいただければ幸いです。

これは、その投稿から取られた本へのリンクです。

4

4 に答える 4

17

私はその本を持っていませんが、最近傍ヒューリスティックとこのデータの最適解との比較を示しています。ここに示されているデータは (-21、-5、-1、0、1、3、11) です。

混乱は、「ローカル」貪欲アルゴリズムと「グローバル」貪欲アルゴリズムの間で発生する可能性があります (適切な言葉がないため)。上記の最近傍は厳密にローカルです。「ロボット」は 0 から始まり、1 に向かうことを選択します。これが最も近いパスだからです。ロボットは 1 にあり、次に近い点は -1 であることがわかります。次に、ロボットは -1 にあり、次に近い点は 3 などです。

最も近いペアはよりグローバルです。一度にすべての最適なエッジを調べています。したがって、このアルゴリズムは 0 から始まり、正確に 1 単位離れた (0, 1)、(1, 0)、(-1, 0)、および (0, -1) の 4 つを見つけます。グラフを作成する 2 つの異なるペア (-1、0、1) を追加します。これは、有向または無向のいずれかです。

次に、(1, 3) が 2 番目に小さいエッジであることがわかり、最適解に到達するまで繰り返されます。

違いは、最近傍の場合、ロボットは現在位置の近傍しか見ることができないということです。最も近いペアの場合、すべてのエッジを調べて最小のものを選択できます。

于 2012-07-12T20:06:01.903 に答える
15

私はこれが本の中であまり明確ではないことに同意します（読者がすぐに遭遇するので、これは少し残念です-私の版の7ページ）。

ここでの難しさは、最近接ペア ヒューリスティック自体にあるとは思いません。重要なのは、ヒューリスティック自体が問題の解決策ではないことに注意することです! 本で完全に説明されていないアルゴリズムの一部 (おそらく最も重要な部分) のみ (おそらく、これは間違ったアルゴリズムとして意図されているため)。ヒューリスティックを使用すると、接続する必要がある頂点のペアを取得できますが、接続する順序は取得できません。そのためには、さらに何かが必要です。

完全を期すために、ここに本の問題文があります

問題: ロボット ツアーの最適化

入力: 平面上のn点の集合S

出力: セットS内の各ポイントを訪れる最短のサイクル ツアーは?

現在、最も近いペアのヒューリスティックは、本で定義され、ここで引用されているように、ツアー自体ではなく、接続のセット/リストのみを提供するため、必要なソリューションではありません。ツアーを取得するには、さらに何かを行う必要があります。この戦略を使用した全体的な (欠陥のある!) ソリューションは、次のようになります。

1) Initialize the output list of vertexes to visit as the empty list (call it RET).
2) Obtain the list of connections (vertex pairs) given by ClosestPair (let it be L)
3) If L is empty, jump to 12
4) Remove an arbitrary connection from L (call it C1).
5) Choose an arbitrary vertex from C1 (call it V1)
6) Append V1 to RET
7) Remove from L the other connection that contains V1 (call it C2)
8) Choose the other vertex from that connection (call it V2)
9) append V2 to RET
10) Set V1=V2
11) If L is not empty, jump back to 7
12) return RET

または疑似コードで

Alg(P): # P is the input set of points
    RET = []
    L = ClosestPairs(P)
    if(L.empty()):
        return RET
    C1 = L.getAndRemoveRandomElement()
    V1 = C1.getRandomVertex()
    RET.append(V1)
    while(!L.empty()):
        C2 = L.getAndRemoveElementContaining(V1)
        V2 = C2.getTheOtherVertex(V1)
        RET.append(V2)
        V1 = V2
    return RET
于 2014-11-23T20:26:35.070 に答える