C語言動態(tài)規(guī)劃課件

1、C語言動態(tài)規(guī)劃,1,第十章 動態(tài)規(guī)劃,用遞推代替遞歸 用空間換時間,C語言動態(tài)規(guī)劃,2,10.1 什么是動態(tài)規(guī)劃,1、最短路徑問題 2、數(shù)塔問題,C語言動態(tài)規(guī)劃,3,下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費用，單向通行由A-E。試用動態(tài)規(guī)劃的最優(yōu)化原理求出A-E的最省費用。,1 最短距離問題,C語言動態(tài)規(guī)劃,4,如圖從A到E共分為4個階段，即第一階段從A到B，第二階段從B到C，第三階段從C到D，第四階段從D到E。 除起點A和終點E外，其它各點既是上一階段的終點又是下一階段的起點。,例如從A到B的第一階段中，A為起點，終點有B1，B2兩個，因而這時走的路線有兩個選擇，一是走到B1，一是走到

2、B2。,若選擇B2的決策，B2就是第一階段在我們決策之下的結(jié)果，它既是第一階段路線的終點，又是第二階段路線的始點。,在第二階段，再從B2點出發(fā)，對于B2點就有一個可供選擇的終點集合(C1，C2，C3)；若選擇由B2走至C2為第二階段的決策，則C2就是第二階段的終點，同時又是第三階段的始點。,同理遞推下去，可看到各個階段的決策不同，線路就不同。,C語言動態(tài)規(guī)劃,5,很明顯，當某階段的起點給定時，它直接影響著后面各階段的行進路線和整個路線的長短。 故此問題的要求是：在各個階段選取一個恰當?shù)臎Q策，使由這些決策組成的一個決策序列所決定的一條路線，其總路程最短。如何解決這個問題呢？,要求在各階段選取一個

3、恰當?shù)臎Q策,C語言動態(tài)規(guī)劃,6,決策過程： （1）由目標狀態(tài)E向前推，可以分成四個階段，即四個子問題。 DE CE BE AE （2）策略：每個階段到E的最省費用為本階段的決策路徑。,用動態(tài)規(guī)劃法求解,C語言動態(tài)規(guī)劃,7,（3）D1，D2是第一次輸入的結(jié)點。他們到E都只有一種費用： f(D1)=5 f(D2)=2,目前無法定下，哪一個點將在全程最優(yōu)策略的路徑上。第二階段計算中，5，2都應(yīng)分別參加計算,C語言動態(tài)規(guī)劃,8,（4）C1，C2，C3是第二次輸入結(jié)點，他們到D1，D2各有兩種費用。此時應(yīng)計算C1，C2，C3分別到E的最少費用。 f(C1) =minC1D1+ f(D1) ，C1D2+

4、f(D2)。 計算結(jié)果是f(C1)= C1D1+ f(D1)=8 （D1) 同理C2的決策路徑計算結(jié)果是C2+D2+ E , f(C2)=7 。同理C3的決策路徑計算結(jié)果是C3+D2+E，f(C3)=10。,C語言動態(tài)規(guī)劃,9,（5）第三次輸入結(jié)點為B1，B2，而決策輸出結(jié)點可能為C1，C2，C3。仿前計算可得Bl，B2的決策路徑為如下情況。Bl: B1C1 費用 f(B1)=5+8=13， B2:B2C1 費用 f(B2)= 6+8=14，,C語言動態(tài)規(guī)劃,10,（6）第四次輸入結(jié)點為A，決策輸出結(jié)點可能為B1，B2。 同理可得決策路徑為A：AB2，費用5+14=19 此時才正式確定每個子問

5、題的結(jié)點中，那一個結(jié)點將在最優(yōu)費用的路徑上。 子問題的決策中，只對同一城市（結(jié)點）比較優(yōu)劣。而同一階段的城市（結(jié)點）的優(yōu)劣要由下一個階段去決定。,C語言動態(tài)規(guī)劃,11,2、數(shù)塔問題,有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。,C語言動態(tài)規(guī)劃,12,用暴力的方法，可以嗎？,C語言動態(tài)規(guī)劃,13,這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如31），則需要列舉出的路徑條數(shù)將是一個非常龐大的數(shù)目（230= 10243 109=10億）。,試想一下：,C語言動態(tài)規(guī)劃,14,拒絕暴力，倡導(dǎo)和諧,C語言動態(tài)規(guī)劃,15

6、,從頂點出發(fā)時到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。 可見，由下層的子問題可以得到上層的子問題，所以，可從底層開始，層層遞進，最后得到最大值。 結(jié)論：自頂向下的分析，自底向上的計算。,考慮一下：,C語言動態(tài)規(guī)劃,16,如果各個子問題不是獨立的，不同的子問題的個數(shù)只是多項式量級，如果我們能夠保存已經(jīng)解決的子問題的答案，而在需要的時候再找出已求得的答案，這樣就可以避免大量的重復(fù)計算。由此而來的基本思路是，用一個表記錄所有已解決的子問題的答案，不管該問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。,10.2 動

7、態(tài)規(guī)劃的基本思想,C語言動態(tài)規(guī)劃,17,動態(tài)規(guī)劃的基本步驟,動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值（最大值或最小值）的那個解。設(shè)計一個動態(tài)規(guī)劃算法，通?？梢园匆韵聨讉€步驟進行：,C語言動態(tài)規(guī)劃,18,（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。 （2）遞歸地定義最優(yōu)值。 （3）以自底向上的方式計算出最優(yōu)值。 （4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。 其中（1）（3）步是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省去。若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟（4）。此時，在步

8、驟（3）中計算最優(yōu)值時，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速構(gòu)造出一個最優(yōu)解。,基本步驟,C語言動態(tài)規(guī)劃,19,動態(tài)規(guī)劃問題的特征,動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要性質(zhì)： 1、最優(yōu)子結(jié)構(gòu)：當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 2、重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。,C語言動態(tài)規(guī)劃,20,10.3 最長有序子序列,C語言動態(tài)

9、規(guī)劃,21,子問題的構(gòu)造,子問題“求以ak（k=1, 2, 3N）為終點的最長上升子序列的長度” 雖然這個子問題和原問題形式上并不完全一樣，但是只要這N 個子問題都解決了，那么這N 個子問題的解中，最大的那個就是整個問題的解。 該子問題可以遞推求解,C語言動態(tài)規(guī)劃,22,假定MaxLen (k)表示以ak 做為“終點”的最長上升子序列的長度，那么： MaxLen (1) = 1 MaxLen (k) = Max MaxLen (i)：1i k 且 ai ak 且 k1 + 1,C語言動態(tài)規(guī)劃,23,實例：,所求最大值是Fn嗎？,2,C語言動態(tài)規(guī)劃,24,10.4 最長公共子序列,一個給定序列的

10、子序列是在該序列中刪去若干元素后得到的序列。 給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。,C語言動態(tài)規(guī)劃,25,例如，若X=A，B，C，B，D，B，A，Y=B，D，C，A，B，A，則 序列B，C，A是X和Y的一個公共子序列，但它不是X和Y的一個最長公共子序列。 序列B，C，B，A也是X和Y的一個公共子序列，它的長度為4，而且它是X和Y的一個最長公共子序列，因為X和Y沒有長度大于4的公共子序列。,C語言動態(tài)規(guī)劃,26,給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。 問題：給定2個序列X=x1,x2

11、,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。,最長公共子序列,C語言動態(tài)規(guī)劃,27,典型應(yīng)用,計算兩個文本的相似程度 生物學(xué)上的基因比較,C語言動態(tài)規(guī)劃,28,人類基因組計劃的研究成果,一個細胞核內(nèi)的23個染色體含31億個核苷酸（只有A、G、T、C四種）； 基因數(shù)在3萬-3.5萬，每個基因有幾千個核苷酸； 人與人之間有99.99%的基因序列是相同的。,C語言動態(tài)規(guī)劃,29,生物學(xué)家對鑒別人類基因和確定他們的功能很感興趣。因為這對診斷人類疾病和開發(fā)新藥很有用。 一旦一段基因被確定后，接下來的工作便是確定它的功能，這個工作一般是通過搜索基因數(shù)據(jù)庫來進行的。數(shù)據(jù)庫中存儲了很多基因序列及

12、其相應(yīng)的功能，將返回與新基因序列功能相似的已知序列。 生物學(xué)家們假設(shè)類似的基因表示類似的功能。確定與待研究基因最相近的一個已知基因?qū)ι镌囼灧浅１匾?C語言動態(tài)規(guī)劃,30,那么如何確定兩個基因序列的相似性呢，這主要是通過相似性函數(shù)來判斷的。 比如已知兩個序列AGTGATG和GTTAG，他們有多相似？一個判斷的方法是在兩個序列中分別插入若干空格使得兩序列的長度相等， AGTGAT- G - GT - -TAG 這種匹配的函數(shù)值是(-3)+5+5+(-3)+(-3)+5 +(-3)+5=8,C語言動態(tài)規(guī)劃,31,窮舉法,對X的所有子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序

13、列。 X的所有子序列都檢查過后即可求出X和Y的最長公共子序列。X的每個子序列相應(yīng)于下標集1,2,.,m的一個子集。因此，共有2m個不同子序列，故窮舉搜索法需要指數(shù)時間 。 而事實上，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì),C語言動態(tài)規(guī)劃,32,最長公共子序列的結(jié)構(gòu),首先引入前綴的概念： 給定一個序列X=x1,x2,xm，對i=1,m定義X的第i個前綴為Xi=x1,x2,xi 例如：X=A ,B, C, B,D,A,B 則X4=A ,B, C, B，X0為空序列,C語言動態(tài)規(guī)劃,33,最長公共子序列的結(jié)構(gòu),設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，則

14、 (1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序列。 (2)若xmyn，則zkxm蘊涵Z是xm-1和Y的最長公共子序列。 (3)若xmyn，則zkyn蘊涵Z是X和yn-1的最長公共子序列。,由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。,如 X=A B C B Y=B D C A B Z=B C B,如 X=A B C B D Y=B D C A B Z=B C B,如 X=A B C B Y=B D C B A Z=B C B,C語言動態(tài)規(guī)劃,34,子問題的遞歸結(jié)構(gòu),由以上三個性質(zhì)可

15、知，要X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列，可能要檢查如下子問題： 若xm=yn時，我們就要找出Xm-1和Yn-1的LCS,將xm=yn拼接到這個LCS后，就得到 Xm和Yn的 LCS 若xmyn時，我們需要解決兩個子問題： 找出 Xm-1和Yn的 LCS，和 Xm和Yn-1 的LCS，取兩者中較長的作為Xm和Yn的 LCS,C語言動態(tài)規(guī)劃,35,子問題的遞歸結(jié)構(gòu),由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出X和Y的最長公共子序列，可按如下方式遞歸的進行： 若xm=yn時， LCS(Xm,Yn)= LCS(Xm-1,Yn-1)+xm 若xmyn時， LCS(Xm,Yn

16、)= maxLCS(Xm-1,Yn), LCS(Xm,Yn-1),max LCS(Xm-1,Yn-1), LCS(Xm-2,Yn),maxLCS(Xm-1,Yn-1), LCS(Xm,Yn-2),C語言動態(tài)規(guī)劃,36,子問題的遞歸結(jié)構(gòu),由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列Xi=x1,x2,xi 和Yj=y1,y2,yj的最長公共子序列的長度。由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：,C語言動態(tài)規(guī)劃,37,計算最優(yōu)值,由于在所考慮的子問題空間中，總共有(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。 輸入： X=x1,x2

17、,xm和Y=y1,y2,yn 輸出： 數(shù)組c：cij存儲Xi=x1,x2,xi和Yj=y1,y2,yj的最長公共子序列的長度,C語言動態(tài)規(guī)劃,38,算法： 對i=1到m做 對j=1到n做 若（xi=yj) cij=ci-1j-1+1; 否則若ci-1j=cij-1 cij=ci-1j; 否則 cij=cij-1;,LCS(Xm,Yn)= LCS(Xm,Yn)+xm,C語言動態(tài)規(guī)劃,39,例：X=A B C B D A B Y=B D C A B A,0 B D C A B A,0 A B C B D A B, A AB ABC ABCB ABCBD ABCBDA ABCBDAB, B BD B

18、DC ,C語言動態(tài)規(guī)劃,40,例：X=A B C B D A B Y=B D C A B A,0 B D C A B A,0 A B C B D A B,C語言動態(tài)規(guī)劃,41,void LCS(int m，int n，char *x， char *y, char *z ,int *c) /不用數(shù)組b，構(gòu)造最優(yōu)解的非遞歸算法 int i=m,j=n; int k=cmn; /最長公共子序列的長度 while(i0 ,構(gòu)造最長公共子序列,C語言動態(tài)規(guī)劃,42,10.5 0-1背包問題,給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中

19、物品的總價值最大? 目標：使裝入背包中物品的總價值最大 約束條件：裝入的物品總重不得超過C,C語言動態(tài)規(guī)劃,43,海盜盜寶問題,海盜有一背包，最大容積為9，現(xiàn)有5件寶物： 體積si分別是2、3、4、5和4公斤 價值vi分別是3、7、5、9和 8 請給出裝載方案，使背包價值達到最大。,C=9,C語言動態(tài)規(guī)劃,44,一開始，見物品就裝，物品1、2、3全裝入，背包裝滿了，得到背包總價值為15，這是不是最大價值呢？,考慮只有前三個物品的情況,C語言動態(tài)規(guī)劃,45,物品4該不該裝？有兩個選擇： （1）不裝，背包價值不變，為15,（2）裝入，它占去的體積為5，得到價值為9，剩下容積4最多可以裝下多大價值？

20、,考慮只有前4個物品的情況,C語言動態(tài)規(guī)劃,46,這是一個n=3(從前三個物品中選擇），容量c=4的子問題。,目前最優(yōu)：裝入物品2和物品4，總價值為16,若已知這個子問題的解是：裝物品2，得價值為7。,（2）裝入物品4，它占去的體積為5，得到價值為9，剩下容積4最多可以裝下多大價值？,C語言動態(tài)規(guī)劃,47,考慮5個物品的情況,物品5該不該裝？ (1)不裝，得到背包價值仍為16,C語言動態(tài)規(guī)劃,48,（2）若裝入物品5，占用體積為4，得價值為8，背包剩余容積為5。 如何在前4個物品中選擇裝入，使背包價值最大化？這是n=4,c=5的一個子問題。 若得到該子問題的解為：裝入物品1、2，得價值為10,

21、考慮5個物品的情況,目前最優(yōu)：裝入物品5和1、2，總價值為1816,C語言動態(tài)規(guī)劃,49,子問題的構(gòu)造,當n=1時:只有一個物品， s1=2,v1=3 若背包容量c=0、1，則無法裝入物品1，得到背包價值為0 若背包容量c=2、3、4、5、6，7，8，9則可裝入物品1，得到背包價值為3。,C10=0 C11=0 C12=3 C13=3 C14=3 C15=3 C16=3 C17=3 C18=3 C19=3,C語言動態(tài)規(guī)劃,50,考慮兩個物品的情況,當n=2時，有兩個物品， s1=2,v1=3，s2=3,v2=7 若背包容量c=0、1，得到背包價值為0 若背包容量c=2，可裝入物品1，得總價值m

22、22=3 若背包容量c=3，m23=7,若背包容量c=4, m24=7 若背包容量c=5, m25=10,若不裝物品2，m23=m13=3 若裝入物品2，m23=v2+m13-3=7+0=7,m26=10 m27=10 m28=10 m29=10,若不裝物品2，m25=m15=3 若裝入物品2，m25=v2+m15-3=7+3=7,C語言動態(tài)規(guī)劃,51,遞推關(guān)系的建立,用mij來表示從前i個物品中選取物品裝入容量為j的背包所得的最大價值。則要尋求的是mnc。 mij是以下兩個值的最大值（1） mi-1j: 即不裝入物品i,背包價值與僅考慮前i-1個物品時情況相同； （2）vi+mi-1j-si:即裝入物品i,再從前i-1個物品中選取，使背包剩余容積j-si價值最大化。,C語言動態(tài)規(guī)劃,52,構(gòu)造價值數(shù)組,背包容量j,從前i個物品中選取,C語言動態(tài)規(guī)劃,53,背包容量j,從前i個物品中選取,C語言動態(tài)規(guī)劃,54,構(gòu)造最優(yōu)解,因m59m49, 物品5被裝