algorithm - 最も近いペアのアルゴリズム

Question

最も近いペアのアルゴリズムを理解しようとしています。セットを半分に分割することについて理解しています。しかし、最も近いペアを再帰的に計算する方法を理解するのに苦労しています。再帰は理解できますが、再帰によって最も近いペアを計算する方法がわかりません。（1,2）（1,11）（7,8）がある場合、再帰はこれらに対してどのように機能しますか？

Answer 1

アルゴリズムの基本的な考え方はこれです。

一連の点 P があり、それらの間の距離が最も短い P 内の 2 つの点を見つけたいとします。

単純な力ずくのアプローチでは、P のすべてのペアを調べて距離を計算し、距離が最も短いペアを 1 つ取得します。これは O(n²) アルゴリズムです。

ただし、あなたが話しているアルゴリズムによって改善することは可能です。アイデアは、最初に座標の 1 つ (x 座標など) に従ってすべてのポイントを並べ替えることです。これで、セット P は実際には、x 座標で並べ替えられた点の並べ替えられたリストになります。アルゴリズムは、ポイントのセットではなく、ソートされたポイントのリストを入力として受け取ります。アルゴリズムを ClosestPair(L) と呼びましょう。ここで、L は引数として与えられたポイントのリストです。

ClosestPair(L) は、次のように再帰的に実装されるようになりました。

1. リスト L を中央で分割し、 L _leftと L _rightを取得します。
2. ClosestPair(L _left ) と ClosestPair(L _right ) を再帰的に解きます。対応する最短距離を δ _leftおよび δ _rightによって取得します。
3. _{これで、元のセット (L で表される) の最短距離は、2 つの δ のいずれか、または L left}内の点と L _right内の点の間の距離であることがわかります。
4. 左と右のサブディビジョンからの 2 点間の距離が短いかどうかを確認する必要があります。_{トリックは、距離が δ left}および δ right_よりも小さくなければならないことがわかっているため_、分割線 (x 座標元のリストを分割していました L)。この最適化により、実際には O(n log n) のブルート フォース アプローチよりも手順が高速になります。

Answer 2

このアルゴリズムを意味する場合は、次のようにします。

1. ソートポイント: (1,2) (1,11) (7,8)
2. (1,2) (1,11) と (7,8) の 2 つのサブセットを作成します。
3. (1,2) (1,11) と (7,8) で別々にアルゴリズムを実行します <= ここで再帰が行われます。結果は dLmin = 9 および dRmin = 無限大 (右側に 2 番目の点はありません)
4. dLRmin = sqrt(45)
5. 結果 = 分 (dLmin、dRmin、dLRmin) = sqrt(45)

再帰は、上記と同じ手順で構成されます。たとえば、(1,2) と (1,11) の呼び出しは次のようになります。

1. ソートポイント: (1,2) (1,11)
2. (1,2) と (1,11) の 2 つのサブセットを作成します。
3. (1,2) と (1,11) で別々にアルゴリズムを実行します <= 再帰呼び出し。結果は、dLmin = 無限大および dRmin = 無限大です。
4. dLRmin = 9
5. 結果 = 分 (dLmin、dRmin、dLRmin) = 9

Answer 3

私はあなたが話しているアルゴリズムを知っていると思います。ここで自分で詳しく説明することもできますが、アルゴリズムの紹介に記載されている説明は、私が作成できるものよりもはるかに優れています. そして、その章はグーグルブックスでも利用できます：楽しむ。(他の誰もがそこに問題の説明を見つけることができます)

Answer 4

おそらく、線形時間のランダム化された最近接ペアアルゴリズムが役立つでしょう。そこで、予想時間 O(n) でペアを見つけることができます。