almost 3 years ago

0 前言

在一個二維平面上,有很多個點,我們說一個點 支配(dominate)了另一個點 ,若且唯若點 的兩個座標都嚴格大於點 的兩個座標。如下圖:我們說 A 支配了 B;D 支配了 B、C。

一個直接的問題是:給定平面上 個點 ,要如何找出所有的支配點對?(或者是,我們想要知道總共有多少點對?)顯然在極端的情形下, 個點的支配點對的數量可以高達 個(例如他們座落在直線 上),但我們希望找出一個更有效率的演算法,在輸出量不到 的時候,能夠更快解決問題。

對於二維支配點對的問題,我們可以提出一個分而治之的演算法:我們先找出所有點 座標的中位數,然後把所有點分成兩群 以及 ,接著所有的支配點對要嘛就在 裡頭,要嘛都在 裡頭,要嘛比較低的在左邊、比較高的在右邊。分別遞迴找出 的所有支配點對,然後把 中的點依照 座標排序。排完以後兩個註標追趕的方式(保持右邊的點永遠比左邊的點來得高)就可以得知所有的點對了。

以下這支程式是表示如何求出支配點對的總數。如果預先排序好 軸,我們可以寫出以下的虛擬碼:

bool compare_by_X(const Point &A, const Point &B) {
    reutrn A.x < B.x || (A.x == B.x && A.y < B.y);
}
long long countDominatingPairs(vector<Point> &P) {
    vector<Point> L, R;
    if (P.size() <= 1) return 0;
  
  //第一步:找出中位數
 auto mid = nth_element(P.begin(), P.end(), compare_by_X);
  //第二步:把點分成兩邊
 for (auto &&p : P) {
        if (p.x < mid.x)
            L.push_back(p);
        else
            R.push_back(p);
    }
    //第三步:由於 Y 座標已經排序,我們只需要掃過兩個陣列計算支配點對的數量。
 long long cnt = 0;
  for (int i = 0, j = 0; i < R.size(); i++) {
        while (j < L.size() && L[j].y < R[i].y) j++;
        cnt += j;
    }
  //遞迴與回傳結果
 return countDominantPairs(L) + countDominantPairs(R) + cnt;
}

時間複雜度為 因此解得

1 維度更高的時候怎麼辦?

維度更高的時候,我們可以從最後一個維度下手。如果我們依照最後一個維度的座標值,選取了中位數以後,把這些點分成兩部份 以及 ,這時候我們雖然可以遞迴計算 之中的支配點對,但此時並非所有 都可以形成支配點對。因此我們需要修改一下題目,讓接下來的子問題都可以符合我們要的形式:

給定兩個 維空間中的點集合 以及 ,請計算(或找出)所有支配點對 。我們令 為輸入的總點數。

因此分而治之法也即將要完成了:首先我們考慮 根據最後一個維度座標值選取的中位數 ,然後把所有 中的點根據 各分成兩群:

注意到因為 是中位數,因此我們有 以及 (思考問題:若座標值有重複時,我們該如何選取?)。分別遞迴下去以後資料量都會減半,感覺挺好地。那麼第三部分呢?顯然此時我們只需要顧慮 的情形就可以了!而且,我們還可以把維度減少一維!

複雜度分析

的時候,我們可以用 的時間解決這題。假若我們要解決的問題是 個點、 維的問題。可以得到遞迴式:

解得

2 有沒有類似題?

有的!請參考 UVa 103 Stacking Boxes 雖然沒有太直接的關聯,但是大家可以想看看要怎麼把這題的解法用進去~(在實作上可能直接用 的動態規劃就行了。)

巢狀收納箱子問題,我們可以做到 ,不過細節有點複雜,就交給有興趣的同學們討論了!

← 分而治之法(三):尋找中位數 分而治之法(四之二):(min, +) 矩陣相乘問題 →
 
comments powered by Disqus