任何一個可以用計算機求解的問題所需要的計算時間都與其規(guī)模有關。

以上五種可以理解為一種思想废亭，而不是算法。

1. 分治法 Divide and Conquer
2. 動態(tài)規(guī)劃法 Dynamic Programing
3. 貪心法 Greedy
4. 回溯法 Back Tracking
5. 分支限界法 Branch and Bound

先拋出一個對比表格具钥，可以當總結豆村，也可以有一個感性認識。

分治法 Divide and Conquer

適用情況：

1. 該問題的規(guī)模縮小到一定的程序就可以容易解決宁玫。
2. 該問題可以分解成若干個 規(guī)模較小的相同問題粗恢，即該問題具有最優(yōu)子結構的性質。
3. 該問題分解出的子問題的解可以合并為該問題的解撬统。
4. 該問題所分解出的各個子問題是相互獨立的适滓，即子問題之間不包含公共的子問題。

適用情況說明：

1. 第一條特征恋追，絕大多問題都可以滿足凭迹，因為問題的計算復雜性一般是追著問題規(guī)模的增加而增加。
2. 第二條特征苦囱，是應用分治法的前提嗅绸，也是大多數問題可以滿足的，此特征反應了遞歸思想的應用撕彤。
3. 第三條特征鱼鸠，是關鍵猛拴，能否使用分治法完全取決于問題是否滿足該特征，如果具備第一和第二特征蚀狰，而不具備第三特征愉昆，則可以考慮用 貪心法和動態(tài)規(guī)劃法。
4. 第四條特征麻蹋，涉及分治法的效率跛溉，如果各個子問題是不獨立的，那么分治法要做許多不必要的工作扮授，重復地解決公共子問題芳室，此時雖然可用分治法，但一般用動態(tài)規(guī)劃法較好刹勃，可以保存公共問題的解堪侯。

基本步驟：

分治法在每一層遞歸上都有三個步驟：

1. 分解 Divider，將原問題分解成若干個規(guī)模較小荔仁，相互獨立伍宦，與原問題形式相同 的子問題。
2. 解決 Conquer乏梁，若子問題規(guī)模較小且容易被解決雹拄，則直接解，否則遞歸地解各個子問題掌呜。
3. 合并 Combine，將子問題的解合并為原問題的解坪哄。

設計模式：

Divide-and-Conquer(P)
if |P| <= n0
    then return( ADHOC(P) )
將P分解為較小的子問題 P1, P2,…,Pk
for  i - 1 to k
    do  yi - Divide-and-Conquer(Pi) 遞歸解決Pi
T - MERGE(y1, y2,…,yk) 合并子問題
return（T)

其中质蕉，|P| 表示問題P的規(guī)模；n0表示閾值翩肌，當問題P規(guī)模不超過n0時模暗，問題容易解出，不必再繼續(xù)分解念祭；ADHOC(P) 表示分治法中的基本子算法兑宇，用于直接解小規(guī)模的問題P；MERGE (y1, y2,…,yk) 表示分治法中合并子算法粱坤。

復雜性分析：

// todo

思維過程：
類似于數學歸納法隶糕，找到解決問題的求解方程，根據方程公式設計遞歸程序站玄。

1. 先找到最小問題規(guī)模時的求解法枚驻。
2. 考慮隨著問題規(guī)模增大時的求解法
3. 找到求解的遞歸函數式后，設計遞歸程序即可株旷。

動態(tài)規(guī)劃 dynamic programming

基本概念

過程：每次決策依賴于當前（階段）狀態(tài)再登，又隨即引起狀態(tài)的轉移。一個決策序列就是在變化的狀態(tài)中產生的，所以這種多階段最優(yōu)化決策解決問題的過程就成為動態(tài)規(guī)劃锉矢。

基本思想和策略：

與分治法類似梯嗽，也是將求解的問題分解為若干個子問題（階段），按順序求解子階段沽损，前一子問題的解灯节，為后一子問題的求解提供了有用信息。在求解任一子問題時缠俺，列出各種可能的局部解显晶，通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解壹士。依次解決各子問題磷雇，最后一個子問題就是初始問題的解。

特點：解決重疊子問題躏救，為了減少重復計算唯笙，對每一個問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數組中盒使。

與分治法的區(qū)別：適合于動態(tài)規(guī)劃法求解的問題崩掘，經分解后得到的子問題往往不是相互獨立的。（即重疊子問題少办，下一階段的求解是建立在上一階段的解的基礎上苞慢，可利用保存的解）

適用情況：

1. 最優(yōu)化原理：該問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，即具有最優(yōu)子結構
2. 無后效性：即某階段狀態(tài)一旦確定英妓，就不受這個狀態(tài)以后決策的影響挽放，只與當前狀態(tài)有關。
3. 有重疊子問題：一個子問題在下一階段決策中可能被多次使用到蔓纠。子問題的空間要很小辑畦，遞歸算法可反復地解同樣的子問題，而不是產生新的子問題腿倚。相同且獨立纯出。（該性質不是動態(tài)規(guī)劃適用的必要條件，但如果問題沒有該性質敷燎，那動態(tài)規(guī)劃算法痛其他算法相比就不具備優(yōu)勢）

通常應用于最優(yōu)問題暂筝，即要做出一組選擇以達到最優(yōu)解。

舉例：無權最短路徑硬贯，無權最長簡單路徑乖杠。前者有最優(yōu)子結構，而后者沒有澄成，故不能用動態(tài)規(guī)劃求解胧洒。

求解的基本步驟：

動態(tài)規(guī)劃所處理是一個多階段決策問題畏吓，一般由初始狀態(tài)開始，通過中間階段決策選擇卫漫，達到結束狀態(tài)菲饼。
這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線列赎。（通常是最優(yōu)的活動路線）

初始狀態(tài) -> 決策1 -> 決策1 -> … -> 決策n -> 結束狀態(tài)

動態(tài)規(guī)劃的設計有著一定的模式宏悦，要經歷以下幾個步驟：

1. 劃分階段：按照問題的時間和空間特征，把問題分成若干個階段包吝。注意階段一定要是有序的或者是可排序的饼煞，否則問題就無法求解。
2. 確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時 所處于的各種客觀情況用不同的狀態(tài)表示出來诗越。當然狀態(tài)的選擇要滿足無后效性砖瞧。
3. 確定決策并寫出狀態(tài)轉移方程：因為決策和狀態(tài)轉移有著天然的聯系，狀態(tài)轉移就是根據上一階段的狀態(tài)和決策來導出本階段的狀態(tài)嚷狞。所以如果確定了決策块促，狀態(tài)轉移方程即可寫出。但事實上常常反過來做床未，根據相鄰兩個階段的狀態(tài)之間的關系來確定 決策方法和狀態(tài)轉移方程竭翠。
4. 尋找邊界條件：給出狀態(tài)轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件薇搁。

一般斋扰，只要解決問題的階段卿樱、狀態(tài)和狀態(tài)轉移決策確定了俄烁，就可以寫出狀態(tài)轉移方程（包括邊界條件）芦瘾。

實際應用中芒粹，可以按以下簡化的步驟進行設計：

1. 分析最優(yōu)解的性質，并刻畫其結構特征朵诫。
2. 遞歸的定義最優(yōu)解。
3. 以自底向上或自頂向下的記憶化方式（備忘錄法）計算出最優(yōu)值。
4. 根據計算最優(yōu)值時得到的信息绝编，構造問題的最優(yōu)解。

貪心算法 greedy

基本概念

所謂貪心算法是指貌踏，在對問題求解時十饥，總是做出在當前看來是最好的選擇。也就是說祖乳，不從整體最優(yōu)上加以考慮逗堵，他所做出的僅是在某種意義上的局部最優(yōu)解。

貪心算法沒有固定的算法框架眷昆，算法設計的關鍵是貪心策略的選擇蜒秤。

必須注意的是汁咏，貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具有無后效性作媚，即某個狀態(tài)以后的過程不會影響以前的狀態(tài)攘滩，只與當前狀態(tài)有關。

基本思路

1. 建立數學模型來描述問題纸泡。
2. 把求解的問題分成若干個子問題漂问。
3. 對每一個子問題進行求解，得到子問題的局部最優(yōu)解女揭。
4. 把子問題的局部最優(yōu)解合成原來問題的一個解蚤假。

適用的問題

前提：局部最優(yōu)策略能產生全局最優(yōu)解。
實際上吧兔，貪心算法的適用情況較少磷仰。判斷是否適用于貪心算法可以舉幾個實際數據進行分析。

實現框架

從問題的某一個初始解出發(fā)掩驱；
while(能朝給定目標前進一步){
利用可行的決策芒划，求出可行解的一個解元素；
}
由所有解元素組合成問題的一個解欧穴；

貪心策略的選擇

因為貪心算法只能通過解局部最優(yōu)解的策略來達到全局最優(yōu)解民逼，因此，一定要注意判斷問題是否適合采用貪心算法策略涮帘，找到的解是否一定是問題的最優(yōu)解拼苍。

例題分析

1. 背包問題：有一個背包，容量是 M=150调缨。有7個物品疮鲫，可以分割成任意大小。要求盡可能讓裝入背包中的物品總價值最大弦叶，但不能超過總容量俊犯。

   物品	A	B	C	D	E	F	G
   重量	35	30	60	50	40	10	25
   價值	10	40	30	50	35	40	30

   貪心策略：

   1. 每次挑選 價值最大 的物品
   2. 每次挑選 重量最小 的物品
   3. 每次挑選 單位重量價值最大 的物品

   以上三種策略都不符合，可能針對本題 3 合適伤哺，但不具有統(tǒng)一性燕侠，更換了物品個數、背包容量等參數就不滿足了立莉。

2. 錢幣問題

   比如有錢幣1元绢彤、3元、4元蜓耻，要拿6元茫舶。貪心算法的解：先拿 4元，再拿 1 元刹淌，再拿 1元饶氏。一共三張錢讥耗，但實際最優(yōu)兩張3元就夠了。

回溯法 backtracking

概念

回溯算法嚷往，實際上是一個類似枚舉的搜索嘗試過程葛账，主要是在搜索嘗試過程中尋找問題的解，當發(fā)現已不滿足求解條件時皮仁，就“回溯”返回籍琳，嘗試別的路徑。

回溯法是一個選優(yōu)搜索法贷祈，按選優(yōu)條件向前搜索趋急，以達到目標。但當搜索到某一步時势誊，發(fā)現原先選擇并不優(yōu)或達不到目標呜达，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法粟耻，滿足回溯條件的某個狀態(tài)的點稱為“回溯點”

許多復雜的查近，規(guī)模較大的問題都使用回溯法，有“通用解題方法”的美稱挤忙。

基本思想

在包含問題的所有解的解空間樹中霜威，按照深度優(yōu)先搜索的策略，從根節(jié)點出發(fā)深度探索解空間樹册烈。當搜索到某一結點時戈泼，要先判斷該結點是否包含問題的解，如果包含赏僧，就從該結點出發(fā)繼續(xù)探索下去大猛；如果不包含，則逐層向其祖先結點回溯淀零。

其實回溯法就是對隱式圖的深度優(yōu)先搜索算法挽绩。

求所有解：要回溯到根，且根結點的所有可行的子樹都要被搜索遍才能結束驾中。
求任一解：只要搜索到問題的一個解就可以結束唉堪。

解題步驟

1. 針對所給的問題，確定問題的解空間哀卫。明確定義問題的解空間，問題的解空間應該至少包含問題的一個（最優(yōu)）解撬槽。
2. 確定結點的擴展搜索規(guī)則
3. 以深度優(yōu)先方式搜索解空間此改，并在搜索過程中用剪枝函數避免無效搜索。

算法框架

問題框架：
設問題的解是一個 n 維向量(a1, a2, … ,an)侄柔，約束條件是 ai (i=1, 2, ... , n) 之間滿足某種條件共啃，記為f(ai)占调。

非遞歸回溯框架

`int a[n](),i; 初始化數組a[]();
 i = 1;
 while (i\>0(有路可走)   and  (未達到目標))  // 還未回溯到頭
 {
     if(i \> n)  {   // 搜索到葉結點
           搜索到一個解，輸出移剪；
     } else {          // 處理第i個元素
          a[i]()第一個可能的值究珊；
          while(a[i]()在不滿足約束條件且在搜索空間內) {
              a[i]()下一個可能的值；
          }
           if(a[i]()在搜索空間內)  {
              標識占用的資源纵苛；
              i = i+1;                              // 擴展下一個結點
          } else {
              清理所占的狀態(tài)空間剿涮；            // 回溯
               i = i –1; 
          }
}

遞歸回溯框架

try(int i) {
    if ( i \> n){
        輸出結果
    } else {
        for( j=下界; j\<= 上界; j++) {
            if (fun(j)){
                a[i][7] = j;
                try( i + 1);
                回溯前的清理工作（如a[i][8]置空等）；
            }
        }
    }
}

分支限界法 Branch and Bound

基本描述

類似于回溯法攻人，也是一種在問題的解空間樹T上搜索問題解的算法取试。

但是一般情況下，分支限界法與回溯法求解目標不同怀吻。

1. 回溯法的求解目標是：找出T中滿足約束條件的所有解瞬浓。
   2. 分支限界法的求解目標是：找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標函數值達到極大或極小的解蓬坡，即在某種意義下的最優(yōu)解猿棉。

分支搜索算法

所謂“分支”就是采用廣度優(yōu)先的策略，依次搜索E-結點的所有分支屑咳，也就是所有的相鄰結點萨赁，拋棄不滿足約束條件的結點，其余結點加入活結點表乔宿，然后從表中選擇一個結點作為下一個E-結點位迂，繼續(xù)搜索。
選擇下一個E-結點的方式不同详瑞，則會有幾種不同的分支搜索方式：

1. FIFO搜索
2. LIFO搜索
3. 優(yōu)先隊列式搜索

分支限界搜索算法

一般過程

由于求解目標不同掂林，導致分支限界法與回溯法在解空間樹T上的搜索方式也不相同。

• 回溯法：以 深度優(yōu)先 的方式搜索空間樹T坝橡。
• 分支限界法：以 廣度優(yōu)先 或 最小耗費(最大效益)優(yōu)先 方式探索空間樹T泻帮。

分支限界法的搜索策略是：
問題的解空間樹是表示問題解空間的一棵有序樹，常見的有子集樹和排列樹计寇。
在搜索問題的解空間樹時锣杂，分支限定法與回溯法對當前擴展結點所使用的拓展方式不同。
在分支限界法中番宁，每一個活結點只有一次機會成為擴展結點元莫。
在擴展結點處，一次性生成其所有的兒子結點(分支)蝶押，在這些兒子結點中踱蠢，那些導致不可行解或導致非最優(yōu)解的兒子結點會被舍棄，其余兒子結點被加入活結點表中棋电。
然后再從當前的的活結點中選擇下一個擴展結點茎截。為了有效地選擇下一擴展結點苇侵，以加速搜索的進程，在每一伙結點處企锌，計算一個函數值（限界）榆浓，并根據這些已計算出的函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點撕攒，使搜索朝著解空間樹上有最優(yōu)解的分支推進陡鹃，以便盡快找出一個最優(yōu)解。

算法差異

分治法打却、動態(tài)規(guī)劃法杉适、貪心算法三者的相似之處： 都需要將問題劃分為一個個子問題，然后通過解決這些子問題來解決最終問題柳击。

分治法和動態(tài)規(guī)劃的區(qū)別

共同點：

1. 都要求原問題具有 最優(yōu)子結構性質猿推。
2. 都將原問題分成若干個子問題
3. 然后都將子問題的解合并，形成原問題的解捌肴。

不同點：

1. 分治法是分解成若干個互不相交的子問題蹬叭；動態(tài)規(guī)劃是將問題分解成若干個相互重疊的子問題；
2. 分治法求解子問題重疊部分會被重復計算多次状知；動態(tài)規(guī)劃每個子問題只求解一次并將其保存在一個表中秽五，遇到重疊部分查表得到解，避免重復計算饥悴。

動態(tài)規(guī)劃和貪心法的區(qū)別

共同點：

1. 都是遞推算法坦喘。
2. 都是對子問題樹進行修剪。
3. 都要求原問題具有 最優(yōu)子結構性質西设。

不同點：

1. 動態(tài)規(guī)劃通常以自底向上的方式解各子問題瓣铣，采用遞歸的方式；貪心法通常以自頂向下的方式贷揽，用迭代的方式做出相繼的貪心選擇棠笑，每做一次貪心選擇就將問題簡化為規(guī)模更小的問題。
2. 動態(tài)規(guī)劃用到之前的最優(yōu)解禽绪，貪心算法則不用蓖救。貪心無法解決動態(tài)規(guī)劃的問題，但動態(tài)規(guī)劃能解決貪心的問題印屁。
3. 貪心算法解決的問題一定能用動態(tài)規(guī)劃法循捺，但貪心算法效率高于動態(tài)規(guī)劃。

貪心算法是通過一系列選擇來給出某一問題的最優(yōu)解雄人。每一個決策點从橘，做出當時看起來是最佳的選擇。當前選擇可能要依賴于已經做出的所有選擇，但不依賴于有待于做出的選擇或子問題的解洋满。因此，貪心算法通常是自頂向下地做出貪心選擇珍坊，不斷地將給定的問題實例規(guī)約為更小的問題牺勾。貪心算法劃分子問題的結果，通常是僅存在一個非空的子問題阵漏。
而動態(tài)規(guī)劃中驻民，每一步要做出選擇，但這些選擇依賴于子問題的解履怯。因此解動態(tài)規(guī)劃問題一般是自底向上回还，從小問題處理至大問題。

回溯法和分支限界的區(qū)別

共同點：

1. 一種在問題的解空間樹上搜索問題解的算法

不同點：

1. 求解目標不同叹洲∧叮回溯法：找出滿足約束條件的所有解；分支限界法：盡快找出滿足約束條件的一個解运提。
2. 搜索方法不同蝗柔。回溯法：深度優(yōu)先方法搜索解空間民泵；分支限界法：廣度優(yōu)先或以最小消耗優(yōu)先的方式搜索解空間癣丧。
3. 對擴展結點的擴展方式不同≌蛔保回溯法：如果當前擴展結點不能再縱深方向移動胁编，則當前擴展結點成為死結點，此時回溯到最近的一個活結點使其成為擴展結點鳞尔；分支限界法：每一次活結點只有一次機會成為擴展結點嬉橙，一旦成為擴展結點，就一次性產生其所有兒子結點铅檩。
4. 存儲空間的要求不同：回溯法：性饕摹；分支限界法：大昧旨；但內存有限時拾给，回溯法成功可能性更大。

參考資料

感謝以下文章作者

五類常見算法小記 （遞歸與分治兔沃，動態(tài)規(guī)劃蒋得，貪心，回溯乒疏，分支界限法）
Leetcode常用五大算法思想
分治法额衙，動態(tài)規(guī)劃法，貪心法，回溯法窍侧，分支限界法的區(qū)別和聯系以及適用情況
分支限界法和回溯法的區(qū)別