原理入門理論最優(yōu)化原理問題求解模式實現(xiàn)思路狀態(tài)實現(xiàn)最長公共子序列湊硬幣

原理

入門理論

最優(yōu)化原理

1951年美國數(shù)學家R．Bellman等人，根據(jù)一類多階段問題的特點，把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然后逐個加以解決。一些靜態(tài)模型，只要人為地引進“時間”因素，分成時段，就可以轉(zhuǎn)化成多階段的動態(tài)模型，用動態(tài)規(guī)劃方法去處理。與此同時，他提出了解決這類問題的“最優(yōu)化原理”(PRinciple of optimality)：

“一個過程的最優(yōu)決策具有這樣的性質(zhì)：即無論其初始狀態(tài)和初始決策如何，其今后諸策略對以第一個決策所形成的狀態(tài)作為初始狀態(tài)的過程而言，必須構(gòu)成最優(yōu)策略”。簡言之，一個最優(yōu)策略的子策略，對于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。

這個“最優(yōu)化原理”如果用數(shù)學化一點的語言來描述的話，就是：假設為了解決某一優(yōu)化問題，需要依次作出n個決策D1，D2，…，Dn，如若這個決策序列是最優(yōu)的，對于任何一個整數(shù)k，1 < k < n，不論前面k個決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當前狀態(tài)，即以后的決策Dk+1，Dk+2，…，Dn也是最優(yōu)的。

最優(yōu)化原理是動態(tài)規(guī)劃的基礎。任何一個問題，如果失去了這個最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。能采用動態(tài)規(guī)劃求解的問題都需要滿足一定的條件： (1) 問題中的狀態(tài)必須滿足最優(yōu)化原理； (2) 問題中的狀態(tài)必須滿足無后效性。 所謂的無后效性是指：“下一時刻的狀態(tài)只與當前狀態(tài)有關，而和當前狀態(tài)之前的狀態(tài)無關，當前的狀態(tài)是對以往決策的總結(jié)”。（這個感覺和馬爾科夫模型很像） (3) 子問題的重疊性 動態(tài)規(guī)劃將原來具有指數(shù)級時間復雜度的搜索算法改進成了具有多項式時間復雜度的算法。其中的關鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。動態(tài)規(guī)劃實質(zhì)上是一種以空間換時間的技術(shù)，它在實現(xiàn)的過程中，不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以它的空間復雜度要大于其它的算法。

問題求解模式

　　　　　 初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài) 　　　　　 動態(tài)規(guī)劃決策過程示意圖 　　　　　

實現(xiàn)思路

動態(tài)規(guī)劃算法通常基于一個遞推公式及一個或多個初始狀態(tài)。 當前子問題的解將由上一次子問題的解推出。使用動態(tài)規(guī)劃來解題只需要多項式時間復雜度， 因此它比回溯法、暴力法等要快許多。現(xiàn)在讓我們通過一個例子來了解一下DP的基本原理。首先，我們要找到某個狀態(tài)的最優(yōu)解，然后在它的幫助下，找到下一個狀態(tài)的最優(yōu)解。

最重要的就是確定動態(tài)規(guī)劃三要素： （1）問題的階段 （2）每個階段的狀態(tài) （3）從前一個階段轉(zhuǎn)化到后一個階段之間的遞推關系。

確定了動態(tài)規(guī)劃的這三要素，整個求解過程就可以用一個最優(yōu)決策表來描述，最優(yōu)決策表是一個二維表，其中行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對應此問題的在某個階段某個狀態(tài)下的最優(yōu)值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據(jù)遞推關系，從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個表格的數(shù)據(jù)通過簡單的取舍或者運算求得問題的最優(yōu)解。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

舉個例子：

http://www.companysz.com/steven_oyj/archive/2010/05/22/1741374.html

實現(xiàn)思路有： 1.自頂向下(又稱記憶化搜索、備忘錄)：基本上對應著遞歸函數(shù)實現(xiàn)，從大范圍開始計算，要注意不斷保存中間結(jié)果，避免重復計算； 2.自底向上(遞推)：從小范圍遞推計算到大范圍； 動態(tài)規(guī)劃的重點：遞歸方程+邊界條件

動態(tài)規(guī)劃算法可以求解很多問題，比如矩陣乘法、最長公共子序列、構(gòu)造最優(yōu)二叉查找樹等，現(xiàn)就著名的最長公共子序列問題，采用動態(tài)規(guī)劃法分析之。

狀態(tài)

“狀態(tài)”用來描述該問題的子問題的解。

實現(xiàn)

最長公共子序列

子序列:若給定序列X={x1,x2,…,xm},則另一序列Z={z1,z2,…,zk},是X的子序列是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有:zj=xij.

公共子序列:給定2個序列X和Y,當另一序列Z既是X的子序列又是Y的子序列時,稱Z是序列X和Y的公共子序列.

最長公共子序列:給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最長公共子序列.

如：序列ABCDEF和ADFGH的最長公共子序列為ADF

注意:最長公共子串(Longest Common Substirng)和最長公共子序列(Longest Common Subsequence,簡稱LCS)的區(qū)別為是最長公共子串的串是一個連續(xù)的部分,而最長公共子序列則是從不改變序列的順序,而從序列中去掉任意的元素而獲得新的序列;通俗的說就是子串中字符的位置必須是連續(xù)的而子序列則可以不必連續(xù)。

問題描述：給定2個序列X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A},找出X和Y的最長公共子序列

1.分析最優(yōu)子結(jié)構(gòu)性質(zhì)：

設序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk} ,則

(1)若xm=yn,則zk=xm=yn,且z1,z2,…, zk-1是否為x1,x2,…,xm-1和y1,y2,…,yn-1的最長公共子序列.

(2)若xm≠yn且zk≠xm,則Z是x1,x2,…,xm-1和Y的最長公共子序列.

(3)若xm≠yn且zk≠yn,則Z是X和y1,y2,…,yn-1的最長公共子序列.

由此可見,2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列.因此,最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì).當問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)時就可以用動態(tài)規(guī)劃算法解決該問題.

2.由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關系.用c[i][j]記錄序列和的最長公共子序列的長度.其中,Xi={x1,x2,…,xi},Yj={y1,y2,…,yj}.當i=0或j=0時,空序列是Xi和Yj的最長公共子序列.故此時C[i][j]=0.其它情況下,由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關系如下: c[i][j]=?????0,c[i?1][j?1]+1,maxc[i?1][j],c[i][j?1],if i=0,j=0if x>0,y>0, xi>yjif i>0,j>0,xi≠yj  $$c[i][j] = /begin{cases}0, & /text{if $i = 0, j =0$} //c[i - 1][j - 1] + 1, & /text{if $x > 0, y >0$, $x_i > y_j$} //max{c[i-1][j], c[i][j-1]}, & /text{if $i > 0, j > 0, x_i /neq y_j$ }/end{cases}$$

http://www.2cto.com/kf/201611/565606.html http://m.codes51.com/article/detail_556679.html

湊硬幣

如果我們有面值為1元、3元和5元的硬幣若干枚，如何用最少的硬幣湊夠11元？ (表面上這道題可以用貪心算法，但貪心算法無法保證可以求出解，比如1元換成2元的時候)

首先我們思考一個問題，如何用最少的硬幣湊夠i元(i<11)？為什么要這么問呢？ 兩個原因：1.當我們遇到一個大問題時，總是習慣把問題的規(guī)模變小，這樣便于分析討論。 2.這個規(guī)模變小后的問題和原來的問題是同質(zhì)的，除了規(guī)模變小，其它的都是一樣的， 本質(zhì)上它還是同一個問題(規(guī)模變小后的問題其實是原問題的子問題)。

好了，讓我們從最小的i開始吧。當i=0，即我們需要多少個硬幣來湊夠0元。 由于1，3，5都大于0，即沒有比0小的幣值，因此湊夠0元我們最少需要0個硬幣。 (這個分析很傻是不是？別著急，這個思路有利于我們理清動態(tài)規(guī)劃究竟在做些什么。) 這時候我們發(fā)現(xiàn)用一個標記來表示這句“湊夠0元我們最少需要0個硬幣。”會比較方便， 如果一直用純文字來表述，不出一會兒你就會覺得很繞了。那么， 我們用d(i)=j來表示湊夠i元最少需要j個硬幣。于是我們已經(jīng)得到了d(0)=0， 表示湊夠0元最小需要0個硬幣。當i=1時，只有面值為1元的硬幣可用， 因此我們拿起一個面值為1的硬幣，接下來只需要湊夠0元即可，而這個是已經(jīng)知道答案的， 即d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。當i=2時， 仍然只有面值為1的硬幣可用，于是我拿起一個面值為1的硬幣， 接下來我只需要再湊夠2-1=1元即可(記得要用最小的硬幣數(shù)量)，而這個答案也已經(jīng)知道了。 所以d(2)=d(2-1)+1=d(1)+1=1+1=2。一直到這里，你都可能會覺得，好無聊， 感覺像做小學生的題目似的。因為我們一直都只能操作面值為1的硬幣！ 讓我們看看i=3時的情況。當i=3時，我們能用的硬幣就有兩種了：1元的和3元的( 5元的仍然沒用，因為你需要湊的數(shù)目是3元！5元太多了親)。 既然能用的硬幣有兩種，我就有兩種方案。如果我拿了一個1元的硬幣，我的目標就變?yōu)榱耍?湊夠3-1=2元需要的最少硬幣數(shù)量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。 這個方案說的是，我拿3個1元的硬幣；第二種方案是我拿起一個3元的硬幣， 我的目標就變成：湊夠3-3=0元需要的最少硬幣數(shù)量。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 這個方案說的是，我拿1個3元的硬幣。好了，這兩種方案哪種更優(yōu)呢？ 記得我們可是要用最少的硬幣數(shù)量來湊夠3元的。所以， 選擇d(3)=1，怎么來的呢？具體是這樣得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。 我們要抽出動態(tài)規(guī)劃里非常重要的兩個概念：狀態(tài)和狀態(tài)轉(zhuǎn)移方程。

上文中d(i)表示湊夠i元需要的最少硬幣數(shù)量，我們將它定義為該問題的”狀態(tài)”， 這個狀態(tài)是怎么找出來的呢？我在另一篇文章 動態(tài)規(guī)劃之背包問題(一)中寫過： 根據(jù)子問題定義狀態(tài)。你找到子問題，狀態(tài)也就浮出水面了。 最終我們要求解的問題，可以用這個狀態(tài)來表示：d(11)，即湊夠11元最少需要多少個硬幣。 那狀態(tài)轉(zhuǎn)移方程是什么呢？既然我們用d(i)表示狀態(tài)，那么狀態(tài)轉(zhuǎn)移方程自然包含d(i)， 上文中包含狀態(tài)d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。沒錯， 它就是狀態(tài)轉(zhuǎn)移方程，描述狀態(tài)之間是如何轉(zhuǎn)移的。當然，我們要對它抽象一下，

d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j個硬幣的面值。

偽代碼為：

參考鏈接：

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg http://www.hawstein.com/posts/dp-novice-to-advanced.html http://dev.21tx.com/2007/01/17/11010.html

動態(tài)規(guī)劃與貪婪算法的區(qū)別：

http://www.programgo.com/article/67512173783/ http://amp.itgo.me/a/3219840973004004279

動態(tài)規(guī)劃的教程算法以及源碼：

http://www.xuebuyuan.com/zt/4352330.html https://www.codechef.com/wiki/tutorial-dynamic-programming