使用分治法找出最近的點對

本節介紹了使用分治法來找出最接近的點對的有效演算法。給定一組點，最近對問題是找到彼此最接近的兩個點。如下圖所示，繪製一條線來連接最近對動畫中兩個最近的點。

案例研究：查找最近對，提出了一種用於查找最近點對的強力演算法。此演算法計算所有點對之間的距離並找到距離最小的點。顯然，該演算法需要 O(n^2) 時間。我們能設計一個更有效率的演算法嗎？

我們將使用一種名為分而治之的方法來解決這個問題。此方法將問題分成子問題，求解子問題，然後組合子問題的解以獲得整個問題的解。與動態規劃法不同，分而治之方法中的子問題不重疊。子問題就像原問題一樣，但規模較小，因此可以應用遞歸來解決問題。事實上，所有遞歸問題的解決方案都遵循分而治之的方法。

以下步驟描述如何使用分而治之的方法來解決最近對問題。

• 第 1 步：依 x 座標升序對點進行排序。對於具有相同 x 座標的點，按 y 座標排序。這會產生一個排序的點列表 S。
• 第 2 步：使用排序清單中的中點將 S 分成兩個大小相等的子集 S1 和 S2。令中點位於 S1 處。遞歸地找到 S1 和 S2 中最接近的對。令 d1 和 d2 分別表示兩個子集中最近對的距離。
• 第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，只需考慮d X 2d矩形內的右點，如下圖(b)所示。矩形外的任何右點都不能與 p 形成最接近的對。由於 S2 中最近對的距離大於或等於 d，因此最多可以有 6 個
矩形內的點。因此，對於stripL中的每個點，最多需要考慮stripR中的六個點。

對於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，跳過 stripR 中低於 p.y – d 的點（第 5-6 行）。一旦跳過某個點，就不再考慮該點。 while 循環（第 9-17 行）檢查 (p, q[r1]) 是否是可能最接近的對。這樣的 q[r1] 對最多有 6 個，因為 stripR 中兩點之間的距離不能小於 d。因此，在步驟 3 中找到最接近的對的複雜度是 O(n)。

請注意，上述步驟中的步驟 1 僅執行一次以對點進行預先排序。假設所有點都已預先排序。令 T(n) 表示演算法的時間複雜度。因此，

因此，可以在 O(n log n) 時間內找到最接近的點對。

以上是使用分治法找出最近的點對的詳細內容。更多資訊請關注PHP中文網其他相關文章！