C語言 動(dòng)態(tài)規(guī)劃.ppt

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

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

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

4、 ，C1D2+ f(D2)。 計(jì)算結(jié)果是f(C1)= C1D1+ f(D1)=8 （D1) 同理C2的決策路徑計(jì)算結(jié)果是C2+D2+ E , f(C2)=7 。同理C3的決策路徑計(jì)算結(jié)果是C3+D2+E，f(C3)=10。,2020/9/7,9,（5）第三次輸入結(jié)點(diǎn)為B1，B2，而決策輸出結(jié)點(diǎn)可能為C1，C2，C3。仿前計(jì)算可得Bl，B2的決策路徑為如下情況。Bl: B1C1 費(fèi)用 f(B1)=5+8=13， B2:B2C1 費(fèi)用 f(B2)= 6+8=14，,2020/9/7,10,（6）第四次輸入結(jié)點(diǎn)為A，決策輸出結(jié)點(diǎn)可能為B1，B2。 同理可得決策路徑為A：AB2，費(fèi)用5+14=19 此

5、時(shí)才正式確定每個(gè)子問題的結(jié)點(diǎn)中，那一個(gè)結(jié)點(diǎn)將在最優(yōu)費(fèi)用的路徑上。 子問題的決策中，只對(duì)同一城市（結(jié)點(diǎn)）比較優(yōu)劣。而同一階段的城市（結(jié)點(diǎn)）的優(yōu)劣要由下一個(gè)階段去決定。,2020/9/7,11,2、數(shù)塔問題,有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。,2020/9/7,12,用暴力的方法，可以嗎？,2020/9/7,13,這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如31），則需要列舉出的路徑條數(shù)將是一個(gè)非常龐大的數(shù)目（230= 10243 109=10億）。,試想一下：,2020/9/7,14,拒絕暴力，倡

6、導(dǎo)和諧,2020/9/7,15,從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。 可見，由下層的子問題可以得到上層的子問題，所以，可從底層開始，層層遞進(jìn)，最后得到最大值。 結(jié)論：自頂向下的分析，自底向上的計(jì)算。,考慮一下：,2020/9/7,16,如果各個(gè)子問題不是獨(dú)立的，不同的子問題的個(gè)數(shù)只是多項(xiàng)式量級(jí)，如果我們能夠保存已經(jīng)解決的子問題的答案，而在需要的時(shí)候再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算。由此而來的基本思路是，用一個(gè)表記錄所有已解決的子問題的答案，不管該問題以后是否被用到，只要它被計(jì)算過，就

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

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

9、0,10.3 最長有序子序列,2020/9/7,21,子問題的構(gòu)造,子問題“求以ak（k=1, 2, 3N）為終點(diǎn)的最長上升子序列的長度” 雖然這個(gè)子問題和原問題形式上并不完全一樣，但是只要這N 個(gè)子問題都解決了，那么這N 個(gè)子問題的解中，最大的那個(gè)就是整個(gè)問題的解。 該子問題可以遞推求解,2020/9/7,22,假定MaxLen (k)表示以ak 做為“終點(diǎn)”的最長上升子序列的長度，那么： MaxLen (1) = 1 MaxLen (k) = Max MaxLen (i)：1i k 且 ai ak 且 k1 + 1,2020/9/7,23,實(shí)例：,所求最大值是Fn嗎？,2,2020/9/7

10、,24,10.4 最長公共子序列,一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。 給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。,2020/9/7,25,例如，若X=A，B，C，B，D，B，A，Y=B，D，C，A，B，A，則 序列B，C，A是X和Y的一個(gè)公共子序列，但它不是X和Y的一個(gè)最長公共子序列。 序列B，C，B，A也是X和Y的一個(gè)公共子序列，它的長度為4，而且它是X和Y的一個(gè)最長公共子序列，因?yàn)閄和Y沒有長度大于4的公共子序列。,2020/9/7,26,給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X

11、和Y的公共子序列。 問題：給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。,最長公共子序列,2020/9/7,27,典型應(yīng)用,計(jì)算兩個(gè)文本的相似程度 生物學(xué)上的基因比較,2020/9/7,28,人類基因組計(jì)劃的研究成果,一個(gè)細(xì)胞核內(nèi)的23個(gè)染色體含31億個(gè)核苷酸（只有A、G、T、C四種）； 基因數(shù)在3萬-3.5萬，每個(gè)基因有幾千個(gè)核苷酸； 人與人之間有99.99%的基因序列是相同的。,2020/9/7,29,生物學(xué)家對(duì)鑒別人類基因和確定他們的功能很感興趣。因?yàn)檫@對(duì)診斷人類疾病和開發(fā)新藥很有用。 一旦一段基因被確定后，接下來的工作便是確定它的功能，這個(gè)工作一般

12、是通過搜索基因數(shù)據(jù)庫來進(jìn)行的。數(shù)據(jù)庫中存儲(chǔ)了很多基因序列及其相應(yīng)的功能，將返回與新基因序列功能相似的已知序列。 生物學(xué)家們假設(shè)類似的基因表示類似的功能。確定與待研究基因最相近的一個(gè)已知基因?qū)ι镌囼?yàn)非常必要。,2020/9/7,30,那么如何確定兩個(gè)基因序列的相似性呢，這主要是通過相似性函數(shù)來判斷的。 比如已知兩個(gè)序列AGTGATG和GTTAG，他們有多相似？一個(gè)判斷的方法是在兩個(gè)序列中分別插入若干空格使得兩序列的長度相等， AGTGAT- G - GT - -TAG 這種匹配的函數(shù)值是(-3)+5+5+(-3)+(-3)+5 +(-3)+5=8,2020/9/7,31,窮舉法,對(duì)X的所有子序

13、列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列。 X的所有子序列都檢查過后即可求出X和Y的最長公共子序列。X的每個(gè)子序列相應(yīng)于下標(biāo)集1,2,.,m的一個(gè)子集。因此，共有2m個(gè)不同子序列，故窮舉搜索法需要指數(shù)時(shí)間 。 而事實(shí)上，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì),2020/9/7,32,最長公共子序列的結(jié)構(gòu),首先引入前綴的概念： 給定一個(gè)序列X=x1,x2,xm，對(duì)i=1,m定義X的第i個(gè)前綴為Xi=x1,x2,xi 例如：X=A ,B, C, B,D,A,B 則X4=A ,B, C, B，X0為空序列,2020/9/7,33,最長公共子序列的結(jié)構(gòu),設(shè)序列X=x1,x2,xm

14、和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，則 (1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序列。 (2)若xmyn，則zkxm蘊(yùn)涵Z是xm-1和Y的最長公共子序列。 (3)若xmyn，則zkyn蘊(yùn)涵Z是X和yn-1的最長公共子序列。,由此可見，2個(gè)序列的最長公共子序列包含了這2個(gè)序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(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

15、 C B,2020/9/7,34,子問題的遞歸結(jié)構(gòu),由以上三個(gè)性質(zhì)可知，要X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列，可能要檢查如下子問題： 若xm=yn時(shí)，我們就要找出Xm-1和Yn-1的LCS,將xm=yn拼接到這個(gè)LCS后，就得到 Xm和Yn的 LCS 若xmyn時(shí)，我們需要解決兩個(gè)子問題： 找出 Xm-1和Yn的 LCS，和 Xm和Yn-1 的LCS，取兩者中較長的作為Xm和Yn的 LCS,2020/9/7,35,子問題的遞歸結(jié)構(gòu),由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出X和Y的最長公共子序列，可按如下方式遞歸的進(jìn)行： 若xm=yn時(shí)， LCS(Xm,Yn)=

16、LCS(Xm-1,Yn-1)+xm 若xmyn時(shí)， LCS(Xm,Yn)= 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),2020/9/7,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)系如下：,2020/9/7,37,計(jì)算最優(yōu)值,由于在所考慮的子問題空間中，總共有(mn)個(gè)不同的子問題，因此，用

17、動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。 輸入： X=x1,x2,xm和Y=y1,y2,yn 輸出： 數(shù)組c：cij存儲(chǔ)Xi=x1,x2,xi和Yj=y1,y2,yj的最長公共子序列的長度,2020/9/7,38,算法： 對(duì)i=1到m做 對(duì)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,2020/9/7,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 A

18、B ABC ABCB ABCBD ABCBDA ABCBDAB, B BD BDC ,2020/9/7,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,2020/9/7,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)造最長公共子序列,2020/9/7,42,10.5 0-1背包問題,給定n種物品和一背包。物品i的

19、重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大? 目標(biāo)：使裝入背包中物品的總價(jià)值最大 約束條件：裝入的物品總重不得超過C,2020/9/7,43,海盜盜寶問題,海盜有一背包，最大容積為9，現(xiàn)有5件寶物： 體積si分別是2、3、4、5和4公斤 價(jià)值vi分別是3、7、5、9和 8 請(qǐng)給出裝載方案，使背包價(jià)值達(dá)到最大。,C=9,2020/9/7,44,一開始，見物品就裝，物品1、2、3全裝入，背包裝滿了，得到背包總價(jià)值為15，這是不是最大價(jià)值呢？,考慮只有前三個(gè)物品的情況,2020/9/7,45,物品4該不該裝？有兩個(gè)選擇： （1）不裝，背包價(jià)值

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

21、值最大化？這是n=4,c=5的一個(gè)子問題。 若得到該子問題的解為：裝入物品1、2，得價(jià)值為10,考慮5個(gè)物品的情況,目前最優(yōu)：裝入物品5和1、2，總價(jià)值為1816,2020/9/7,49,子問題的構(gòu)造,當(dāng)n=1時(shí):只有一個(gè)物品， s1=2,v1=3 若背包容量c=0、1，則無法裝入物品1，得到背包價(jià)值為0 若背包容量c=2、3、4、5、6，7，8，9則可裝入物品1，得到背包價(jià)值為3。,C10=0 C11=0 C12=3 C13=3 C14=3 C15=3 C16=3 C17=3 C18=3 C19=3,2020/9/7,50,考慮兩個(gè)物品的情況,當(dāng)n=2時(shí)，有兩個(gè)物品， s1=2,v1=3，s

22、2=3,v2=7 若背包容量c=0、1，得到背包價(jià)值為0 若背包容量c=2，可裝入物品1，得總價(jià)值m22=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,2020/9/7,51,遞推關(guān)系的建立,用mij來表示從前i個(gè)物品中選取物品裝入容量為j的背包所得的最大價(jià)值。則要尋求的是mnc。 mij是以下兩個(gè)值的最大值（1） mi-1j: 即不裝入物品i,背包價(jià)值與僅考慮前i-1個(gè)物品時(shí)情況相同； （2）vi+mi-1j-si:即裝入物品i,再從前i-1個(gè)物品中選取，使背包剩余容積j-si價(jià)值最大化。,2020/9/7,52,構(gòu)造價(jià)值數(shù)組,背包容量j,從前i個(gè)物品中選取,2020/9/7,53,背包容量j,從前i個(gè)物品中選取,2020/9/7,54,構(gòu)造最優(yōu)解,因m59m49, 物品5被裝入