一、貪心算法
貪心算法（又稱貪婪算法）是指，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。
用貪心法設(shè)計(jì)算法的特點(diǎn)是一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測(cè)度作最優(yōu)選擇，而不考慮各種可能的整體情況，它省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間，它采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡(jiǎn)化為一個(gè)規(guī)模更小的子問題，通過每一步貪心選擇，可得到問題的一個(gè)最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的，所以貪心法不需要回溯。
注意：對(duì)于一個(gè)給定的問題，往往可能有好幾種量度標(biāo)準(zhǔn)。初看起來，這些量度標(biāo)準(zhǔn)似乎都是可取的，但實(shí)際上，用其中的大多數(shù)量度標(biāo)準(zhǔn)作貪婪處理所得到該量度意義下的最優(yōu)解并不是問題的最優(yōu)解，而是次優(yōu)解。因此，選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪婪算法的核心。
經(jīng)典的求最小生成樹的Prim算法和算法、計(jì)算強(qiáng)連通子圖的算法、構(gòu)造樹的算法都是漂亮的貪心算法
基本思路：
⒈建立數(shù)學(xué)模型來描述問題。
⒉把求解的問題分成若干個(gè)子問題。
⒊對(duì)每一子問題求解，得到子問題的局部最優(yōu)解。
⒋把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。
實(shí)現(xiàn)該算法的過程：
從問題的某一初始解出發(fā)；
while 能朝給定總目標(biāo)前進(jìn)一步 do
求出可行解的一個(gè)解元素；
由所有解元素組合成問題的一個(gè)可行解。
例子：
馬踏棋盤的貪心算法
【問題描述】
馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發(fā)，為馬尋找一條走遍棋盤每一格并且只經(jīng)過一次的一條最短路徑。
【貪心算法】
其實(shí)馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.就提出了一個(gè)有名的算法。在每個(gè)結(jié)點(diǎn)對(duì)其子結(jié)點(diǎn)進(jìn)行選取時(shí)，優(yōu)先選擇‘出口’最小的進(jìn)行搜索，‘出口’的意思是在這些子結(jié)點(diǎn)中它們的可行子結(jié)點(diǎn)的個(gè)數(shù)，也就是‘孫子’結(jié)點(diǎn)越少的越優(yōu)先跳，為什么要這樣選取，這是一種局部調(diào)整最優(yōu)的做法，如果優(yōu)先選擇出口多的子結(jié)點(diǎn)，那出口少的子結(jié)點(diǎn)就會(huì)越來越多，很可能出現(xiàn)‘死’結(jié)點(diǎn)（顧名思義就是沒有出口又沒有跳過的結(jié)點(diǎn)），這樣對(duì)下面的搜索純粹是徒勞，這樣會(huì)浪費(fèi)很多無用的時(shí)間，反過來如果每次都優(yōu)先選擇出口少的結(jié)點(diǎn)跳，那出口少的結(jié)點(diǎn)就會(huì)越來越少，這樣跳成功的機(jī)會(huì)就更大一些。
二、分治算法
思想：
分治算法的基本思想是將一個(gè)規(guī)模為N的問題分解為K個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。
分治法應(yīng)用場(chǎng)景：
運(yùn)用分治策略解決的問題一般來說具有以下特點(diǎn)：
1、原問題可以分解為多個(gè)子問題
這些子問題與原問題相比，只是問題的規(guī)模有所降低，其結(jié)構(gòu)和求解方法與原問題相同或相似。
2、原問題在分解過程中，遞歸地求解子問題
由于遞歸都必須有一個(gè)終止條件，因此，當(dāng)分解后的子問題規(guī)模足夠小時(shí)，應(yīng)能夠直接求解。
3、在求解并得到各個(gè)子問題的解后
應(yīng)能夠采用某種方式、方法合并或構(gòu)造出原問題的解。
不難發(fā)現(xiàn)，在分治策略中，由于子問題與原問題在結(jié)構(gòu)和解法上的相似性，用分治方法解決的問題，大都采用了遞歸的形式。在各種排序方法中，如歸并排序、堆排序、快速排序等，都存在有分治的思想。
分治法解題的一般步驟：
（1）分解，將要解決的問題劃分成若干規(guī)模較小的同類問題；
（2）求解，當(dāng)子問題劃分得足夠小時(shí)，用較簡(jiǎn)單的方法解決；
（3）合并，按原問題的要求，將子問題的解逐層合并構(gòu)成原問題的解。
三、動(dòng)態(tài)規(guī)劃
基本思想：
動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。
與分治法最大的差別是：適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨(dú)立的（即下一個(gè)子階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解）
應(yīng)用場(chǎng)景：
適用動(dòng)態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理、無后效性和重疊性。
1.最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)） 最優(yōu)化原理可這樣闡述：一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
2.無后效性 將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個(gè)狀態(tài)。換句話說，每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié)。這就是無后向性，又稱為無后效性。
3.子問題的重疊性 動(dòng)態(tài)規(guī)劃將原來具有指數(shù)級(jí)時(shí)間復(fù)雜度的搜索算法改進(jìn)成了具有多項(xiàng)式時(shí)間復(fù)雜度的算法。其中的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。
求全路徑最短路徑的Floyd算法就是漂亮地運(yùn)用了動(dòng)態(tài)規(guī)劃思想。
下面是我找到的一個(gè)關(guān)于0-1背包問題的動(dòng)態(tài)規(guī)劃思想PPT截圖：
問題描述：
給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?
對(duì)于一種物品，要么裝入背包，要么不裝。所以對(duì)于一種物品的裝入狀態(tài)可以取0和1.我們?cè)O(shè)物品i的裝入狀態(tài)為xi,xi∈ (0,1)，此問題稱為0-11背包問題。
數(shù)據(jù)：物品個(gè)數(shù)n=5,物品重量w[n]={0，2算法設(shè)計(jì)與分析堆和堆排序ppt，2，6，5，4},物品價(jià)值V[n]={0，6，3，5，4，6},
（第0位，置為0，不參與計(jì)算，只是便于與后面的下標(biāo)進(jìn)行統(tǒng)一，無特別用處，也可不這么處理。）總重量c=10。背包的最大容量為10，那么在設(shè)置數(shù)組m大小時(shí)，可以設(shè)行列值為6和11，那么，對(duì)于m(i,j)就表示可選物品為i…n背包容量為j(總重量)時(shí)背包中所放物品的最大價(jià)值。
四、回溯法
回溯法（探索與回溯法）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。
基本思想：
回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含（剪枝過程），則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。
回溯法就是對(duì)隱式圖的深度優(yōu)先搜索算法
回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)( )來處死(剪枝)那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的計(jì)算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。（回溯法 = 窮舉 +剪枝）
一般步驟：
(1)針對(duì)所給問題，定義問題的解空間；
(2)確定易于搜索的解空間結(jié)構(gòu)；
(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。
兩個(gè)常用的剪枝函數(shù)：
(1)約束函數(shù)：在擴(kuò)展結(jié)點(diǎn)處減去不滿足約束的子數(shù)
(2)限界函數(shù)：減去得不到最優(yōu)解的子樹
用回溯法解題的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n)，則回溯法所需的計(jì)算空間通常為O(h(n))。而顯式地存儲(chǔ)整個(gè)解空間則需要O(2^h(n))或O(h(n)!)內(nèi)存空間。
五、分支限界法
基本思想：
分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。
在分支限界法中算法設(shè)計(jì)與分析堆和堆排序ppt，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。
此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。
分支限界法與回溯法的區(qū)別：
（1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。
（2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。
常見的兩種分支限界法：
（1）隊(duì)列式(FIFO)分支限界法
按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。
（2）優(yōu)先隊(duì)列式分支限界法
按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。
例子：?jiǎn)卧醋疃搪窂絾栴}（參考）
1、問題描述
在下圖所給的有向圖G中，每一邊都有一個(gè)非負(fù)邊權(quán)。要求圖G的從源頂點(diǎn)s到目標(biāo)頂點(diǎn)t之間的最短路徑。
下圖是用優(yōu)先隊(duì)列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個(gè)結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。
找到一條路徑：
目前的最短路徑是8，一旦發(fā)現(xiàn)某個(gè)結(jié)點(diǎn)的下界不小于這個(gè)最短路進(jìn)，則剪枝：
同一個(gè)結(jié)點(diǎn)選擇最短的到達(dá)路徑：
2.剪枝策略
在算法擴(kuò)展結(jié)點(diǎn)的過程中，一旦發(fā)現(xiàn)一個(gè)結(jié)點(diǎn)的下界不小于當(dāng)前找到的最短路長(zhǎng)，則算法剪去以該結(jié)點(diǎn)為根的子樹。
在算法中，利用結(jié)點(diǎn)間的控制關(guān)系進(jìn)行剪枝。從源頂點(diǎn)s出發(fā)，2條不同路徑到達(dá)圖G的同一頂點(diǎn)。由于兩條路徑的路長(zhǎng)不同，因此可以將路長(zhǎng)長(zhǎng)的路徑所對(duì)應(yīng)的樹中的結(jié)點(diǎn)為根的子樹剪去。
3.算法思想
解單源最短路徑問題的優(yōu)先隊(duì)列式分支限界法用一極小堆來存儲(chǔ)活結(jié)點(diǎn)表。其優(yōu)先級(jí)是結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。
算法從圖G的源頂點(diǎn)s和空優(yōu)先隊(duì)列開始。結(jié)點(diǎn)s被擴(kuò)展后，它的兒子結(jié)點(diǎn)被依次插入堆中。此后，算法從堆中取出具有最小當(dāng)前路長(zhǎng)的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并依次檢查與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰的所有頂點(diǎn)。如果從當(dāng)前擴(kuò)展結(jié)點(diǎn)i到頂點(diǎn)j有邊可達(dá)，且從源出發(fā)，途經(jīng)頂點(diǎn)i再到頂點(diǎn)j的所相應(yīng)的路徑的長(zhǎng)度小于當(dāng)前最優(yōu)路徑長(zhǎng)度，則將該頂點(diǎn)作為活結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。這個(gè)結(jié)點(diǎn)的擴(kuò)展過程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止。
源碼如下：
[cpp]view
/* 主題：?jiǎn)卧醋疃搪窂絾栴}