分割統治を使用して最も近い点のペアを見つける

このセクションでは、分割統治法を使用して最も近い点のペアを見つけるための効率的なアルゴリズムを紹介します。一連の点が与えられた場合、最近接ペア問題は、互いに最も近い 2 つの点を見つけることです。下図に示すように、最近接ペアのアニメーションでは、最も近い 2 点を結ぶ線が描画されます。

ケーススタディ: 最も近いペアの検索では、点の最も近いペアを見つけるための総当たりアルゴリズムを紹介しました。アルゴリズムは、すべての点のペア間の距離を計算し、最小距離を持つ点を見つけます。明らかに、アルゴリズムには O(n^2) 時間がかかります。より効率的なアルゴリズムを設計できますか?

この問題を解決するには、分割統治と呼ばれるアプローチを使用します。このアプローチでは、問題をサブ問題に分割し、サブ問題を解決し、サブ問題の解を組み合わせて問題全体の解を取得します。動的プログラミングのアプローチとは異なり、分割統治アプローチの部分問題は重複しません。部分問題は元の問題に似ていますが、サイズが小さいため、再帰を適用して問題を解決できます。実際、再帰的問題に対するすべての解決策は分割統治アプローチに従っています。

以下の手順では、分割統治法を使用して最近接ペア問題を解く方法を説明します。

• ステップ 1: 点を x 座標の昇順に並べ替えます。同じ X 座標を持つ点については、Y 座標に基づいて並べ替えます。これにより、ソートされたポイントのリスト S が生成されます。
• ステップ 2: ソートされたリストの中点を使用して、S を同じサイズの 2 つのサブセット S1 と S2 に分割します。中間点を S1 に置きます。 S1 と S2 で最も近いペアを再帰的に見つけます。 d1 と d2 が、それぞれ 2 つのサブセット内の最も近いペアの距離を表すものとします。
• ステップ 3: S1 の点と S2 の点の間で最も近いペアを見つけ、それらの距離を d3 として示します。最も近いペアは、距離が min(d1, d2, d3) のペアです。

選択ソートには O(n^2) 時間がかかります。ステップ 1 は O(n log n) 時間で実行できます。ステップ 3 は O(n) 時間で実行できます。 d = min(d1, d2) とします。最も近いペアの距離が d より大きくならないことはすでにわかっています。 S1 の点と S2 の点が S で最も近いペアを形成するには、以下の図に示すように、左の点が stripL 内にあり、右の点が stripR 内にある必要があります ( a).

stripL 内の点 p については、以下の (b) に示すように、d X 2d 長方形内の右側の点のみを考慮する必要があります。長方形の外側の任意の右点は、p と最も近いペアを形成できません。 S2 の最近接ペアの距離は d 以上であるため、最大 6 つ存在する可能性があります
長方形内の点。したがって、stripL の各点について、stripR 内の最大 6 つの点を考慮する必要があります。

stripL の各点 p について、stripR の対応する d X 2d 長方形領域内の点をどのように見つけますか? stripL と stripR 内の点が y 座標の昇順に並べ替えられている場合、これを効率的に行うことができます。 pointsOrderedOnY を、y 座標の昇順に並べ替えた点のリストとします。 pointsOrderedOnY はアルゴリズムで事前に取得できます。 stripL と stripR は、以下のコードに示すように、ステップ 3 の pointsOrderedOnY から取得できます。

pointsOrderedOnY の各ポイント p について
if (p が S1 にあり、mid.x – p.x pをstripLに追加;
else if (p が S2 にあり、p.x - Mid.x pをstripRに追加;

次に示すように、stripL と stripR の点を {p0, p1, ... , pk} と {q0, q1, ... , qt} とします。上図(c)。 stripL 内の点と stripR 内の点の間で最も近いペアは、以下のコードで説明されているアルゴリズムを使用して見つけることができます。

d = min(d1, d2);
 r = 0; // r is the index of a point in stripR
 for (each point p in stripL) {
 // Skip the points in stripR below p.y - d
  while (r < stripR.length && q[r].y <= p.y - d)
  r++;

  let r1 = r;
  while (r1 < stripR.length && |q[r1].y – p.y| <= d) {
 // Check if (p, q[r1]) is a possible closest pair
 if (distance(p, q[r1]) < d) {
 d = distance(p, q[r1]);
 (p, q[r1]) is now the current closest pair;
 }

 r1 = r1 + 1;
 }
}

stripL 内の点は、p0、p1、...、pk からこの順序で考慮されます。 stripL 内の点 p については、p.y – d より下にある stripR 内の点をスキップします (行 5 ～ 6)。ポイントがスキップされると、そのポイントは考慮されなくなります。 while ループ (9 ～ 17 行目) は、(p, q[r1]) が最も近いペアである可能性があるかどうかをチェックします。 stripR 内の 2 点間の距離は d より小さくなることはできないため、そのような q[r1] ペアは最大 6 つあります。したがって、ステップ 3 で最も近いペアを見つけるための複雑さは O(n) です。

上記の手順のステップ 1 は、ポイントを事前に並べ替えるために 1 回だけ実行されることに注意してください。すべての点が事前に並べ替えられていると仮定します。 T(n) がこのアルゴリズムの時間計算量を表すものとします。したがって、

したがって、最も近い点のペアは O(n log n) 時間で見つかります。

以上が分割統治を使用して最も近い点のペアを見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。