參考博客：https://blog.csdn.net/Bloodyrabbits/article/details/78445036?

一、遞歸與分支策略

1.分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

2.如果原問題可分割成k個子問題（1＜k≤n），且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。

3.由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。

4.程序直接或間接調用自身的編程技巧稱為遞歸算法 （Recursion）。

5.遞歸通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解。

6.遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。

7.遞歸優秀在代碼簡潔，但首先需要有清晰的思路理清遞歸的循環條件及出口。

8.有時遞歸需要多次重復某一計算，可以用數組記錄下需要的數據進行調用大大降低空間復雜度。

9.遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

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

分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；

解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；

合并：將各個子問題的解合并為原問題的解。

11.在用分治法設計算法時，最好使子問題的規模大致相同。如分成大小相等的k個子問題，許多問題可以取k＝2。

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

（1）該問題的規模縮小到一定的程度就可以容易地解決；

（2）該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；

（3）利用該問題分解出的子問題的解可以合并為該問題的解；

（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

二、貪心算法

1.在求最優解問題的過程中，依據某種貪心標準，從問題的初始狀態出發，直接去求每一步的最優解，通過若干次的貪心選擇，最終得出整個問題的最優解，這種求解方法就是貪心算法。

2.從貪心算法的定義可以看出，貪心算法不是從整體上考慮問題，它所做出的選擇只是在某種意義上的局部最優解，而由問題自身的特性決定了該題運用貪心算法可以得到最優解。

3.如果一個問題可以同時用幾種方法解決，貪心算法應該是最好的選擇之一。

4.貪心算法是一種在每一步選擇中都采取在當前狀態下最好或最優的選擇，希望得到結果是最好或最優的算法。

5.貪心算法是一種能夠得到某種度量意義下的最優解的分級處理方法，通過一系列的選擇得到一個問題的解，而它所做的每一次選擇都是當前狀態下某種意義的最好選擇。即希望通過問題的局部最優解求出整個問題的最優解。

6.這種策略是一種很簡潔的方法，對許多問題它能產生整體最優解，但不能保證總是有效，因為它不是對所有問題都能得到整體最優解。

7.利用貪心策略解題，需要解決兩個問題：

（1）該題是否適合于用貪心策略求解；

（2）如何選擇貪心標準，以得到問題的最優/較優解。

8.貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。

（1）在動態規劃算法中，每步所做的選擇往往依賴于相關子問題的解，因而只有在解出相關子問題后，才能做出選擇。

（2）在貪心算法中，僅在當前狀態下做出最好選擇，即局部最優選擇，然后再去解出這個選擇后產生的相應的子問題。

9.當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。

10.運用貪心策略在每一次轉化時都取得了最優解。問題的最優子結構性質是該問題可用貪心算法或動態規劃算法求解的關鍵特征。

11.貪心算法的每一次操作都對結果產生直接影響，而動態規劃則不是。

12.貪心算法對每個子問題的解決方案都做出選擇，不能回退；動態規劃則會根據以前的選擇結果對當前進行選擇，有回退功能。

13.動態規劃主要運用于二維或三維問題，而貪心一般是一維問題。

14.使用貪心算法求解問題應該考慮如下幾個方面：

（1）候選集合A：為了構造問題的解決方案，有一個候選集合A作為問題的可能解，即問題的最終解均取自于候選集合A。

（2）解集合S：隨著貪心選擇的進行，解集合S不斷擴展，直到構成滿足問題的完整解。

（3）解決函數solution：檢查解集合S是否構成問題的完整解。

（4）選擇函數select：即貪心策略，這是貪心法的關鍵，它指出哪個候選對象最有希望構成問題的解，選擇函數通常和目標函數有關。

（5）可行函數feasible：檢查解集合中加入一個候選對象是否可行，即解集合擴展后是否滿足約束條件。

貪心算法的一般流程

//A是問題的輸入集合即候選集合
Greedy(A)
{
S={ };　　　　　　　　　　　//初始解集合為空集
while (not solution(S))　　//集合S沒有構成問題的一個解
{
x = select(A);　　　　　//在候選集合A中做貪心選擇
if feasible(S, x)　　　　//判斷集合S中加入x后的解是否可行
S = S+{x};

A = A-{x};
}

return S;

｝

15.原則上來說對于有多種變量的問題來說動態規劃能夠做出最正，確的解答，但貪心算法對于某些適用于上述規則的問題可以大幅縮短運算。

16.貪心算法是在最短的時間內找出當前一步的最優解，但最終組合到一起時卻不一定是最優的。

下面舉一個例子

給定一些數組，要求取出的數組相互之間無交且包含的區間范圍最大。根據貪心算法，首先按照每個數組的尾部從小到大排序，隨后判斷下一個數組的頭部是否大于當前數組的尾部，若不是的話則這兩個數組為符合要求的數組。在數組繁多的情況下這種算法無疑大幅度減少了運算時間，但是一定正確嗎？

[200，300]，[1，301]，[400，500]，我們一眼就可以看出，選擇后面兩個數組包含的區間范圍最大，然而根據貪心算法第一個數組可以取到而第二個數組和第一個數組有交因而唄舍棄。當然，這個例子選取的數組較少，若是有很多個數組哪怕最開始選到的數組不是最優的，后面的其他數組反而會因此被選中加入區間中最后得到最大的區間。由此看來，貪心算法依然是解決問題的最快方法，但舍棄了嚴謹性一味追求greedy（貪婪）卻勢必在一些時候得到的不是最優的，在時間有限的范圍內，貪心算法能找到相對來說最優的結果對我們來說已經足夠了。

17.貪心算法不只是一種算法，更是一種思想，讓我們看到問題抽絲剝繭看到最里面的一部分，有些像數學函數一樣把多個變量都由一個變量的不同函數分別表示，最終只剩下一個變量，貪心算法也是如此。當找到問題的本質時，就能以最短的時間得到最優的結果。

三、回溯算法

1.回溯法是一種組織搜索的一般技術，有“通用的解題法”之稱，用它可以系統的搜索一個問題的所有解或任一解。

2.有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。

3.回溯可以系統地搜索一個問題的所有解或任意解，既有系統性又有跳躍性。
4.回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。
5.這種以深度優先的方式系統地搜索問題的解的方法稱為回溯法。

6.應用回溯法求解時，需要明確定義問題的解空間。問題的解空間應至少包含問題的一個（最優）解。

7.在生成解空間樹時，定義以下幾個相關概念：
活結點：如果已生成一個結點而它的所有兒子結點還沒有全部生成，則這個結點叫做活結點。

擴展結點：當前正在生成其兒子結點的活結點叫擴展結點（正擴展的結點）。
死結點：不再進一步擴展或者其兒子結點已全部生成的結點就是死結點。
8.在確定了解空間的組織結構后，回溯從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。

這個開始結點成為一個活結點，同時成為當前的擴展結點。在當前的擴展結點，搜索向深度方向進入一個新的結點。這個新結點成為一個新的活結點，并成為當前的擴展結點。

若在當前擴展結點處不能再向深度方向移動，則當前的擴展結點成為死結點，即該活結點成為死結點。此時回溯到最近的一個活結點處，并使得這個活結點成為當前的擴展結點。

回溯法以這樣的方式遞歸搜索整個解空間（樹），直至滿足中止條件。

9.在回溯法搜索解空間樹時，通常采用兩種策略（剪枝函數）避免無效搜索以提高回溯法的搜索效率：

用約束函數在擴展結點處減去不滿足約束條件的子樹。

用限界函數減去不能得到最優解的子樹。

10.有時問題是要從一個集合的所有子集中搜索一個集合，作為問題的解。或者從一個集合的排列中搜索一個排列，作為問題的解。

11.回溯算法可以很方便地遍歷一個集合的所有子集或者所有排列。

12.當問題是要計算n個元素的子集，以便達到某種優化目標時，可以把這個解空間組織成一棵子集樹。

13.遍歷子集樹的任何算法，其計算時間復雜度都是Ω(2n)。

14.當所給的問題是確定n個元素滿足某種性質的排列時，可以把這個解空間組織成一棵排列樹。

15.排列樹通常有n!個葉子結點。因此遍歷排列樹時，其計算時間復雜度是Ω(n!)?

16.回溯算法是要在可行解中找最優解。

17.隨著深度搜索的進行，子集樹的擴展節點不變，排列樹的擴展節點變少。

18.對于深度搜索來說，搜索下去就有可能再回到這個節點。

19.對于排列樹很多時候需要注意恢復現場。

四、分支限界算法

1.分支限界法是一個用途十分廣泛的算法，運用這種算法的技巧性很強，不同類型的問題解法也各不相同。

2.分支限界法的基本思想是對有約束條件的最優化問題的所有可行解（數目有限）空間進行搜索。

（1）該算法在具體執行時，把全部可行的解空間不斷分割為越來越小的子集（稱為分支），并為每個子集內的解的值計算一個下界或上界（稱為限界）。

（2）在每次分支后，對凡是界限超出已知可行解值那些子集不再做進一步分支。這樣，解的許多子集（即搜索樹上的許多結點）就可以不予考慮，從而縮小了搜索范圍。

（3）這一過程一直進行到找出可行解為止，該可行解的值不大于任何子集的界限。

（4）這種算法一般可以求得最優解。

4.在分支限界法中，每一個活結點只有一次機會成為擴展結點。

（1）活結點一旦成為擴展結點，就一次性產生其所有兒子結點。

（2）在這些兒子結點中，導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中。

（3）從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。

（4）這個過程一直持續到找到所需的解或活結點表為空時為止。

5.從活結點表中選擇下一個活結點作為新的擴展結點，分支限界算法通常可以分為兩種形式：

（1）FIFO（First In First Out）分支限界算法

按照先進先出（FIFO）原則選擇下一個活結點作為擴展結點，即從活結點表中取出結點的順序與加入結點的順序相同。

（2）最小耗費或最大收益分支限界算法

在這種情況下，每個結點都有一個耗費或收益。

根據問題的需要，可能是要查找一個具有最小耗費的解，或者是查找一個具有最大收益的解。

6.實現分支限界算法時，首先確定目標值的上下界，邊搜索邊減掉搜索樹的某些分支，提高搜索效率。

7.在搜索時，絕大部分需要用到剪枝。“剪枝”是搜索算法中優化程序的一種基本方法，需要通過設計出合理的判斷方法，以決定某一分支的取舍。

8.若我們把搜索的過程看成是對一棵樹的遍歷，那么剪枝就是將樹中的一些“死結點”，不能到達最優解的枝條“剪”掉，以減少搜索的時間。

9.分支限界法類似于回溯法，是一種在問題的解空間樹T上搜索問題解的算法。

10.一般情況下，分支限界法與回溯法的求解目標不同。回溯法的求解目標是找出T中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標函數值達到極大或極小的解，即在某種意義下的最優解。

五、動態規劃

1.動態規劃是解決多階段決策問題的一種方法。

2.多階段決策問題：如果一類問題的求解過程可以分為若干個互相聯系的階段，在每一個階段都需作出決策，并影響到下一個階段的決策。

3.多階段決策問題，就是要在可以選擇的那些策略中間，選取一個最優策略，使在預定的標準下達到最好的效果。

4.最優性原理
（1）不論初始狀態和第一步決策是什么，余下的決策相對于前一次決策所產生的新狀態，構成一個最優決策序列。

（2）最優決策序列的子序列，一定是局部最優決策子序列。

（3）包含有非局部最優的決策子序列，一定不是最優決策序列。

5.動態規劃的指導思想
（1）在做每一步決策時，列出各種可能的局部解.

（2）依據某種判定條件，舍棄那些肯定不能得到最優解的局部解。

（3）以每一步都是最優的來保證全局是最優的。

6.動態規劃的幾個概念

階段：據空間順序或時間順序對問題的求解劃分階段。

狀態：描述事物的性質，不同事物有不同的性質，因而用不同的狀態來刻畫。對問題的求解狀態的描述是分階段的。

決策：根據題意要求，對每個階段所做出的某種選擇性操作。

狀態轉移方程：用數學公式描述與階段相關的狀態間的演變規律。

7.大多數問題動態規劃都可以解決，但是太慢。因此有些問題貪心確實比動態快的多。不過相對的貪心解決問題并不如動態規劃精細，得出來的不一定是最優解，只能說是相對最優，根據情況選擇不同的算法解決問題才是王道。

轉載于:https://www.cnblogs.com/henuliulei/p/9893051.html

總結

以上是生活随笔為你收集整理的浅析几种常见算法(转载)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。