摘要訊息 : 如果一個問題的規模過大, 是否可以採用將大問題分為小問題, 然後逐個擊破小問題的方案?

0. 前言

如果你是一個搬運工人, 需要將貨車上的十噸貨物搬入貨船運往別的國家, 在沒有任何工具的情況下, 你會選擇只搬運一次嗎? 我想沒有一個人可以一次性搬走十噸的東西. 這些貨物並不是黏連在一起的, 所以我們通常會選擇一次搬運幾箱貨物, 然後來回搬運多次, 直到所有貨物都被裝載到貨船上. 這便是最原始的分而治之.

更新紀錄 :

• 2022 年 5 月 24 日進行第一次更新和修正;
• 2022 年 6 月 6 日進行內容添加.

1. 分而治之演算法

定義 1. 設有一合併函數 f. 對於任意給定的可分解問題 P, 按固定的規模或者比例將問題分解為 n 個小問題 : P_{1}, P_{2}, ..., P_{n}, 則有 P = f(P_{1}, P_{2}, ..., P_{n}). 若 S_{1}, S_{2}, ..., S_{n} 是 n 個小問題 P_{1}, P_{2}, ..., P_{n} 的解, 而 S = f(S_{1}, S_{2}, ..., S_{n}) 是原問題 P 的解, 則我們稱問題 P 可運用分而治之演算法 (divide and conquer algorithm), 分解問題的固定策略稱為分治策略 (divide and conquer strategy).

分而治之演算法在日常生活中的體現雖然不如貪婪演算法多, 但是除了第 0 節提到的搬運問題之外, 比較和搜尋問題也會較多地用到分而治之演算法. 例如在二分搜尋 (《【演算法】二分搜尋法 (Binary Search)》) 中, 我們將有序序列一分為二, 左右兩側的元素之差在一個之內, 這就是一個分治策略.

在遇到一個問題的時候, 如果發現這個問題可以使用分而治之演算法, 那麼如何制定分治策略非常重要. 分治策略不像貪婪策略 (《貪婪演算法》) 那樣, 只要合理即可. 分治策略主要從兩方面考慮, 一個是怎麼分, 還有一個是分到什麼程度結束.

我們首先考慮的問題是分到什麼程度算結束. 我們首先考慮第 0 節中的搬運問題, 你可以一次性扛起十箱貨物嗎? 我想不太可能. 那一次性扛起五箱貨物有可能嗎? 有可能, 但是貨物很大很重的情況下, 這又是不可能的. 那一次性扛起兩箱貨物有可能嗎? 有可能, 而且完全有可能. 這樣我們可以下一個結論, 就是當一個問題被分解之後, 如果小問題可以在瞬間或者很短時間內就可以被解決, 那麼把問題分到這個程度就可以結束了. 當然, 對於搬運問題我們還可以繼續分, 一次只扛一箱貨物. 但是在體能可能的情況下, 我們肯定希望在儘可能短的時間內完成搬運, 所以繼續分下去當然可以, 但是沒有意義.

再考慮怎麼分這個問題. 這個問題比較複雜, 通常來說需要根據實際情況來定. 我們可以一分為四, 也可以一分為二. 在搬運問題中, 我們採取的就是一分為二. 十箱扛不動, 就嘗試五箱, 分成兩組來嘗試. 一般來說, 一分為二也是比較多採用的分法, 例如二分搜尋. 三分搜尋或者四分搜尋可以嗎? 當然可以, 只是演算法實際的運作效能不一定有二分搜尋高. 所以我們不但要考慮實際的限制, 還要考慮分法對演算法效能的影響.

例題 1. 一個袋子裡有 2^{n} 枚硬幣, 這些硬幣中有一枚是假幣. 現在已經知道假幣的重量要比真幣輕一些, 給定一台可用來比較重量的儀器, 找出這一枚假幣.

解 :

我們可以將硬幣一分為二, 然後進行稱重, 選取較輕的那一份繼續一分為二. 直到只剩下兩枚硬幣為止, 哪一枚硬幣比較輕, 這一枚硬幣就是假幣.

\blacksquare

在例題 1 中, 如果採用一分為二的分而治之演算法, 那麼每一次我們都可以少稱 \frac {k}{2} 個硬幣的重量. 其中, k 是當前要被一分為二的硬幣總數, 一開始 k = 2^{n}. 如果採用一個一個硬幣稱重的方式, 運氣好的情況下我們稱中兩次就可以找到假幣, 但是運氣不好的情況下我們要稱重 2^{n} 次才能找到這枚假幣.

例題 2. 一個老闆有一袋子金塊, 共 2^{n} 塊. 每個月有兩名僱員會因為優異表現分別獲得一個金塊獎勵, 排名第一的員工會得到最重的金塊, 排名第二的員工會得到最輕的金塊. 由於定期會有金塊加入到袋子中, 所以每個月都必須找出最重和最輕的金塊. 現在給定一台可以用來比較重量的儀器, 我們希望使用最少的次數找到最重和最輕的金塊.

解 :

由於給定的儀器只能比較重量, 不能稱重, 所以我們將金塊無限細分, 直到每一組中只有兩塊金塊為止. 然後使用儀器選出較大的那一塊放入最重金塊候選集合, 較小的那一塊放入最輕金塊候選集合. 得到兩個候選集合之後, 採用相同的方法繼續細分, 從原最重金塊候選集合中選出更重的金塊候選集合, 剩餘另外一半可以無須考慮; 從原最輕金塊候選集合中找出更輕的金塊候選集合, 剩餘另外一半也無須考慮. 不斷這樣做, 直到最重金塊候選集合和最輕金塊候選集合中都只剩下一塊金塊為止. 這兩塊金塊就是袋子中最終和最輕的金塊.

\blacksquare

例題 1 和例題 2 的差別就在於稱重的儀器不同, 導致解決方案完全不同. 但是總體來說, 它們的解決方案中都使用了分而治之演算法, 而且都採用了一分為二的分治策略.

經過上面的討論, 我們可以得到使用分而治之演算法解決問題的基本步驟 :

1. 對於一個問題, 首先確定是否可以使用分而治之演算法;
2. 如果這個問題適用分而治之演算法, 那麼指定分治策略;
3. 使用分治策略將原問題進行細分為兩個或者兩個以上更小的子問題. 這些子問題除了要有原來問題的性質之外, 解決這些子問題的演算法時間複雜度應該是 \Theta(1) 的;
4. 解決這些子問題, 得到若干個子問題的解;
5. 將若干個子問題的解合併為原問題的解, 得到原問題的最終解.

我們提到, 解決子問題的演算法時間複雜度應該是 \Theta(1) 的, 這一點非常重要. 另外, 在確定是否可以使用分而治之演算法之前, 首先就要考慮若干子問題的解合併之後還能不能成為原問題的解. 如果若干子問題的解合併之後不合理, 那麼分而治之演算法就無法適用.

例題 3. 設有一個 2^{k} \times 2^{k} 個方格的棋盤, 但是這個棋盤中有一個方格是殘缺的. 當 k = 0 時, 棋盤中有且唯有一個方格, 那麼整個棋盤都是殘缺的. 當 k > 0 時, 棋盤中共有 2^{2k} 個方格, 那麼總共有 2^{2k} 種可能的殘缺棋盤. 我們希望使用三格板覆蓋整個殘缺棋盤. 在覆蓋的過程中, 任意兩個三格板不能出現交疊, 任意三格板不能覆蓋殘缺的格子且必須覆蓋除殘缺格子之外所有的方格.

分析 :

當 k = 0 時, 棋盤只有一個方格, 由於這一個方格是殘缺的, 所以整個棋盤都是殘缺的. 準確來說, 這樣的棋盤看不到, 但是到處存在 :

當 k = 1 時, 棋盤總共有四個方格, 但是一個是殘缺的, 所以有四種情況 :

對應地, 三角板也會有四種 :

當 k = 2 的時候, 如果殘缺棋盤是這樣的 :

我們採取的方案是從中間一分為四, 分成四個 2 \times 2 方格. 殘缺棋盤位於那一個部分, 覆蓋的三格板就不能涉及那一部分. 否則的話, 那個部分就會有兩個位置被佔用, 剩下兩個位置是不能用三格板覆蓋的. 那麼對於 Figure 2-1 中的殘缺棋盤, 一分為四之後應該這樣去覆蓋 :

這樣, 我們發現剩餘的棋盤都可以用三格板來覆蓋了 :

\blacksquare

解 :

當 k = 1 的時候, 由於只有一個方格, 所以我們可以直接使用三角板覆蓋. 這個時候演算法的時間複雜度為 \Theta(1), 所以分治策略就以此為標準.

對於 k > 1 的棋盤, 我們將整個棋盤一分為四, 分成四個 2^{k - 1} \times 2^{k - 1} 的棋盤. 然後查看殘缺的棋盤在哪一個部分, 以分析中那樣的方式用三格板覆蓋另外三個沒有殘缺的棋盤. 這樣, 四個棋盤都可以被當成是有殘缺的棋盤. 然後不斷細分, 直到所有棋盤都是 2 \times 2 棋盤為止, 這個時候不斷使用三格板覆蓋, 合併之後整個棋盤就都被三格板覆蓋了.

\blacksquare

2. 遞迴

一般來說, 分而治之演算法都是由遞迴解決的. 遞迴過程就是使用分治策略的過程, 遞迴結束過程就是小問題被解決之後合併的過程. 以例題 3 為例, 其遞迴過程可以寫為

3. 複雜度

使用分而治之演算法通常需要遞迴, 所以時間複雜度和空間複雜度的分析和貪婪演算法比要困難一些. 因為採用了遞迴的程式, 本身複雜度分析就不容易.

3.1 空間複雜度

使用分而治之演算法通常需要遞迴, 所以空間複雜度通常和實體特徵 n 有關係 (《程式碼效能分析》). 例如棋盤中格子的數量, 二分搜尋的線性表中的元素數量等. 設實體特徵 n 滿足 n = 2^{k}, 那麼一分為二的次數一共是 k 次. 因此需要的空間複雜度應該是 \Theta(k) = \Theta(\log_{2}{n}) = \Theta(\log {n}).

一般來說, 不論一分為幾, 使用了分而治之演算法的解決方案空間複雜度都是 \Theta(\log {n}).

3.2 時間複雜度

當一個演算法包含對其自身的遞迴呼叫時, 我們往往可以通過遞迴方程式來描述其運作時間. 令 T(n) 為一個使用了分而治之演算法的解決方案d惡運作時間. 當問題的規模足夠小的時候, 例如對於某一個常數 c, 當 n \leq c 時, 其運作時間可以在常數時間內完成. 此時, 其時間複雜度可以使用 \Theta(1) 來表示; 當問題規模擴大, 以至於 n > c, 使用分而治之演算法將問題分解為 a 個子問題, 每一個子問題的規模都是原問題的 \frac {1}{b}. 為了求解一個規模為 \frac {n}{b} 的子問題, 需要 T(\frac {n}{b}) 的時間. 那麼, 總共需要 a \cdot T(\frac {n}{b}) 的時間來求解 a 個子問題. 若分解一個問題或者子問題的時間為 D(n), 合併子問題的解為原問題的解的時間為 C(n), 則可以得到關於 T(n) 的遞迴方程式 \displaystyle {T(n)=\begin{cases} \Theta(1) & {n \leq c} \\ aT(\frac {n}{b}) + D(n) + C(n) & {n > c}. \end{cases}} 其中, n 是實體特徵.

在殘缺棋盤覆蓋問題中, 當 k > 2 時, 我們將棋盤分為四個子棋盤. 在子棋盤中, 問題規模從覆蓋一個 2^{k} \times 2^{k} 的殘缺棋盤變成了覆蓋一個 2^{k - 1} \times 2^{k - 1} 的殘缺棋盤, 那麼需要 T(k - 1) 的時間. 我們總共需要處理四個子棋盤, 總的時間為 4T(k - 1). 將一個規模為 2^{k} \times 2^{k} 細分為四個 2^{k - 1} \times 2^{k - 1} 的子棋盤, 實際上是四次函式呼叫. 對於 k > 1, 總共需要 4^{k - 1} 次遞迴, 因此 D(k) = \Theta(4^{k - 1}). 其中, D(k) 還包含了其它有關的處理需要的時間. 準確地來說, D(k) = 4^{k - 1} + c. 其中, c 為常數. 在所有子棋盤覆蓋完成之後, 並不需要進行合併, 棋盤就已經覆蓋完成了, 所以 C(k) = 0. 故使用分而治之演算法解決殘缺棋盤覆蓋問題的時間複雜度為 \displaystyle {T(k)=\begin{cases} \Theta(1) & {k \leq 1} \\ 4T(k - 1) + 4^{k - 1} + c & {k > 1}. \end{cases}} 我們無法直接從遞迴方程式中得到問題時間複雜度的漸近記法表示, 因為我們需要求解這個遞迴方程式. 這裡我們直接給出結論, 使用了分而治之演算法的殘缺棋盤覆蓋解決方案的時間複雜度為 T(k) = \Theta(4^{k}).

求解遞迴方程式可以參考文章 : 《【遞迴方程式】替代法與歸納法》, 《【遞迴方程式】特徵根法》和《【遞迴方程式】生成函數法》.

4. 距離最近的點

給定二維平面上的 n 個點 (x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{n}, y_{n}). 要求找到距離相近的兩個點. 對於點 (x_{i}, y_{i}) 和 (x_{j}, y_{j}) 的距離定義為 \displaystyle {d = \sqrt {(x_{i} - x_{j})^{2} + (y_{i} - y_{j})^{2}}}. 其中, i, j = 1, 2, …, n 且 i \neq j.

最直接的方法是考察所有的點對組合, 分別計算其距離, 並且從中選出最小的. 當 n 比較小的時候, 這個方法最直接簡單, 但是當 很大的時候, 這個方法的複雜度就很高. 使用上述方法求解, 時間複雜度為 O(n^{2}). 但是如果使用分而治之的思想, 可以降低複雜度.

首先我們對平面進行劃分. 對於 n 個點, 其必定分佈在某個矩形內, 選定一條中軸線將 n 個頂點劃分為 A 與 B 兩個集合. 若有點剛好落在中軸線上, 那麼將這些點平均地分配到集合 A 和 B 中. 不妨設 A 和 B 滿足 \displaystyle {\mathop {\mathrm {card}}{A} = \left \lceil \frac {n}{2} \right \rceil \text { 且 } \mathop {\mathrm {card}}{B} = n - \left \lceil \frac {n}{2} \right \rceil}. 接著, 點對的距離分為三種情況 :

• 要計算的兩個點都落在 A 中;
• 要計算的兩個點都落在 B 中;
• 要計算的點對中, 一個點落在 A 中, 另一個點落在 B 中.

對於前面兩種情況, 當 \mathop {\mathrm {card}}{A} 和 \mathop {\mathrm {card}}{B} 仍然較大的時候, 可以繼續一分為二, 直到區域中點的數量少於四個為止. 這個時候, 我們可以在常數時間複雜度內求解問題. 對於第三種情況, 則要使用不同的方法進行求解 : 設 A 中距離最短的點對的距離為 \xi, B 中距離最短的點對距離為 \zeta, 記 \delta = \min \left \{ \xi, \zeta \right \}. 我們的目的是試圖從第三類點對中尋找一個點對, 使得其距離比 \delta 還要小. 與中軸線距離大於 \delta 的點會被排除. 以中軸線為基礎, 寬度為 2\delta 內的點才能被留下. 若存在點被保留下來, 那麼從這些點中確定是否存在一個點對, 使得距離小於 \delta.

令 R_{A} 和 R_{B} 分別表示 A 和 B 中被保留下來的點的集合. 若存在一點對 (p, q), 使得 p \in A, p \in B, 且 d(p, q) < \delta, 則必有 p \in R_{A}, q \in R_{B}. 其中, d(p, q) 表示點對 p 和 q 之間的距離. 為了尋找這樣的點對, 每次考察 R_{A} 中的一個點 p. 設 p 的 y 座標為 y_{p}. 然後, 我們只需在 R_{B} 中查看那些 y 座標與 y_{p} 相距小於 \delta 的點 q, 即 \left | y_{q} - y_{p} \right | < \delta; 否則, 根據距離公式, \left | y_{q} - y_{p} \right | \geq \delta, 那麼 d(p, q) \geq \delta. 因此, 若且唯若 q 滿足 \left | y_{q} - y_{p} \right | < \delta 時, 才可能與 p 構成間距小於 \delta 的點對. 最終, 我們將區域縮小到大小為 \delta \times 2\delta 的區域, 稱其為比較區. 對於確定的 p \in R_{A}, 只需要在比較區尋找一個 q \in R_{B} 即可.

我們來分析使用了分而治之的解決方案的時間複雜度. 令 T(n) 表示使用了分而治之思想的演算法的運作時間, 當 n < 4 的時候, 我們採用直接法求解, 其用時為 \Theta(1), 則有 \displaystyle {T(n) = \begin {cases} \Theta(1) & {n < 4} \\ T \left ( \left \lceil \frac {n}{2} \right \rceil \right ) + T \left ( n - \left \lceil \frac {n}{2} \right \rceil \right ) + D(n) + C(n) & {n \geq 4}. \end {cases}} 從結果中取得最小距離的點對, 使用的時間為 \Theta(n), 因此 C(n) = \Theta(n). 對於點的一分為二, 即尋找一條中軸線, 所用的時間是常數級別的, 因此 D(n) = \Theta(1). 最終有 \displaystyle {T(n) = \begin {cases} \Theta(1) & {n < 4} \\ T \left ( \left \lceil \frac {n}{2} \right \rceil \right ) + T \left ( n - \left \lceil \frac {n}{2} \right \rceil \right ) + \Theta(n) & {n \geq 4}. \end {cases}} 若 \log_{2} {n} 為整數, 則 T(n) 有更簡單的遞迴方程式 \displaystyle {T(n) = \begin {cases} \Theta(1) & {n < 4} \\ T \left ( \frac {n}{2} \right ) + \Theta(n) & {n \geq 4}. \end {cases}} 解這個遞迴方程式, 可知 T(n) = \Theta(n\log {n}). 對於 n 不滿足 \log_{2}{n} 為整數的情形, 我們可以適當加入一些點來擴大 n, 使得n 滿足 \log_{2}{n} 為整數.

對於空間複雜度, 如果 A 區域沒有處理完成的話, 我們並不會開始用一分為二的方式處理 B 區域. 因此, 每次至多只有一半的點被一分為二. 最終, 空間複雜度為 \Theta(\log {n}).