《數據結構與算法分析》一書中，除了分篇章介紹的不同類型數據結構及其具體實現算法。不同類型的常用算法思想貫通了全書，本文予以彙總並逐一介紹。
1. 遞推法
2. 遞歸法
3. 窮舉法（枚舉法）
4. 貪心算法（貪婪算法）
5. 分治法(Divide and Conquer)
6. 動態規劃法
7. 迭代法
8. 分支界限法
9. 回溯法
1. 遞推法
遞推是序列計算機中的一種常用算法。它是按照一定的規律來計算序列中的每個項，通常是通過計算機前面的一些項來得出序列中的指定項的值。
其思想是把一個複雜的龐大的計算過程轉化為簡單過程的多次重複，該算法利用了計算機速度快和不知疲倦的機器特點。
使用場景：
- 統計算法的時間複雜度（比如多層嵌套遍歷時）；
- 現實場景，如下列示例所示：
題：植樹節那天，有五位同學參加了植樹活動，他們完成植樹的棵樹都不相同。問第一位同學植了多少棵時，他指著旁邊的第二位同學說比他多植了兩棵；追問第二位同學，他又說比第三位同學多植了兩棵；... 如此，都說比另一位同學多植兩棵。最後問到第五位同學時，他說自己植了10棵。到底第一位同學植了多少棵樹？
答：本程序的遞推運算可用下圖示表示：
初始值a:=10 ----- i=1,a=a+2(12) ----- i=2,a=a+2(14) ------ i=3,a=a+2(16) ----- i=4,a=a+2(18) ---- 輸出a值18
2. 遞歸法
- 程序調用自身的編程技巧稱為遞歸（recursion）。一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法。
- 遞歸法是設計和描述算法的一種有力的工具，由於它在複雜算法的描述中被經常採用，為此在進一步介紹其他算法設計方法之前先討論它。
遞歸算法特性：
- 它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重複計算，大大地減少了程序的代碼量。
- 遞歸的能力在於用有限的語句來定義對象的無限集合。
- 一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
算法設計的注意事項：
(1) 遞歸就是在過程或函數里調用自身;
(2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
使用場景：
- 磁盤目錄&文件遍歷（File，B樹結構）
- 更寬泛的樹遍歷
- 斐波那契數列的計算
【問題】 編寫計算斐波那契（Fibonacci）數列的第n項函數fib（n）。斐波那契數列為：0、1、1、2、3、……，即：
fib(0)=0;
fib⑴=1;
fib(n)=fib(n-1）+fib(n-2） （當n>1時）。
寫成遞歸函數有：
<code>int fib(int n){
if (n==0) return 0;
if (n==1） return 1;
if (n>1） return fib(n-1）+fib(n-2）；
}/<code>3. 窮舉法（枚舉法）
窮舉法，或稱為暴力破解法，其基本思路是：對於要解決的問題，列舉出它的所有可能的情況，逐個判斷有哪些是符合問題所要求的條件，從而得到問題的解。
窮舉法是利用計算機運算速度快、精確度高的特點，對要解決問題的所有可能情況，一個不漏地進行檢驗，從中找出符合要求的答案，因此枚舉法是通過犧牲時間來換取答案的全面性。
算法結構：
一般使用while循環。
使用場景：
- 密碼的破譯，即將密碼進行逐個推算直到找出真正的密碼為止。
- 例如一個已知是四位並且全部由數字組成的密碼，其可能共有10000種組合，因此最多嘗試10000次就能找到正確的密碼。理論上利用這種方法可以破解任何一種密碼，問題只在於如何縮短試誤時間。因此有些人運用計算機來增加效率，有些人輔以字典來縮小密碼組合的範圍。
4. 貪心算法（貪婪算法）
- 貪心算法是一種對某些求最優解問題的更簡單、更迅速的設計技術。
- 用貪心法設計算法的特點是一步一步地進行，常以當前情況為基礎根據某個優化測度作最優選擇，而不考慮各種可能的整體情況，它省去了為找最優解要窮盡所有可能而必須耗費的大量時間，它採用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題。
- 通過每一步貪心選擇,可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以貪婪法不要回溯。
量度標準的選擇：
- 對於一個給定的問題，往往可能有好幾種量度標準。
- 初看起來，這些量度標準似乎都是可取的，但實際上，用其中的大多數量度標準作貪婪處理所得到該量度意義下的最優解並不是問題的最優解，而是次優解。
- 因此，選擇能產生問題最優解的最優量度標準是使用貪婪算法的核心。
- 一般情況下，要選出最優量度標準並不是一件容易的事，但對某問題能選擇出最優量度標準後，用貪婪算法求解則特別有效。
貪婪算法&動態規劃算法的區別：
- 當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。運用貪心策略在每一次轉化時都取得了最優解。
- 問題的最優子結構性質是該問題可用貪心算法或動態規劃算法求解的關鍵特徵。
- 貪心算法的每一次操作都對結果產生直接影響，而動態規劃則不是。
- 貪心算法對每個子問題的解決方案都做出選擇，不能回退；動態規劃則會根據以前的選擇結果對當前進行選擇，有回退功能。
- 動態規劃主要運用於二維或三維問題，而貪心一般是一維問題。
使用場景：
- 密碼的破譯，即將密碼進行逐個推算直到找出真正的密碼為止。
- 輔幣找零錢，比如中如何找到17美元61美分的零錢（10美元+5美元+2張1美元+2個25分幣+10分幣+1分幣）。
5. 分治法(Divide and Conquer)
- 分：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
- 治：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；
- 合：將各個子問題的解合併為原問題的解。
分治法所能解決的問題一般具有以下幾個特徵：
- 該問題的規模縮小到一定的程度就可以容易地解決；
- 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；
- 利用該問題分解出的子問題的解可以合併為該問題的解；
- 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。
使用場景：
- 二分搜索（折半查找）
- 合併排序
- 快速排序
- 大整數乘法
- Strassen矩陣乘法
- 棋盤覆蓋
- 線性時間選擇
- 最接近點對問題
- 循環賽日程表
- 漢諾塔
6. 動態規劃法
- 動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。
- 動態規劃的思想是多種算法的基礎，被廣泛應用於計算機科學和工程領域。
- 動態規劃程序設計是對解最優化問題的一種途徑、一種方法，而不是一種特殊算法。
動態規劃算法特性：
- 不象前面所述的那些搜索或數值計算那樣，具有一個標準的數學表達式和明確清晰的解題方法。
- 動態規劃程序設計往往是針對一種最優化問題，由於各種問題的性質不同，確定最優解的條件也互不相同，因而動態規劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態規劃算法，可以解決各類最優化問題。
- 因此讀者在學習時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創造性的技巧去求解。
動態規劃一般可分為線性動規，區域動規，樹形動規，揹包動規四類。
- 線性動規：攔截導彈，合唱隊形，挖地雷，建學校，劍客決鬥等；
- 區域動規：石子合併， 加分二叉樹，統計單詞個數，炮兵佈陣等；
- 樹形動規：貪吃的九頭龍，二分查找樹，聚會的歡樂，數字三角形等；
- 揹包問題：01揹包問題，完全揹包問題，分組揹包問題，二維揹包，裝箱問題，擠牛奶（同濟ACM第1132題）等；
使用場景：
- 最短路徑問題 ；
- 項目管理；
- 網絡流優化；
- POJ動態規劃題目列表：
7. 迭代法
- 迭代法也稱輾轉法，是一種不斷用變量的舊值遞推新值的過程，跟迭代法相對應的是直接法（或者稱為一次解法），即一次性解決問題。
- 迭代法又分為精確迭代和近似迭代。“二分法”和“牛頓迭代法”屬於近似迭代法。迭代算法是用計算機解決問題的一種基本方法。
- 它利用計算機運算速度快、適合做重複性操作的特點，讓計算機對一組指令（或一定步驟）進行重複執行，
- 在每次執行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。
算法特性：
利用迭代算法解決問題，需要做好以下三個方面的工作：
- 確定迭代變量：在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。
- 建立迭代關係式：所謂迭代關係式，指如何從變量的前一個值推出其下一個值的公式（或關係）。迭代關係式的建立是解決迭代問題的關鍵，通常可以順推或倒推的方法來完成。
- 對迭代過程進行控制：在什麼時候結束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重複執行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定。對於前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對於後一種情況，需要進一步分析出用來結束迭代過程的條件。
使用場景：
- 舉例：驗證谷角猜想。
日本數學家谷角靜夫在研究自然數時發現了一個奇怪現象：對於任意一個自然數 n ，若 n 為偶數，則將其除以 2 ；若 n 為奇數，則將其乘以 3 ，然後再加 1。如此經過有限次運算後，總可以得到自然數 1。人們把谷角靜夫的這一發現叫做“谷角猜想”。
要求：編寫一個程序，由鍵盤輸入一個自然數 n ，把 n 經過有限次運算後，最終變成自然數 1 的全過程打印出來。
分析：定義迭代變量為 n ，按照谷角猜想的內容，可以得到兩種情況下的迭代關係式：當 n 為偶數時， n=n/2 ；當 n 為奇數時， n=n*3+1。用 QBASIC 語言把它描述出來就是：
<code>if n 為偶數 then
n=n/2
else
n=n*3+1
end if/<code>
這就是需要計算機重複執行的迭代過程。這個迭代過程需要重複執行多少次，才能使迭代變量 n 最終變成自然數 1 ，這是我們無法計算出來的。
8. 分支界限法
- 分枝界限法是一個用途十分廣泛的算法，運用這種算法的技巧性很強，不同類型的問題解法也各不相同。
- 分支定界法的基本思想是對有約束條件的最優化問題的所有可行解（數目有限）空間進行搜索。
- 該算法在具體執行時，把全部可行的解空間不斷分割為越來越小的子集（稱為分支），併為每個子集內的解的值計算一個下界或上界（稱為定界）。
- 在每次分支後，對凡是界限超出已知可行解值那些子集不再做進一步分支，這樣，解的許多子集（即搜索樹上的許多結點）就可以不予考慮了，從而縮小了搜索範圍。
- 這一過程一直進行到找出可行解為止，該可行解的值不大於任何子集的界限。因此這種算法一般可以求得最優解。
常見兩種方法：
- 隊列式(FIFO)分支限界法：按照隊列先進先出（FIFO）原則選取下一個節點為擴展節點。
- 優先隊列式分支限界法：按照優先隊列中規定的優先級選取優先級最高的節點成為當前擴展節點。
分支限界法的特性：
- 與貪心算法一樣，這種方法也是用來為組合優化問題設計求解算法的，所不同的是它在問題的整個可能解空間搜索，所設計出來的算法雖其時間複雜度比貪婪算法高。
- 它的優點是與窮舉法類似，都能保證求出問題的最佳解，而且這種方法不是盲目的窮舉搜索，而是在搜索過程中通過限界，可以中途停止對某些不可能得到最優解的子空間進一步搜索（類似於人工智能中的剪枝），故它比窮舉法效率更高。
分支限界法與回溯法的區別：
- 求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優解。
- 搜索方式的不同：回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹。
使用場景：
- 解空間樹的動態搜索：分支限界法首先確定一個合理的限界函數，並根據限界函數確定目標函數的界[down, up]；然後按照廣度優先策略遍歷問題的解空間樹，在某一分支上，依次搜索該結點的所有孩子結點，分別估算這些孩子結點的目標函數的可能取值（對最小化問題，估算結點的down，對最大化問題，估算結點的up）。如果某孩子結點的目標函數值超出目標函數的界，則將其丟棄（從此結點生成的解不會比如今已得的更好），否則入待處理表 。
9. 回溯法
回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點”。
算法的基本思想：
- 在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。
- 其實回溯法就是對隱式圖的深度優先搜索算法。
- 若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。
使用場景：
回溯算法其實是一種窮舉算法，將所有可能發生的情況都列舉一遍，選擇可行解或最優解。 用於搜索算法中，比如：
- 數獨；
- 八皇后問題；
- 全排列；
- 0-1 揹包；
- 正則表達式匹配；
- 編譯原理中語法分析等
閱讀更多 編程家園 的文章
