算法范式 - gaochundong－IT工程師數位筆記本

文章出處

算法：按步驟解決問題的過程。

An algorithm is a step-by-step procedure for solving a problem.

范式：思考問題的模式。

"Pattern of thought" which governs scientific apprehension during a certain period of time.

算法范式：為問題構建高效解決方案的常規方法。

General approaches to the construction of efficient solutions to problems。

算法范式可以被看做為解決一類問題的高層算法。

算法范式提供的模板可適用于解決更廣泛的問題。
通過最高層的語言可以將范式轉換成通用的組件或數據結構。
對算法產生結果所需的時間和空間的需求可以做精確的分析。

常見的算法范式有：

暴力破解法（Brute Force Paradigm）
分治法（Divide and Conquer Paradigm）
動態規劃法（Dynamic Programming Paradigm）
貪心算法（Greedy Paradigm）
回溯法（Backtracking Paradigm）
分支限界法（Branch and Bound Paradigm）

暴力破解法（Brute Force Paradigm）

暴力破解法簡單直接，根據問題聲明的定義，找到所有可變化的因子（Divisor），窮舉所有可能解決問題的方法，逐個嘗試。

所以，根據暴力破解法的定義，理論上講任何問題都可以使用暴力破解法來解決，只是在實際應用中算法對時間和空間的需求則無法滿足。

將暴力破解法應用于數據查找，由于查找比較次數與給定目標的規模直接相關，所以也稱為線性查找（Linear Search）。

線性查找有很多典型應用：

分治法（Divide and Conquer Paradigm）

分治法（Divide-and-Conquer），即 "分而治之"，是將原問題劃分成 n 個規模較小而結構與原問題相似的子問題，遞歸地解決這些問題，然后再合并其結果，以得到原問題的解。

當我們遇到一個大問題時，總是習慣把問題的規模變小，這樣便于分析討論。這些規模變小后的問題和原來的問題是同質的，除了規模變小，其它的都是一樣的，本質上它還是同一個問題，規模變小后的問題其實是原問題的子問題。

分治模式在每一層上都有三個步驟：

分解（Divide）：將原問題分解成一系列與原問題同質的子問題；
解決（Conquer）：遞歸地解決各個子問題。若子問題足夠小，則直接求解；
合并（Combine）：將子問題的結果合并成原問題的解。

分治法所能解決的問題一般具有以下幾個特征：

可以將問題分解為若干個規模較小的相同問題；
問題的規模縮小到一定程度后就可以很容易地解決；
問題分解出的子問題的解可以合并為該問題的解；
問題所分解出的各個子問題是相互獨立的，即子問題之間不再包含公共的孫問題。

符合 1,2,3 條特征是使用分治法的關鍵，而特征 4 將涉及到分治法的效率問題。而如果不符合 3,4 特征的問題可以嘗試考慮使用動態規劃或貪心算法來解決。

分治法的典型應用：

動態規劃法（Dynamic Programming Paradigm）

動態規劃的過程可以描述為多階段最優化解決問題的過程，每一次的決策依賴于當前的狀態，隨即又引起狀態的轉移，以此類推在變化的狀態中產生出決策序列。

動態規劃算法通常基于一個遞推公式及一個或多個初始狀態，當前子問題的解將由上一次子問題的解推出。使用動態規劃來解題通常只需要多項式時間復雜度，所以會比回溯法、暴力法等要快許多。

動態規劃方法中的關鍵詞包括：階段（Stage）、狀態（State）、決策（Decision）、遞推關系（Recurrent Relation）。

動態規劃首先將待求解的問題分解為若干個子問題（階段），按順序求解子問題。前一子問題的解為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。以此類推解決各子問題，最后一個子問題的解就是初始問題的解。

動態規劃與分治法最大的差別是：適合于用動態規劃法求解的問題，經分解后得到的子問題往往不是互相獨立的（即下一個子問題的求解是建立在上一個子問題的解的基礎上，進行進一步的求解）。

動態規劃所能解決的問題一般具有以下幾個特征：

最優化原理（Mathematical Optimization）：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構（Optimal Substructure），即滿足最優化原理。
無后效性：即某階段狀態一旦確定，就不受這個狀態以后決策的影響。也就是說，某狀態以后的過程不會影響以前的狀態，只與當前狀態有關。
有重疊子問題（Overlapping Subproblems）：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。

特征 3 并不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃算法同其他算法相比就不具備優勢。

動態規劃的基本步驟：

劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。
確定狀態和狀態變量：將問題發展到各個階段時所處于的各種客觀情況用不同的狀態表示出來。狀態的選擇要滿足無后效性。
確定決策并寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩個階段的狀態之間的關系來確定決策方法和狀態轉移方程。
尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

貪心算法（Greedy Paradigm）

所謂貪心算法是指，在對問題求解時，總是做出在當前看來最好的選擇。也就是說，不從整體最優上加以考慮，它所做出的僅是在某種意義上的局部最優解。

貪心算法沒有固定的算法框架，算法設計的關鍵是貪心策略的選擇。貪心策略適用的前提是：局部最優策略能導致產生全局最優解。所以實際上，貪心算法適用的情況很少。

貪心算法不是對所有問題都能得到整體最優解，選擇的貪心策略必須具備無后效性，即某個狀態以后的過程不會影響以前的狀態，只與當前狀態有關。所以對所采用的貪心策略一定要仔細分析其是否滿足無后效性。

貪心算法的基本思路：

建立數學模型來描述問題。
把求解的問題分成若干個子問題。
對每一子問題求解，得到子問題的局部最優解。
把子問題的解局部最優解合成原來問題的一個解。

回溯法（Backtracking Paradigm）

回溯法描述了一種選優搜索過程，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先的選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的方法稱為回溯法，而滿足回溯條件的某個狀態的點稱為 "回溯點"。

回溯法可以理解為隱式的深度優先搜索算法。其在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根節點出發深度探索解空間樹。當探索到某一節點時，要先判斷該節點是否包含問題的解，如果包含，就從該節點出發繼續探索下去，如果該節點不包含問題的解，則逐層向其祖先節點回溯。

許多復雜的，規模較大的問題都可以使用回溯法，有 "通用解題方法" 的美稱。

回溯法的一般步驟：

針對給定問題，確定問題的解空間，問題的解空間應至少包含問題的一個（最優）解；
確定節點的擴展搜索規則；
以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索；

分支限界法（Branch and Bound Paradigm）

類似于回溯法，分支限界法也是一種在問題的解空間樹上搜索問題解的算法。但在一般情況下，分支限界法與回溯法的求解目標不同。回溯法的求解目標是找出樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標函數值達到極大或極小的解，即在某種意義下的最優解。

所謂 "分支" 就是采用廣度優先搜索算法，依次搜索節點的所有分支，拋棄不滿足約束條件的節點，然后從余下的節點中選擇一個節點作為下一個搜索節點繼續搜索。

由于求解目標不同，導致分支限界法與回溯法在解空間樹上的搜索方式也不相同。回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹。

分支限界法的搜索策略是：在擴展節點處，先生成其所有的兒子節點（分支），然后再從當前的活節點表中選擇下一個擴展節點。為了有效地選擇下一擴展節點，以加速搜索的進程，在每一活節點處，計算一個函數值（限界），并根據這些已計算出的函數值，從當前活節點表中選擇一個最有利的節點作為擴展節點，使搜索朝著解空間樹上有最優解的分支推進，以便盡快地找出一個最優解。