演算法分析——動態規劃-有解無憂

一、動態規劃定義

通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法，

二、動態規劃與貪心演算法區別

已知問題規模為n的前提A，求解一個未知解B，（我們用An表示“問題規模為n的已知條件”）此時，如果把問題規模降到0，即已知A0，可以得到A0->B.

如果從A0添加一個元素，得到A1的變化程序，即A0->A1; 進而有A1->A2; A2->A3; …… ; Ai->Ai+1. 這就是嚴格的歸納推理，也就是我們經常使用的數學歸納法；
對于Ai+1，只需要它的上一個狀態Ai即可完成整個推理程序（而不需要更前序的狀態），我們將這一模型稱為馬爾科夫模型，對應的推理程序叫做“貪心法”，

然而，Ai與Ai+1往往不是互為充要條件，隨著i的增加，有價值的前提資訊越來越少，我們無法僅僅通過上一個狀態得到下一個狀態，因此可以采用如下方案：

{A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,...,Ai}->Ai+1. 這種方式就是第二數學歸納法，
對于Ai+1需要前面的所有前序狀態才能完成推理程序，我們將這一模型稱為高階馬爾科夫模型，對應的推理程序叫做“動態規劃法”，

上述兩種狀態轉移圖如下圖所示：

三、動態規劃原理

基本思想：問題的最優解如果可以由子問題的最優解推導得到，則可以先求解子問題的最優解，在構造原問題的最優解；若子問題有較多的重復出現，則可以自底向上從最終子問題向原問題逐步求解，
使用條件：可分為多個相關子問題，子問題的解被重復使用

Optimal substructure（優化子結構）：

一個問題的優化解包含了子問題的優化解
縮小子問題集合，只需那些優化問題中包含的子問題，降低實作復雜性
我們可以自下而上的

Subteties（重疊子問題）：在問題的求解程序中，很多子問題的解將被多次使用，

動態規劃演算法的設計步驟：

分析優化解的結構
遞回地定義最優解的代價
自底向上地計算優化解的代價保存之，并獲取構造最優解的資訊
根據構造最優解的資訊構造優化解

動態規劃特點：

把原始問題劃分成一系列子問題；
求解每個子問題僅一次，并將其結果保存在一個表中，以后用到時直接存取，不重復計算，節省計算時間
自底向上地計算，
整體問題最優解取決于子問題的最優解（狀態轉移方程）（將子問題稱為狀態，最終狀態的求解歸結為其他狀態的求解）

能采用動態規劃求解的問題的一般要具有3個性質： (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、回傳需要的值，一般是陣列的最后一個或者二維陣列的最右下角，代碼基本框架：　　

 1 for(j=1; j<=m; j=j+1) // 第一個階段
 2     xn[j] = 初始值;
 3 
 4   for(i=n-1; i>=1; i=i-1)// 其他n-1個階段
 5     for(j=1; j>=f(i); j=j+1)//f(i)與i有關的運算式
 6       xi[j]=j=max（或min）{g(xi-[j1:j2]), ......, g(xi-1[jk:jk+1])};
 7 
 8 t = g(x1[j1:j2]); // 由子問題的最優解求解整個問題的最優解的方案
 9 
10 print(x1[j1]);
11 
12 for(i=2; i<=n-1; i=i+1）
13 { 
14       t = t-xi-1[ji];
15 
16       for(j=1; j>=f(i); j=j+1)
17          if(t=xi[ji])
18               break;
19 }

View Code

參考鏈接：

　[1]https://blog.csdn.net/zw6161080123/article/details/80639932

　[2]https://www.cnblogs.com/hithongming/p/9229871.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/252926.html

標籤：其他

上一篇：執行緒之間如何通信

下一篇：GO 語言入門（一）