几个经典算法的概念
http://eriol.iteye.com/blog/1076296
動態(tài)規(guī)劃(Dynamic Programming)
?
一、動態(tài)規(guī)劃的基本思想：
? ? ? 動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計算，節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的基本思路。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。
?
二、設(shè)計動態(tài)規(guī)劃法的步驟：
1. 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；
2. 遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；
3. 以自底向上的方式計算出最優(yōu)值；
4. 根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。
?
? ? ? 步驟1-3是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略，步驟3中記錄的信息也較少；若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。
?
三、動態(tài)規(guī)劃問題的特征：
? ? ?動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。
1. 最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
2. 重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。
?
?
回溯法(Backtracking)
?
一、算法思想
? ? ? 回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。
?
二、算法框架：
1. 問題的解空間：應(yīng)用回溯法解問題時，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)到少包含問題的一個（最優(yōu)）解。
2. 回溯法的基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結(jié)點就成為一個活結(jié)點，同時也成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的活結(jié)點，并成為當(dāng)前擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱深方向移動，則當(dāng)前擴展結(jié)點就成為死結(jié)點。換句話說，這個結(jié)點不再是一個活結(jié)點。此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴展結(jié)點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點時為止。
? ? ?運用回溯法解題通常包含以下三個步驟：
(1) 針對所給問題，定義問題的解空間；
(2) 確定易于搜索的解空間結(jié)構(gòu)；
(3) 以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索；
3. 遞歸回溯：由于回溯法是對解空間的深度優(yōu)先搜索，因此在一般情況下可用遞歸函數(shù)來實現(xiàn)回溯法。
?
?
分治策略(Divide and Conquer)
?
一、算法思想
任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關(guān)。問題規(guī)模越小，解題所需的計算時間往往也越少，從而也越容易計算。想解決一個較大的問題，有時是相當(dāng)困難的。分治法的思想就是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。
分治的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。找出各部分的解，然后把各部分的解組合成整個問題的解。?
?
?
分支限界
?
一、分支限界法：
? ? ? 分支限界法類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的算法。但在一般情況下，分支限界法與回溯法的求解目標(biāo)不同。回溯法的求解目標(biāo)是找出T中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使用某一目標(biāo)函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。
? ? ? 由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法在解空間樹T上的搜索方式也不相同。回溯法以深度優(yōu)先的方式搜索解空間樹T，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹T。分支限界法的搜索策略是：在擴展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當(dāng)前的活結(jié)點表中選擇下一個擴展對點。為了有效地選擇下一擴展結(jié)點，以加速搜索的進程，在每一活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)這些已計算出的函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。
?
二、分支限界法的基本思想：
? ? ? 分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。問題的解空間樹是表示問題解空間的一棵有序樹，常見的有 子集樹和 排列樹。在搜索問題的解空間樹時，分支限界法與回溯法對當(dāng)前擴展結(jié)點所使用的擴展方式不同。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點。活結(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被子加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所求的解或活結(jié)點表為空時為止。
?
三、選擇下一擴展結(jié)點的不同方式：
? ? 從活結(jié)點表中選擇下一擴展結(jié)點的不同方式導(dǎo)致不同的分支限界法。最常見的有以下兩種方式：
1. 隊列式(FIFO)分支限界法：隊列式分支限界法將活結(jié)點表組織成一個隊列，并按隊列的先進先出原則選取下一個結(jié)點為當(dāng)前擴展結(jié)點。
2. 優(yōu)先隊列式分支限界法：優(yōu)先隊列式分支限界法將活結(jié)點表組織成一個優(yōu)先隊列，交按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當(dāng)前擴展結(jié)點。?
?
總結(jié)
