常見的演算法設計策略

1.分治

      分治法的設計思想是，將一個難以直接解決的大問題，分割成k個規模較小的子問題，這些子問題相互獨立，且與原問題相同，然後各個擊破，分而治之。

      分治法常常與遞歸結合使用：通過反覆應用分治，可以使子問題與原問題類型一致而規模不斷縮小，最終使子問題縮小到很容易求出其解，由此自然導致遞歸演算法。

      根據分治法的分割原則，應把原問題分割成多少個子問題才比較適宜？每個子問題是否規模相同或怎樣才為適當？這些問題很難給與肯定的回答。但人們從大量實踐中發現，在使用分治法時，最好均勻劃分，且在很多問題中可以取k=2。這種使子問題規模大致相等的做法源自一種平衡子問題的思想，它幾乎總是比使子問題規模不等的做法好。

2.動態規劃

      動態規劃法與分治法類似，其基本思想也是將原問題分解成若幹個子問題。與分治法不同的是，其分解出的子問題往往不是相互獨立的。這種情況下若用分治法會對一些子問題進行多次求解，這顯然是不必要的。動態規劃法在求解過程中把所有已解決的子問題的答案保存起來，從而避免對子問題重覆求解。

      動態規劃常用於解決最優化問題。對一個最優化問題可否應用動態規劃法，取決於該問題是否具有如下兩個性質：

      1.最優子結構性質

      當問題的最優解包含其子問題的最優解時，稱該問題具有最優子結構性質。

      要證明原問題具有最優子結構性質，通常採用反證法。假設由問題的最優解導出的子問題的解不是最優的，然後再設法說明在該假設下可構造出比原問題的最優解更好的解，從而導致矛盾。

      2.子問題重疊性質

      子問題重疊性質是指由原問題分解出的子問題不是相互獨立的，存在重疊現象。

      用動態規劃法解題過程中，應當先找出最優解的結構特征，即原問題的最優解與其子問題的最優解的關聯。然後有如下兩種程式設計方法：

       1.自底向上遞歸法

       利用問題的最優子結構性質，以自底向上的方式遞歸地從子問題的最優解逐步構造出整個問題的最優解。

       2.自頂向下遞歸法(即備忘錄法)

       利用問題的最優子結構性質，用與直接遞歸法相同的控制結構自頂向下地進行遞歸求解。初始時在表格中為每個子問題存入一個標識解。在求解過程中，對每個待求子問題，首先查看表格中相應的記錄項。若記錄項為初始時的標識值，則表示該子問題是初次遇到，此時應利用問題的最優子結構性質進行遞歸求解，並將結果存入表格，以備以後查看。否則則說明該問題已被求解過，直接返回表格中相應的值即可，不必重新計算。

      當一個問題的所有子問題都要求解時，應當用自底向上遞歸法。當子問題空間中的部分子問題可不必求解時，自底向上遞歸法會進行多餘的計算，此時應採用自頂向下遞歸法。

3.貪心

      當一個問題具有最優子結構性質時，可用動態規劃法求解。但有時會有比動態規劃更簡單更直接效率更高的演算法——貪心法。貪心法總是做出在當前看來最好的選擇，也就是說貪心法並不從整體最優考慮，它所做出的選擇只是在某種意義上的局部最優選擇。雖然貪心法並不能對所有問題都得到整體最優解，但是對許多問題它能產生整體最優解。有些情況下，貪心法雖然不能得到整體最優解，但其最終結果卻是最優解的很好的近似。

      貪心法常用於解決最優化問題。對一個最優化問題可否應用貪心法，取決於該問題是否具有如下兩個性質：

      1.貪心選擇性質

      貪心選擇性質是指原問題總有一個整體最優解可通過當前的局部最優選擇，即貪心選擇來達到。

      對於一個具體問題，要確定它是否具有貪心選擇性質，通常可考察問題的一個整體最優解，並證明可修改這個最優解，使其以貪心選擇開始。由此證明該問題總有一個最優解可通過貪心選擇得到，即具有貪心選擇性質。

     2. 最優子結構性質

      這一點與動態規劃相同。做出貪心選擇後，由於最優子結構性質，原問題簡化為規模更小的類似子問題。如果將子問題的最優解和之前所做的貪心選擇合併，則可得到原問題的一個最優解。

      貪心問題的整體最優解可通過一系列局部的最優選擇，即貪心選擇來達到。這也是貪心法與動態規劃的主要區別。在動態規劃中，每一步所做出的選擇往往依賴於相關子問題的解。因而只有在解出相關子問題後，才能做出選擇。而在貪心法中，僅做出當前狀態下的最好選擇，即局部最優選擇。然後再去解做出這個選擇之後產生的相應的子問題。貪心法所做出的貪心選擇可以依賴於以往所做過的選擇，但絕不依賴於將來所做的選擇，也不依賴於子問題的解。正是由於這種差別，動態規劃通常以自頂向上的方式解各子問題，而貪心法通常以自頂向下的方式進行，以迭代的方式做出相繼的貪心選擇，每做出一次貪心選擇就將所求問題簡化為規模更小的子問題。

4.回溯

      回溯法是對問題的解空間樹進行深度優先搜索 ，但是在對每個節點進行DFS之前，要先判斷該節點是否有可能包含問題的解。如果肯定不包含，則跳過對以該節點為根的子樹的搜索，逐層向其祖先節點回溯。如果有可能包含，則進入該子樹，進行DFS。  

      回溯法通常的解題步驟如下：

     (1)定義問題的解空間。

     (2)將解空間組織成便於進行DFS的結構，通常採用樹或圖的形式。

     (3)對解空間進行DFS，併在搜索過程中用剪枝函數避免無效搜索。

      用回溯法解題時並不需要顯式地存儲整個解空間，而是在DFS過程中動態地產生問題的解空間。在任何時刻，演算法只保存從根節點到當前節點的路徑。如果解空間樹的高度為h，則回溯法的空間複雜度通常為O(h) 

      用回溯法解題時，常會遇到以下兩類典型的解空間樹：

      (1)當所給的問題是從n個元素的集合S中找出S滿足某種性質的子集時，相應的解空間樹稱為子集樹，例如http://www.cnblogs.com/laifeiyao/p/3481800.html

      (2)當所給的問題是找出n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹，例如http://www.cnblogs.com/laifeiyao/p/3492758.html

      回溯法中的剪枝函數通常分為兩類：

      (1)用約束函數在指定節點處剪去不滿足約束的子樹，例如http://www.cnblogs.com/laifeiyao/p/3481800.html

      (2)用限界函數在指定節點處剪去得不到最優解的子樹，例如http://www.cnblogs.com/laifeiyao/p/3492758.html

5.分支限界      

      回溯法是對解空間進行深度優先搜索，事實上任何搜索遍整個解空間的演算法均可解決問題。所以採用通用圖搜索(樹可抽象為特殊的圖)的任何實現作為搜索策略均可解決問題，只要做到窮舉即可。除了深度優先搜索之外，我們還可採用廣度優先搜索，而分支限界法則是對解空間進行優先順序優先搜索。

      分支限界法的搜索策略是，在當前節點處，先生成其所有的子節點(分支)，併為每個滿足約束條件的子節點計算一個函數值(限界)，再將滿足約束條件的子節點全部加入解空間樹的活結點優先隊列。然後再從當前的活節點優先隊列中選擇優先順序最大的節點(節點的優先順序由其限界函數的值來確定) 作為新的當前節點。重覆這一過程，直到到達一個葉節點為止。所到達的葉節點就是最優解。