分治算法

一、基本概念

在計算機科學中，分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問題，當n=1時，不需任何計算。n=2時，只要作一次比較即可排好序。n=3時只要作3次比較即可，…。而當n較大時，問題就不那么容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。

二、基本策略

對于一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題。這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解，這種算法設計策略叫做分治法。

如果原問題可分割成k個子問題，1

動態規劃

一、基本概念

每次決策依賴于當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，所以，這種多階段最優化決策解決問題的過程就稱為動態規劃。

二、基本思想

基本思想：與分治法類似，也是將待求解的問題分解為若干個子問題，按順序求解子問題，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部 解，依次解決各子問題，最后一個子問題就是初始問題的解。

與分治法最大的差別：適合于用動態規劃法求解的問題，經分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）。

三、適用的情況

（1）最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。

（2）無后效性：即某階段狀態一旦確定，就不受這個狀態以后決策的影響，也就是說，某狀態以后的過程不會影響以前的狀態，只與當前狀態有關。

（3）有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質并不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃算法同其他算法相比就不具備優勢）

四、解題步驟

動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟：

初始狀態→│決策１│→│決策２│→…→│決策ｎ│→結束狀態

(1)劃分階段：按照問題的時間特征，把問題分為若干個階段，在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。

(2)確定狀態和狀態變量：將問題發展到各個階段時所處于的各種客觀情況用不同的狀態表示出來，當然，狀態的選擇要滿足無后效性。

(3)確定決策并寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩個階段的狀態之間的關系來確定決策方法和狀態轉移方程。

(4)尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

一般，只要解決問題的階段、狀態和狀態轉移決策確定了，就可以寫出狀態轉移方程。實際應用中可以按以下幾個簡化的步驟進行設計：

（1）分析最優解的性質，并刻畫其結構特征。

（2）遞歸的定義最優解。

（3）以自底向上或自頂向下的記憶化方式（備忘錄法）計算出最優值。

（4）根據計算最優值時得到的信息，構造問題的最優解。

五、算法實現的說明

動態規劃的主要難點在于上面4個步驟的確定，一旦設計完成，實現部分就會非常簡單。使用動態規劃求解問題，最重要的就是確定動態規劃三要素：

（1）問題的階段

（2）每個階段的狀態

（3）從前一個階段轉化到后一個階段之間的遞推關系。

遞推關系必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前面保存的子問題的解來減少重復計算，所以對于大規模問題來說，有遞歸不可比擬的優勢，這也是動態規劃算法的核心之處。

確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格，最后根據整個表格的數據通過簡單的取舍或者運算求得問題的最優解。

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

貪心算法

一、基本概念

在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。

貪心算法沒有固定的算法框架，算法設計的關鍵是貪心策略的選擇。必須注意的是，貪心算法不是對所有問題都能得到整體最優解，選擇的貪心策略必須具備無后效性，即某個狀態以后的過程不會影響以前的狀態，只與當前狀態有關。所以，對所采用的貪心策略一定要仔細分析其是否滿足無后效性。

二、基本思路

1.建立數學模型來描述問題。

2.把求解的問題分成若干個子問題。

3.對每一子問題求解，得到子問題的局部最優解。

4.把子問題的解局部最優解合成原來解問題的一個解。

三、貪心算法適用的問題

貪心策略適用的前提是：局部最優策略能導致產生全局最優解。實際上，貪心算法適用的情況很少。一般，對一個問題分析是否適用于貪心算法，可以先選擇該問題下的幾個實際數據進行分析，就可做出判斷。

四、貪心算法的實現框架

從問題的某一初始解出發；

while（能朝給定總目標前進一步）

{

利用可行的決策，求出可行解的一個解元素；

}

由所有解元素組合成問題的一個可行解；

五、貪心策略的選擇

因為用貪心算法只能通過解局部最優解的策略來達到全局最優解，因此，一定要注意判斷問題是否適合采用貪心算法策略，找到的解是否一定是問題的最優解。

六、例題分析——[背包問題]

有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。

物品 A B C D E F G

重量 35 30 60 50 40 10 25

價值 10 40 30 50 35 40 30

分析：

目標函數： ∑pi最大 約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)

（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？

（2）每次挑選所占重量最小的物品裝入是否能得到最優解？

（3）每次選取單位重量價值最大的物品，成為解本題的策略。

值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經過證明成立后，它就是一種高效的算法。貪心算法還是很常見的算法之一，這是由于它簡單易行，構造貪心策略不是很困難。

可惜的是，它需要證明后才能真正運用到題目的算法中。一般來說，貪心算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。對于例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：

（1）貪心策略：選取價值最大者。反例：

W=30 物品：A B C 重量：28 12 12 價值：30 20 20

根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。

（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。

（3）貪心策略：選取單位重量價值最大的物品。反例：

W=30 物品：A B C 重量：28 20 10 價值：28 20 10

根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。

回溯法（DFS）

一、基本概念

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

回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點”。許多復雜的，規模較大的問題都可以使用回溯法，有“通用解題方法”的美稱。

二、基本思想

在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。

若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。

三、解題步驟

（1）針對所給問題，確定問題的解空間：首先應明確定義問題的解空間，問題的解空間應至少包含問題的一個（最優）解；

（2）確定結點的擴展搜索規則；

（3）以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。

四、算法框架

（1）問題框架

設問題的解是一個n維向量(a1,a2,………,an),約束條件是ai(i=1,2,3,……,n)之間滿足某種條件，記為f(ai)。

（2）非遞歸回溯框架

1.int a[n],i;2.初始化數組a[];3.i = 1;4: while(i>0(有路可走) and (未達到目標)) //還未回溯到頭5: {6: if(i > n) //搜索到葉結點7: {8: 搜索到一個解，輸出；9: }10: else //處理第i個元素11: {12:a[i]第一個可能的值；13: while(a[i]在不滿足約束條件且在搜索空間內)14: {15:a[i]下一個可能的值；16: }17: if(a[i]在搜索空間內)18: {19: 標識占用的資源；20: i = i+1; //擴展下一個結點21: }22: else23: {24: 清理所占的狀態空間； //回溯25:i = i–1;26: }27: }

（3）遞歸的算法框架

回溯法是對解空間的深度優先搜索，在一般情況下使用遞歸函數來實現回溯法比較簡單，其中i為搜索的深度，框架如下：

1: int a[n];2: try(int i)3: {4: if(i>n)5:輸出結果;6: else7: {8: for(j =下界; j <= 上界; j=j+1) //枚舉i所有可能的路徑9: {10: if(fun(j)) //滿足限界函數和約束條件11: {12: a[i] = j;13: … //其他操作14: try(i+1);15:回溯前的清理工作（如a[i]置空值等）;16: }17: }18: }19: }

分支限界法（BFS）

一、基本概念

類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的算法，但在一般情況下，分支限界法與回溯法的求解目標不同。回溯法的求解目標是找出T中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標函數值達到極大或極小的解，即在某種意義下的最優解。

二、一般過程

由于求解目標不同，導致分支限界法與回溯法在解空間樹T上的搜索方式也不相同。回溯法以深度優先的方式搜索解空間樹T，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹T。

分支限界法的搜索策略：在擴展結點處，先生成其所有的兒子結點（分支），然后再從當前的活結點表中選擇下一個擴展對點。為了有效地選擇下一擴展結點，以加速搜索的進程，在每一活結點處，計算一個函數值（限界），并根據這些已計算出的函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間樹上有最優解的分支推進，以便盡快地找出一個最優解。

分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。問題的解空間樹是表示問題解空間的一棵有序樹，常見的有子集樹和排列樹。在搜索問題的解空間樹時，分支限界法與回溯法對當前擴展結點所使用的擴展方式不同。在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，那些導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被子加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所求的解或活結點表為空時為止。

三、回溯法和分支限界法的區別

回溯法深度優先搜索堆棧活結點的所有可行子結點被遍歷后才被從棧中彈出找出滿足約束條件的所有解。

分支限界法廣度優先或最小消耗優先搜索隊列、優先隊列每個結點只有一次成為活結點的機會找出滿足約束條件的一個解或特定意義下的最優解。

總結

以上是生活随笔為你收集整理的史上最全的五大算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。

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