4

私はアルゴリズムに関するCourseraのコースをたどり、最も近いペアの問題の分割/征服アルゴリズムについて考えを思いつきました。それを明確にしたいと思います。

ラフガーデン教授のアルゴリズム (興味がある場合はここで確認できます) に従って: 与えられた点 P のセットに対して、2 つのコピー (X 方向と Y 方向に並べ替えられたもの) - Px と Py がある場合、アルゴリズムは次のように与えられます。

最も近いペア (Px、Py):

  1. ポイントを左半分 - Q と右半分 - R に分割し、x 方向と y 方向に沿って両方の半分のソートされたコピーを形成します - Qx、Qy、Rx、Ry
  2. closestPair(Qx,Qy) を点 p1 と q1 とする
  3. closestPair(Rx,Ry) を p2,q2 とする
  4. デルタを dist(p1,q1) と dist(p2,q2) の最小値とする
  5. これは残念なケースです。p3,q3 を最も近い SplitPair(Px,Py,delta) とします。
  6. 最良の結果を返す

さて、私が望む明確化はステップ 5 に関連しています。私が提案していることはほとんど改善されていないことを前もって言っておく必要がありますが、それでも興味がある場合は、先に読んでください。

R 教授は、ポイントは既に X 方向と Y 方向に並べ替えられているため、ステップ 5 で最適なペアを見つけるには、幅 2*delta のストリップ内のポイントを下から上に、内側で繰り返す必要があると述べています。ループ 7 回の比較のみが必要です。これを1つだけに改善できますか？

私がどのように可能であると考えているかをプレーン テキストで説明するのは少し難しいように思えたので、図を描いて紙に書き、ここにアップロードしました。

ここに画像の説明を入力

誰も思いつかなかったので、私の考えには間違いがあると確信しています。しかし、私は文字通りこれについて何時間も考えていたので、これを投稿する必要がありました. それは私の頭の中にあるすべてです。

誰かが私が間違っているところを指摘できますか?

4

1 に答える 1

5

箇条書き5の結論は正しくありません。分割線に近い点Aを描画してみてください。

Aのデルタ内に、互いにデルタ内にない2つのポイント（上に1つ、下に1つ）を持つことができます。

  | B
  | 
 A|
  | 
  | C

ここで、dist(A,B) = dist(A,C) < dist(B,C)。

これは、写真が直感を得るのに役立つ理由の完璧な例ですが、結論を裏付けるには証明が必要です。

于 2012-07-03T23:43:42.173 に答える