最近點對問題

轉載：這個問題很容易理解，似乎也不難解決。我們只要將每一點與其他n-1個點的距離算出，找出達到最小距離的兩個點即可。然而，這樣做效率太低，需要O(n²)的計算時間。在問題的計算復雜性中我們可以看到，該問題的計算時間下界為Ω(nlogn)。這個下界引導我們去找問題的一個θ(nlogn)算法。

    這個問題顯然滿足分治法的第一個和第二個適用條件，我們考慮將所給的平面上n個點的集合S分成2個子集S₁和S₂，每個子集中約有n/2個點，·然后在每個子集中遞歸地求其最接近的點對。在這里，一個關鍵的問題是如何實現分治法中的合并步驟，即由S₁和S₂的最接近點對，如何求得原集合S中的最接近點對，因為S₁和S₂的最接近點對未必就是S的最接近點對。如果組成S的最接近點對的2個點都在S₁中或都在S₂中，則問題很容易解決。但是，如果這2個點分別在S₁和S₂中，則對于S₁中任一點p，S₂中最多只有n/2個點與它構成最接近點對的候選者，仍需做n²/4次計算和比較才能確定S的最接近點對。因此，依此思路，合并步驟耗時為O(n²)。整個算法所需計算時間T(n)應滿足:　

T(n)=2T(n/2)+O(n²)

    它的解為T(n)=O(n²)，即與合并步驟的耗時同階，顯示不出比用窮舉的方法好。從解遞歸方程的套用公式法，我們看到問題出在合并步驟耗時太多。這啟發我們把注意力放在合并步驟上。

    為了使問題易于理解和分析，我們先來考慮一維的情形。此時S中的n個點退化為x軸上的n個實數x₁,x₂,..,x_n。最接近點對即為這n個實數中相差最小的2個實數。我們顯然可以先將x₁,x₂,..,x_n排好序，然后，用一次線性掃描就可以找出最接近點對。這種方法主要計算時間花在排序上，因此如在排序算法中所證明的，耗時為O(nlogn)。然而這種方法無法直接推廣到二維的情形。因此，對這種一維的簡單情形，我們還是嘗試用分治法來求解，并希望能推廣到二維的情形。

    假設我們用x軸上某個點m將S劃分為2個子集S₁和S₂，使得S₁={x∈S|x≤m}；S₂={x∈S|x>m}。這樣一來，對于所有p∈S₁和q∈S₂有p<q。

    遞歸地在S₁和S₂上找出其最接近點對{p₁,p₂}和{q₁,q₂}，并設δ=min{|p₁-p₂|,|q₁-q₂|}，S中的最接近點對或者是{p₁,p₂}，或者是{q₁,q₂}，或者是某個{p₃,q₃}，其中p₃∈S₁且q₃∈S₂。如圖1所示。

　

圖1 一維情形的分治法

    我們注意到，如果S的最接近點對是{p₃,q₃}，即|p₃-q₃|<δ，則p₃和q₃兩者與m的距離不超過δ，即|p₃-m|<δ，|q₃-m|<δ，也就是說，p₃∈(m-δ,m]，q₃∈(m,m+δ]。由于在S₁中，每個長度為δ的半閉區間至多包含一個點（否則必有兩點距離小于δ），并且m是S₁和S₂的分割點，因此(m-δ,m]中至多包含S中的一個點。同理，(m,m+δ]中也至多包含S中的一個點。由圖1可以看出，如果(m-δ,m]中有S中的點，則此點就是S₁中最大點。同理，如果(m,m+δ]中有S中的點，則此點就是S₂中最小點。因此，我們用線性時間就能找到區間(m-δ,m]和(m,m+δ]中所有點，即p₃和q₃。從而我們用線性時間就可以將S₁的解和S₂的解合并成為S的解。也就是說，按這種分治策略，合并步可在O(n)時間內完成。這樣是否就可以得到一個有效的算法了呢？還有一個問題需要認真考慮，即分割點m的選取，及S₁和S₂的劃分。選取分割點m的一個基本要求是由此導出集合S的一個線性分割，即S=S₁∪S₂ ，S₁∩S₂⁼Φ，且S₁{x|x≤m}；S₂{x|x>m}。容易看出，如果選取m=[max(S)+min(S)]/2，可以滿足線性分割的要求。選取分割點后，再用O(n)時間即可將S劃分成S₁={x∈S|x≤m}和S₂={x∈S|x>m}。然而，這樣選取分割點m，有可能造成劃分出的子集S₁和S₂的不平衡。例如在最壞情況下，|S₁|=1，|S₂|=n-1，由此產生的分治法在最壞情況下所需的計算時間T(n)應滿足遞歸方程:

   T(n)=T(n-1)+O(n)

    它的解是T(n)=O(n²)。這種效率降低的現象可以通過分治法中“平衡子問題”的方法加以解決。也就是說，我們可以通過適當選擇分割點m，使S₁和S₂中有大致相等個數的點。自然地，我們會想到用S的n個點的坐標的中位數來作分割點。在選擇算法中介紹的選取中位數的線性時間算法使我們可以在O(n)時間內確定一個平衡的分割點m。

    至此，我們可以設計出一個求一維點集S中最接近點對的距離的算法CPAIR1如下。

function CPAIR1(S);
begin
  if |S|=2 then δ=|x[2]-x[1]| // x[1..n]存放的是S中n個點的坐標
           else if (|S|=1)
then δ:=∞
                   else begin
                          m:=S中各點的坐標值的中位數;
                          構造S1和S2,使S1={x∈S|x≤m}，S2={x∈S|x>m};
                          δ1:=CPAIRI(S1);
                          δ2:=CPAIRI(S2);
                           p:=max(S1);
                           q:=min(S2);
                          δ:=min(δ1,δ2,q-p);
                        end;
  return(δ);
end;

    由以上的分析可知，該算法的分割步驟和合并步驟總共耗時O(n)。因此，算法耗費的計算時間T(n)滿足遞歸方程：

    解此遞歸方程可得T(n)=O(nlogn)。

    這個算法看上去比用排序加掃描的算法復雜，然而這個算法可以向二維推廣。

    下面我們來考慮二維的情形。此時S中的點為平面上的點，它們都有2個坐標值x和y。為了將平面上點集S線性分割為大小大致相等的2個子集S₁和S₂，我們選取一垂直線l:x=m來作為分割直線。其中m為S中各點x坐標的中位數。由此將S分割為S₁={p∈S|p_x≤m}和S₂={p∈S|p_x>m}。從而使S₁和S₂分別位于直線l的左側和右側，且S=S₁∪S₂ 。由于m是S中各點x坐標值的中位數，因此S₁和S₂中的點數大致相等。

    遞歸地在S₁和S₂上解最接近點對問題，我們分別得到S₁和S₂中的最小距離δ₁和δ₂。現設δ=min(δ₁,δ₁)。若S的最接近點對(p,q)之間的距離d(p,q)<δ則p和q必分屬于S₁和S₂。不妨設p∈S₁，q∈S₂。那么p和q距直線l的距離均小于δ。因此，我們若用P₁和P₂分別表示直線l的左邊和右邊的寬為δ的2個垂直長條，則p∈S₁，q∈S₂，如圖2所示。

圖2 距直線l的距離小于δ的所有點

    在一維的情形，距分割點距離為δ的2個區間(m-δ,m](m,m+δ]中最多各有S中一個點。因而這2點成為唯一的末檢查過的最接近點對候選者。二維的情形則要復雜些，此時，P₁中所有點與P₂中所有點構成的點對均為最接近點對的候選者。在最壞情況下有n²/4對這樣的候選者。但是P₁和P₂中的點具有以下的稀疏性質，它使我們不必檢查所有這n²/4對候選者。考慮P₁中任意一點p,它若與P₂中的點q構成最接近點對的候選者，則必有d(p,q)<δ。滿足這個條件的P₂中的點有多少個呢？容易看出這樣的點一定落在一個δ×2δ的矩形R中，如圖3所示。

圖3 包含點q的δ×2δ的矩形R

由δ的意義可知P₂中任何2個S中的點的距離都不小于δ。由此可以推出矩形R中最多只有6個S中的點。事實上，我們可以將矩形R的長為2δ的邊3等分，將它的長為δ的邊2等分，由此導出6個（δ/2）×（2δ/3）的矩形。如圖4(a)所示。

圖4 矩形R中點的稀疏性

    若矩形R中有多于6個S中的點，則由鴿舍原理易知至少有一個δ×2δ的小矩形中有2個以上S中的點。設u,v是這樣2個點，它們位于同一小矩形中，則

    因此d(u,v)≤5δ/6<δ 。這與δ的意義相矛盾。也就是說矩形R中最多只有6個S中的點。圖4(b)是矩形R中含有S中的6個點的極端情形。由于這種稀疏性質，對于P₁中任一點p，P₂中最多只有6個點與它構成最接近點對的候選者。因此，在分治法的合并步驟中，我們最多只需要檢查6×n/2=3n對候選者，而不是n²/4對候選者。這是否就意味著我們可以在O(n)時間內完成分治法的合并步驟呢？現在還不能作出這個結論，因為我們只知道對于P₁中每個S₁中的點p最多只需要檢查P₂中的6個點，但是我們并不確切地知道要檢查哪6個點。為了解決這個問題，我們可以將p和P₂中所有S₂的點投影到垂直線l上。由于能與p點一起構成最接近點對候選者的S₂中點一定在矩形R中，所以它們在直線l上的投影點距p在l上投影點的距離小于δ。由上面的分析可知，這種投影點最多只有6個。因此，若將P₁和P₂中所有S的點按其y坐標排好序，則對P₁中所有點p，對排好序的點列作一次掃描，就可以找出所有最接近點對的候選者，對P₁中每一點最多只要檢查P₂中排好序的相繼6個點。

    至此，我們可以給出用分治法求二維最接近點對的算法CPAIR2如下:

function CPAIR2(S);
begin
  if |S|=2 then δ:=S中這2點的距離
     else if |S|=0
then δ:=∞
           else begin
                 1.  m:=S中各點x坐標值的中位數;
                     構造S1和S2，使S1={p∈S|px≤m}和S2={p∈S|px>m}
                 2.  δ1:=CPAIR2(S1);δ2:=CPAIR2(S2);
                 3.  δm:=min(δ1,δ2);
                 4.  設P1是S1中距垂直分割線l的距離在δm之內的所有點組成的集合，
                     P2是S2中距分割線l的距離在δm之內所有點組成的集合。將P1和
P2中的點依其y坐標值從小到大排序，并設P1*和P2*是相應的已排
好序的點列;
                 5.  通過掃描P1*以及對于P1*中每個點檢查P2*中與其距離在δm之內的
                     所有點(最多6個)可以完成合并。當P1*中的掃描指針逐次向上移動
                     時，P2*中的掃描指針可在寬為2δm的一個區間內移動。設δl是按
                     這種掃描方式找到的點對間的最小距離;
                 6.  δ=min(δm,δl);
               end;
  return(δ);
end;

    下面我們來分析一下算法CPAIR2的計算復雜性。設對于n個點的平面點集S，算法耗時T(n)。算法的第1步和第5步用了O(n)時間，第3步和第6步用了常數時間，第2步用了2T(n/2)時間。若在每次執行第4步時進行排序，則在最壞情況下第4步要用O(nlogn)時間。這不符合我們的要求。因此，在這里我們要作一個技術上的處理。我們采用設計算法時常用的預排序技術，即在使用分治法之前，預先將S中n個點依其y坐標值排好序，設排好序的點列為P^*。在執行分治法的第4步時，只要對P^*作一次線性掃描，即可抽取出我們所需要的排好序的點列P₁^*和P₂^*。然后，在第5步中再對P₁^*作一次線性掃描，即可求得δ_l。因此，第4步和第5步的兩遍掃描合在一起只要用O(n)時間。這樣一來，經過預排序處理后的算法CPAIR2所需的計算時間T(n)滿足遞歸方程：

    顯而易見T(n)=O(nlogn)，預排序所需的計算時間為O(n1ogn)。因此，整個算法所需的計算時間為O(nlogn)。在漸近的意義下，此算法已是最優的了。

晚上研究了半天，又參考了類似的代碼，終于搞出來了：

posted on 2009-05-18 23:28 極限定律 閱讀(2529) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC