字體：小 中 大 |
|
|
|
| 2009/09/17 22:58:42瀏覽2399｜回應0｜推薦1 | |
Divide and Conquer
「團結力量大」即意味著「分散力量小」，所以在戰術上常常見到「分而擊之」的策略，在政治的舞台上也常常見到政客與其打手無所不用其極地挑撥與分化對手的陣營，企圖令之分崩離析。「分而擊之」所突顯的意義是：較小的團體比較容易解決，所以應該想辦法把較大的團體分化成較小的團體。divide and conquer 的核心思惟就是「分而擊之」，亦即先把欲處理的問題切割成兩個 sub-problem，如果這兩個 sub-problem 還是有點棘手，就分別地再將它們切割成更小的 sub-problem，如此不斷地切割，直到最後的 sub-problem 小到非常容易解決時為止 (請參考圖 5.2-4)。
一般而言，可被 divide and conquer 所解決的問題，通常是 sub-problem 與 whole problem 皆屬於相同類型的問題 (that's why we can use recursion to implement the solution)，差別只在於規模的大小。如果被切割後的 sub-problem 與原來的 whole problem 已經屬於不同類型的問題，則採用 divide and conquer 的方法就有可能無法順利地或很漂亮地解決該問題 (備註：最常見的 D&C Problem，是「切一刀」就將原題切成兩個相似的子題，所以我們採用 Direct Recursion Approach，但有些類型的問題則需要「切好幾刀」，原題才會重回相似的型態，此時我們可採用 Indirect Recursion Approach；當然，「切好幾刀」也可採 Direct Recursion Approach，只是程式寫起來會比較難看、比較不好閱讀)。 就程式的實作而言，我們是把欲處理的問題放到 array 中，再藉由 recursive function call 反覆地對它進行切割的運作。典型的實作程式包含四個主要函式，分別為： 1. 呼叫自己以進行切割程序的函式 (Divide_n_Conquer)。 在此，我們將這四個函式的通力合作關係表達於 the template of divide and conquer 的程式列表中。2. 判斷 sub-problem 是否可以迎刃而解的函式 (IsSmallEnough)。 3. 求得解答的函式 (ConquerIt)。 4. 決定切割點在哪裡的函式 (DivideIt)。
|
|
| ( 創作｜其他 ) |
