一 無(wú)后向 子問(wèn)題的 [例1]最短路徑問(wèn) [例3]Bitonic旅行路線(xiàn)問(wèn) [例4]計(jì)算矩陣連乘 [例5]最長(zhǎng)公共子序列問(wèn)題 [例6]凸多邊形的最優(yōu)三角剖分問(wèn) [例7]多邊形計(jì)算 [例8]字符識(shí)別 [例9]編輯距 其他資 DynamicStarfish 些算法作了比較，最后還簡(jiǎn)單介紹了動(dòng)態(tài)規(guī)劃的數(shù)學(xué)理論基礎(chǔ)和當(dāng)前的研一、動(dòng)態(tài)規(guī)劃的基本動(dòng)態(tài)規(guī)劃的發(fā)展及研究?jī)?nèi)動(dòng)態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初數(shù)學(xué)家R.E.Bellman多階段決策過(guò)程(multistepdecisionprocess)的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過(guò)法——?jiǎng)討B(tài)規(guī)劃。1957年了他的名著DynamicProgramming，這是該領(lǐng)域多階段決策問(wèn)多階段決策過(guò)程決策序列。要使整個(gè)活動(dòng)的總體效果達(dá)到最優(yōu)的問(wèn)題，稱(chēng)為多階段決策問(wèn)題12]1(千元)，每次開(kāi)工的固定成本為3(千元)，工廠(chǎng)每季度的最大生產(chǎn)能力為6(千件)。經(jīng)，市場(chǎng)對(duì)該產(chǎn)品的需2，3，2，4(千件)。如果工廠(chǎng)在第一、二季第三、四季度才能上市的產(chǎn)品需付費(fèi)，每季每千件的費(fèi)為0.5(千季度的產(chǎn)量，使一年的總費(fèi)用(生產(chǎn)成本和費(fèi))最少。決策過(guò)程的分timedecisionprocess)，即多階段決策過(guò)程和連續(xù)時(shí)間決策過(guò)程(continuous-timedecisionprocess)；根據(jù)過(guò)程的演變是確定的還是隨機(jī)的，分為確定性決策過(guò)程(deterministicdecisionprocess)和隨機(jī)性決策過(guò)程(stochasticdecisionprocess)，其中應(yīng)用最廣的是確定性多階段決策過(guò)動(dòng)態(tài)規(guī)劃模型的基本要階k=1,2,..,n1中由Ak=1Bi(i=1,2)k=2Di(i=1,2,3)出發(fā)為k=4，n=42k=1,2,3,4，共4狀狀態(tài)(state)特征并且具有無(wú)后向性描述狀態(tài)的變量稱(chēng)狀態(tài)變量(statevariable)。變量允許取值的范圍稱(chēng)允許狀態(tài)集合(setofadmissiblestates)。用xk表示第k階段的狀態(tài)變量，它可以是一個(gè)數(shù)或一個(gè)向量。用Xk表示第k1中x2可取nn+1，xn+1表示xn1中x5E狀態(tài)變量簡(jiǎn)稱(chēng)為狀態(tài)決態(tài)，這種選擇稱(chēng)為決策(decision)，在最優(yōu)控制問(wèn)題中也稱(chēng)為控制描述決策的變量稱(chēng)決策變量(decisionvariable)。變量允許取值的范圍稱(chēng)允許決策集合(setofadmissibledecisions)。用uk(xk)表示第k階段處于狀態(tài)xk時(shí)的決策變量，它是xk的函數(shù)，用Uk(xkxk1u2(B1C1,C2,C3。決策變量簡(jiǎn)稱(chēng)決策策決策組成的序列稱(chēng)為策略)。由初始狀態(tài)x1開(kāi)始的全過(guò)程的策略記作p1n(x1p1n(x1)={u1(x1),u2(x2),...，un(xnkxk開(kāi)始到終止?fàn)顟B(tài)的后部子過(guò)程的策略記作pkn(xkpkn(xk)={uk(xk),uk+1(xk+1),...，un(xnk到第jpkj(xk)={uk(xk),uk+1(xk+1),...，uj(xjkxk，可供選擇的策略pkj(xk)有一定的范圍，稱(chēng)為允許策略集合(setofadmissiblepolicies)P1n(x1),Pkn(xk),Pkj(xk)表示。狀態(tài)轉(zhuǎn)移方定。用狀態(tài)轉(zhuǎn)移方程(equationofstate)表示這種演變規(guī)律，寫(xiě)作1指標(biāo)函數(shù)和最優(yōu)值函指標(biāo)函數(shù)(objectivefunction)是衡量過(guò)程優(yōu)劣的數(shù)量指標(biāo)，它是關(guān)于策略的數(shù)量函數(shù)，從階段kn的指標(biāo)函數(shù)用Vkn(xk,pkn(xk))表示，能夠用動(dòng)態(tài)規(guī)劃解決的問(wèn)題的指標(biāo)函數(shù)應(yīng)具有可分離性，即Vkn可表為xk,uk,Vk+1n的函數(shù)，記為： 是一個(gè)關(guān)于變量Vk+1n單調(diào)遞增的函數(shù)。這一性質(zhì)保證了最優(yōu)化原理(principleofoptimality)的成立，是動(dòng)態(tài)規(guī)劃的適用前提。過(guò)程在第j階段的階段指標(biāo)取決于狀態(tài)xj和決策uj，用vj(xj,uj到階段nvj(j=k,k+1,..n)這些形式下第kj階段子過(guò)程的指標(biāo)函數(shù)為Vkj(xk,uk,xk+1,...,xj+1)?？梢园l(fā)現(xiàn)，上述(3)-(5)1為(3)vj(xj,uj)是邊<xj,uj(xj)>的權(quán)（邊的長(zhǎng)度）,uj(xjxj出發(fā)根據(jù)決策uj(xj)下一步所到達(dá)的節(jié)點(diǎn)。根據(jù)狀態(tài)轉(zhuǎn)移方程，指標(biāo)函數(shù)Vkn還可以表示為狀態(tài)xk和策略pkn的函數(shù)，即Vkn(xk,pkn)。在xk給定時(shí)指標(biāo)函數(shù)Vkn對(duì)pkn的最優(yōu)值稱(chēng)為最優(yōu)值函數(shù)(optimalvaluefunction)fk(xk)，即optmaxmink個(gè)狀態(tài)xk，從該階段knxk出發(fā)取遍所有能策略pkn所得到的最優(yōu)指標(biāo)值中最優(yōu)的一個(gè)。最優(yōu)策略和最優(yōu)軌使指標(biāo)函數(shù)Vkn達(dá)到最優(yōu)值的策略是從kp*={u*,..u*},p*又是全過(guò)程的最優(yōu)策略，簡(jiǎn)稱(chēng)最優(yōu)策略(optimal) 從初始狀態(tài)x(=x*)出發(fā)，過(guò)程按照 {x*,x*,..,x*}稱(chēng)最優(yōu)軌線(xiàn)(optimaltrajectory) 二、動(dòng)態(tài)規(guī)劃的基本定理和基本方動(dòng)態(tài)規(guī)劃發(fā)展的早期階段，從簡(jiǎn)單邏輯出發(fā)給出了所謂最優(yōu)性原理，然后在最優(yōu)策略存在的前提下導(dǎo)出基本方程，再由這個(gè)方程求解最優(yōu)策略。后來(lái)在動(dòng)態(tài)規(guī)劃的應(yīng)用過(guò)程中發(fā)現(xiàn)，最優(yōu)性原理不是對(duì)任何決策過(guò)程普遍成立，它與基本方程不是無(wú)條件等價(jià)，二者之間也不存在任何確定的蘊(yùn)含關(guān)系態(tài)規(guī)劃中起著更為本質(zhì)的作用。[基本定理對(duì)于初始狀態(tài)x∈Xp*={u*,..u* k,1<k<=n,

若p*∈P(xk,1<k<n，p*對(duì)于由 1,k- 和 *確定的以x*為起點(diǎn)的第k到n1,k- 上述推論稱(chēng)為最優(yōu)化原理決策必定構(gòu)成最優(yōu)策略。根據(jù)基本定理的推論可以得到動(dòng)態(tài)規(guī)劃的基本方程其中 是決策過(guò)程的終端條件，為一個(gè)已知函數(shù)。當(dāng)只取固定的狀態(tài)時(shí)稱(chēng)固定終端；當(dāng)xn+1可在端集合Xn+1中變動(dòng)時(shí)稱(chēng)自由終端。最終要求的最優(yōu)指標(biāo)函數(shù)滿(mǎn)足(10)式：(9)式是一個(gè)遞歸，如果目標(biāo)狀態(tài)確定，當(dāng)然可以直接利用該遞歸求出 三、動(dòng)態(tài)規(guī)劃的適用條最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)2IJACJ必是從BCJ'B到C最優(yōu)路徑，則A到C的路線(xiàn)取I和J'比I和J更優(yōu)，。從而證明J'必是B到C1段的狀態(tài)無(wú)法直接影響它未來(lái)的決策，而只能通過(guò)當(dāng)前的這個(gè)狀態(tài)。換句話(huà)說(shuō)，每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)。這就是無(wú)后向性，又稱(chēng)為性。xk，無(wú)論p1,k-1如何，最優(yōu)子策略pkn*是唯一確定的，這種性質(zhì)稱(chēng)為無(wú)后向性。3]Bitonic貨郎擔(dān)問(wèn)題是對(duì)平面給定的n3(a)給出了七個(gè)點(diǎn)問(wèn)題的解。Bitonic右邊的點(diǎn)，然后再?lài)?yán)格地由右至左到出發(fā)點(diǎn)，求路程最短的路徑長(zhǎng)度。圖（b）7，所以一條路(P1-P2)可以看成兩條Bitonic[P1,P2]如果可以由階段[Q1,Q2]推出，則必須滿(mǎn)足的條件就是:P1<Q1P2<Q2。例如，階段[3,4]中的道路可以由階段[3,5]4-5[3,5]的狀態(tài)卻無(wú)法由階段[3,4]Bitonic知。因此我們可以說(shuō)，Bitonic問(wèn)題滿(mǎn)足無(wú)后向性，可以用動(dòng)態(tài)規(guī)劃來(lái)解決子問(wèn)題的1BitonicO(n2O(n!)，但從空間復(fù)雜度來(lái)O(n2O(n)，搜索算法反而優(yōu)于動(dòng)態(tài)規(guī)劃設(shè)原問(wèn)題的規(guī)模為n，容易看出，當(dāng)子問(wèn)題樹(shù)中的子問(wèn)題總數(shù)是n的超多項(xiàng)式函數(shù)，而不同的子問(wèn)題數(shù)只是n的多項(xiàng)式函數(shù)時(shí)，動(dòng)態(tài)規(guī)劃法顯得特別有意義，此時(shí)動(dòng)態(tài)規(guī)劃法具有線(xiàn)性時(shí)間復(fù)雜性。所以，能夠用動(dòng)態(tài)規(guī)劃解決的問(wèn)還有一個(gè)顯著特征：子問(wèn)題的性。這個(gè)性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要件，但是如果該性質(zhì) ，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)四、動(dòng)態(tài)規(guī)劃的基本思前文主要介紹了動(dòng)態(tài)規(guī)劃的一些理論依據(jù)，前文所說(shuō)的具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的動(dòng)態(tài)規(guī)劃稱(chēng)為標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解（即滿(mǎn)足最優(yōu)子化原理），動(dòng)態(tài)規(guī)劃解決。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想解決冗余動(dòng)態(tài)規(guī)劃解為更小的、相似的子問(wèn)題，并子問(wèn)題的解而避免計(jì)算重復(fù)的子問(wèn)題，以解決最優(yōu)化問(wèn)題的算法策略。因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問(wèn)題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問(wèn)題樹(shù)中的子問(wèn)題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問(wèn)用，不必重新求解。五、動(dòng)態(tài)規(guī)劃算法的基本標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃的基本框?qū)n+1(xn+1)初始化 {邊界條件fork:=ndownto1for每一個(gè)xk∈Xkfor每一個(gè)uk∈Uk(xkdofk(xk):=一個(gè)極值 {∞或 {基本方程(9) tfk(xkthenfk(xk):=t;{計(jì)算fk(xk)的最優(yōu)值}t:=一個(gè)極值 {∞或for每一個(gè)x1∈X1iff1(x1)比t更優(yōu)then {按照10式求出最優(yōu)指標(biāo)以自底向上的方式或自頂向下的化方法（備忘錄法）計(jì)算出最優(yōu)步驟(3)中計(jì)算最優(yōu)值時(shí)，通常需記錄的信息，以便在步驟(4)中，根據(jù)所六、動(dòng)態(tài)規(guī)劃的實(shí)例分下面通過(guò)實(shí)例來(lái)分析動(dòng)態(tài)規(guī)劃的設(shè)計(jì)步驟和具體應(yīng)用。例1已經(jīng)文12345645678（即為了解決問(wèn)題要進(jìn)行兩次動(dòng)態(tài)規(guī)劃）的例子。123Bitonic456781短1A到結(jié)點(diǎn)E 是與v相鄰的節(jié)點(diǎn)的集合，w(v,u)表示從v到u的邊的長(zhǎng)度。functionifv=Ethenreturn0for所有沒(méi)有過(guò)的節(jié)點(diǎn)idoifv和ithen標(biāo)記i過(guò)了t:=vi+MinDistance(i);標(biāo)記i未過(guò);ift<minthenmin=t;開(kāi)始時(shí)標(biāo)記所有的頂點(diǎn)未過(guò)，MinDistance(A)就是從A到E的最短距離這個(gè)程序的效率如何呢？我們可以看到，每次除了已經(jīng)過(guò)的城市外，其他城市都要，所以時(shí)間復(fù)雜度為O(n!)，這是一個(gè)“指數(shù)級(jí)”的算法，那B1EC2到EB2到EC2EC2到EC1、C2ED1ED1E是，可以改進(jìn)該算法，將每次求出的從vEMinDistance(vMinDistance(v)，如果點(diǎn)有nnO(n)。1，可以發(fā)現(xiàn)，A只和Bi相鄰，Bi只和Ci相鄰,...，依此類(lèi)推。這樣，4S1={A},S2={B1,B2},S3={C1,C2,C3,C4},S4={D1,D2,D3}，F(xiàn)k(u)Sk中的點(diǎn)uE顯然可以遞推地求出F1(A)，AEO(n)，因?yàn)樗械臓顟B(tài)總數(shù)（節(jié)點(diǎn)總數(shù)）n，對(duì)每個(gè)狀態(tài)都只要遍歷一次，procedureDynamicProgramming;fori:=4downto1doforeachu∈SkdoFk[u]:=foreachv∈Sk+1∩δ(u)ifFk[u]>w(u,v)+Fk+1[v]then輸出這種高效算法，就是動(dòng)態(tài)規(guī)劃算法3]Bitonic問(wèn)問(wèn)題描貨郎擔(dān)問(wèn)題是對(duì)平面給定的n1(a)給出了七個(gè)點(diǎn)問(wèn)題的解。Bitonic貨郎擔(dān)問(wèn)題的簡(jiǎn)化，這種旅行路線(xiàn)先從最左邊開(kāi)始，嚴(yán)格地嚴(yán)格地1（b）出了七個(gè)點(diǎn)問(wèn)題的解。Bitonic首先將nXL=<1，2，…n>。L[n]為最右點(diǎn)，L[1]11：L[0]=L[1]=1。Wi,j--邊<i,j>Wi..j--j-i<i,i+l>,<i+l,i+2>，…,<j-2,j-1>,<j-1,j> 。由點(diǎn)i至點(diǎn)j的連續(xù)邊組成的路徑稱(chēng)為連續(xù)路徑d[i]ini-1我們專(zhuān)門(mén)設(shè)置了一張表k[i](1≤i≤n)，記下使得d[i]最小的J值。顯然d[n]=Wn,n-1，k[n]=n。由d[i]的遞歸式和表k[i]的定義可以看出，在由點(diǎn)i-1至點(diǎn)i的最短路上，點(diǎn)ik[i]的子路徑上的點(diǎn)序號(hào)是遂一遞增的，為由左至右方向上的連續(xù)子路徑。按照遞歸定義，若k[i]≠Nk[k[i]+1]≠N，k[k[i]+1]+1k[k[k[i]+1]+1]k[k[i]+1]k[i]+1d[i]d[i+1]…d[n-1],d[n]最小,d[i]包含了d[i+1]…d[n]最小的子問(wèn)題，因此該問(wèn)題具有最優(yōu)子結(jié)構(gòu)和子問(wèn)題性質(zhì)，d[n]規(guī)劃方法依次求d[n-1],d[n-2],…,d[1]，充分利用子問(wèn)題。最后求得的d[1]便是最短路線(xiàn)的距離；從點(diǎn)1出發(fā)，順著表k的指示可以遞歸遞輸出這條路線(xiàn)。4乘在科學(xué)計(jì)算中經(jīng)常要計(jì)算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數(shù)等于矩陣B的行數(shù)。若A是一個(gè)p×q的矩陣，B是一個(gè)q×r的矩陣，則其乘積C=AB是一個(gè)p×r的矩陣。其標(biāo)準(zhǔn)計(jì)算為：由該知計(jì)算C=AB總共需要pqr次的數(shù)乘現(xiàn)在的問(wèn)題是，給定n{A1,A2,…,AnAi與Ai+1是可乘的，i=1,2,…,n-1。要求計(jì)算出這n個(gè)矩陣的連乘積A1A2…An。若矩陣連乘積AA連乘積BCA=(BC)。例如，矩陣連乘積A1A2A3A45(((A1A2)A3)A43{A1，A2，A3310×100，100×55×50。若按第一種加括號(hào)方式((A1A2)A3)來(lái)計(jì)算，總共需10×100×5+10×5×50=7500(A1(A2A3))來(lái)100×5×50+10×100×50=75000。第二種加括號(hào)方10個(gè)矩陣{A1,A2,…,nAi的維數(shù)為pi-1×i，i=1,2,…,n)，如何確定計(jì)算矩陣連乘積A1A2…An說(shuō)明：計(jì)算兩個(gè)均為n×n的矩陣(n階方陣)Strassen矩陣乘法，利用分治思nO(n2367)。但無(wú)論如何，所需的乘法次數(shù)總隨兩個(gè)矩陣的階而遞增。在這道題中只考慮采用標(biāo)準(zhǔn)計(jì)算兩個(gè)矩陣的乘積。參考解而，這樣做計(jì)算量太大。事實(shí)上，對(duì)于nP(n)個(gè)不同的計(jì)算次序。由于我們可以首先在第kk+1解此遞歸方程可得,P(n)CatalanP(n)=C(n-1)，也就是說(shuō)，P(n)隨著n的增長(zhǎng)是指數(shù)增長(zhǎng)的。因此，窮舉搜索法不是一個(gè)有效分析最優(yōu)解的結(jié)首先，為方便起見(jiàn)，將矩陣連乘積AiAi+1…Aj簡(jiǎn)記為Aij。我們來(lái)看計(jì)算A1n的一個(gè)最優(yōu)次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開(kāi)，1<=k<n，則完全加括號(hào)方式為((A1…Ak)(Ak+1…AnA1k和Ak+1n，然后，將所得的結(jié)果相乘才得到A1n。顯然其總計(jì)算量為計(jì)算A1k的計(jì)算量加上計(jì)算Ak+1n的計(jì)算量，再加上A1k與Ak+1n相乘的計(jì)算量。這個(gè)問(wèn)題的一個(gè)關(guān)鍵特征是：計(jì)算A1n的一個(gè)最優(yōu)次序所包含的計(jì)算A1k的次序也是最優(yōu)的。事實(shí)上，若有一個(gè)計(jì)算A1k的次序需要的計(jì)算量更少，則用此次序替換原來(lái)計(jì)算A1k的次序，得到的計(jì)算A1n的次序需要的計(jì)算量將比最優(yōu)次序所需計(jì)算量更少，這是一個(gè)。同理可知，計(jì)算A1n的一個(gè)最優(yōu)次序所包含的計(jì)算矩陣子鏈Ak+1n的次序也是最優(yōu)的。根據(jù)該問(wèn)題的指標(biāo)函數(shù)的建立遞歸對(duì)于矩陣連乘積的最優(yōu)計(jì)算次序問(wèn)題，設(shè)計(jì)算Aij,1≤i≤j≤n，所需m[i,j]，m[1,n]。i=j，Aij=Aim[i,i]=0，i=1,2,…,n；i<jm[i,j]Aij的最優(yōu)次序在A(yíng)k和Ak+1之間斷開(kāi)，i≤k<j，則：由于在計(jì)算時(shí)我們并不知道斷開(kāi)點(diǎn)AAk位置只有j-i個(gè)可能，即k∈{i,i+1,…,j-1k是這j-im[i,j]可以遞歸地定義為：m[i,j]Aij所需的最少數(shù)乘次數(shù)。同時(shí)還確定了計(jì)算Aij的最優(yōu)次序中的斷開(kāi)位置k，也就是說(shuō)，對(duì)于這個(gè)km[i,j]=m[i,k]m[k+1,j]pi-1pkpjm[i,j]ks[i,j]計(jì)算最優(yōu)m[i,j]的遞歸定義(2.1)，m[1,n]。稍后看到，簡(jiǎn)單地遞歸計(jì)算將耗費(fèi)指數(shù)計(jì)算時(shí)間。然而，我們注意到，在θ(n21≤i≤j≤n用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)遞歸式(2.1)以自底向上的方式計(jì)算，在計(jì)算過(guò)程中，保存已解決的子問(wèn)題答案，每個(gè)子問(wèn)題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)m[i,j]動(dòng)態(tài)規(guī)劃算法中，輸入是序列P={p0,p1,…,nm[i,j]外，還有使m[i,j]=m[i,k]+m[k+1,j]+pi-k=s[i,j]，1≤i≤j≤nProcedureMATRIX_CHAIN_ORDER(p);forj:=1tondon}fori:=jdownto1doifi=jthenelsefork:=itoj-1doifq<m[i,j]then{s[i,j]A[i..j]

m[n- 的順序根據(jù)(2.1)計(jì)算m[i,j]構(gòu)造最優(yōu)MATRIX_CHAIN_ORDERMATRIX_CHAIN_ORDER所需的最少數(shù)乘次數(shù)，還不知體應(yīng)按什么次序來(lái)做矩陣乘法才能達(dá)到數(shù)乘然而，MATRIX_CHAIN_ORDER息。事實(shí)上，s[i,j]kAij的最佳方式應(yīng)在矩陣Ak和Ak+1之間斷開(kāi)，即最優(yōu)的加括號(hào)方式應(yīng)為(A1...k)(Ak+1ns[i,j]記錄的信息可知計(jì)算A1n(A1s[1,n])(As[1,n]+1n)。而計(jì)算A1s[1,n]的最優(yōu)加括號(hào)方式為(A1s[1,s[1,n]])(As[1,s[1,n]]+1s[1,n])。同理可以確定計(jì)算As[1,n]+1ns[s[1,n]+1,n]處斷開(kāi)?！沾诉f推下去，最終可以確定As[1,n]+1n的最優(yōu)完全加括號(hào)方式，即構(gòu)造出問(wèn)題的一個(gè)最優(yōu)解。MATRIX_CHAIN_MULTIPLY(A,s,i,jsA={A1,A2,…,AnAij的連乘積的算法。ProcdeureMATRIX_CHAIN_MULTIPLY(A,s,i,j);ifj>ireturn(MATRIX_MULTIPLY(X,Y));X*Yelse要計(jì)算A1nMATRIX_CHAIN_MULTIPLY(A,s,1,n從算法MATRIX_CHAIN_ORDER可以看出，該算法的有效性依賴(lài)于問(wèn)題本 指導(dǎo)意義。下面我們著重研究最優(yōu)子結(jié)構(gòu)性質(zhì)問(wèn)題性質(zhì)以及動(dòng)態(tài)規(guī)劃最優(yōu)子結(jié)設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的第1步通常是要刻劃最優(yōu)解的結(jié)構(gòu)。當(dāng)問(wèn)題的最優(yōu)解包含A1n的最優(yōu)完全加括號(hào)方式在A(yíng)k和Ak+1之間將矩陣鏈斷開(kāi)，則由該次序確定的子鏈A1k和Ak+1n的完全加出一個(gè)比原問(wèn)題最優(yōu)解更好的解，從而導(dǎo)致。θ(n2題空間的規(guī)模僅為θ(n2)。子問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這問(wèn)題的為了說(shuō)明這一點(diǎn)，我們來(lái)看在計(jì)算矩陣連乘積最優(yōu)計(jì)算次序時(shí)，利用直接計(jì)算AijFunctionifi=jthenfork:=itoj-1doifq<m[i,j]then圖 計(jì)算A14的遞歸RECURSIVE_MATRIX_CHAIN(P,1,4A141T(n)有指數(shù)下界。設(shè)算法中判斷語(yǔ)句和賦T(n)n>1據(jù)此，可用數(shù)學(xué)歸納法證明T(n)≥2n-1=Ω(2nRECURSIVE_MATRIX_CHAIN(P,1,nnMATRIX_CHAIN_ORDER(P,1,n)只需計(jì)算時(shí)間O(n2)。其有效性就在于它充分利用了問(wèn)題的子問(wèn)題性質(zhì)。不同的子問(wèn)題個(gè)數(shù)為θ(n2)，而動(dòng)態(tài)規(guī)劃算法對(duì)于每個(gè)不同的子問(wèn)題只計(jì)算一次，不備忘錄方看其相應(yīng)的記錄項(xiàng)。若記錄項(xiàng)中的是初始化時(shí)存入的特殊值，則表示該子值，則表示該子問(wèn)題己被求解過(guò)，其相應(yīng)的記錄項(xiàng)中的是該子問(wèn)題的解MEMOIZED_MATRIX_CHAIN(P忘錄方法。Procedurefori:=1tonforj:=1tonFunctionLOOKUP_CHAIN(P,i,j);ifm[i,j]<∞thenifi=jthem[i,j]:=0fork:=itoj-1doq:=LOOKUP_CHAIN(P,i.,k)+LOOKUP_CHAIN(P,k+1,j)+pi-ifq<m[i,j]thenm[i,j]:=q;MATRIX_CHAIN_ORDERMEMOIZED_MATRIX_CHAIN用數(shù)組m[1…n,1…n]m[i,j]Aij的最優(yōu)計(jì)算量。M[i,j]Aij的子問(wèn)題還未被計(jì)算。在調(diào)用LOODKUP_CHAIN(P,i,j)時(shí)，若m[i,j]<∞，則表示m[i,j]中的是所要求子m[i,j]后返回。因此，LOODKUP_CHAIN(P,i,j)m[i,j]的值，但僅在它第一次被調(diào)用時(shí)計(jì)算，以后的調(diào)用就直接MEMOIZED_MATRIX_CHAINO(n3)。事實(shí)O(n2m[i,j]，i=1,2,…,n,j=i,i+1,…n，這些記錄O(n2)時(shí)間。每個(gè)記錄項(xiàng)只填入一次，每次填入時(shí)，不包括填入O(n)。因此，LOODKUP_CHAIN(P,1,nO(n2)個(gè)O(n3)計(jì)算時(shí)間。由此可見(jiàn)，通過(guò)使用備忘錄技術(shù)，直接遞歸算法的計(jì)算時(shí)間從仍Ω(2nO(n3)。向上的動(dòng)態(tài)規(guī)劃算法在O(n3)時(shí)間內(nèi)求解。這兩個(gè)算法都利用了子問(wèn)題性質(zhì)?？偣灿笑?n2)個(gè)不同的子問(wèn)題。對(duì)每個(gè)子問(wèn)題，兩種方法都只解一次，并5]最長(zhǎng)公共子序列問(wèn)題問(wèn)題描X=<x1x2xmZ=<z1z2zkX的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列<i1,i2,…,ikj=1,2,…,kXY，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱(chēng)Z是序列XYX=<A,B,C,B,D,A,BY=<B,D,C,A,B,A>，則序列<B,C,A>XY<B,C,B,A>XYXY列，因?yàn)閄Y4最長(zhǎng)公共子序列(LCS)X=<x1x2xmy2yn>，要求找出XY最長(zhǎng)公共子序列的結(jié)X序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并且在檢查過(guò)程中選出最長(zhǎng)的公共子序列。X的所有子序列都檢查過(guò)后即可求出XY的最長(zhǎng)公共子序列。X的一個(gè)子序列相應(yīng)于下標(biāo)序列{1,2,…,m}的一個(gè)子序列，因此，X2m個(gè)不同子序列，從而窮舉搜索法需要指數(shù)時(shí)間。定理:LCSX=<x1x2xmY=<y1y2ynZ=<z1,z2,…,zk>，則：xm=yn，則zk=xm=ynZk-1是Xm-1Yn-1xm≠yn且zk≠xm，Z是Xm-1Yxm≠yn且zk≠ynZ是XYn-1其中Xm-1=<x1x2xm-1>，Yn-1=<y1y2yn-1>，Zk-1=<z1z2zk-1>。zk≠xm，則<z1,z2,…,zk,xm>是XYk1的公共子序列。這與Z是X和Y的一個(gè)最長(zhǎng)公共子序列。因此，必有zk=xm=yn。由此可Zk-1Xm-1和Yn-1k-1Xm-1Yn-1有一個(gè)長(zhǎng)度k-1的公共子序列W，則將xmX和Y的一個(gè)長(zhǎng)度大于k的公共子序列。此為。故Zk-1是Xm-1和Yn-1的一個(gè)最長(zhǎng)公共子序列。zk≠xm，ZXm-1和YXm-1Yk的公共子序列WWXYk的公共子序列。這與ZX和Y的一個(gè)最長(zhǎng)公共子序列。由此即知Z是Xm-1和Y的一個(gè)最長(zhǎng)公共子序與2.子問(wèn)題的遞歸結(jié)X=<x1,x2,…,xmY=<y1y2yn>的最長(zhǎng)公共子序列，可按以下方式遞歸地進(jìn)行：當(dāng)時(shí)，找出Xm-1和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上x(chóng)m(=ynX和Y的一個(gè)最長(zhǎng)公共子序列。當(dāng)xm≠yn時(shí)，必須解兩個(gè)子問(wèn)題，即找出Xm-1和Y個(gè)最長(zhǎng)公共子序列及X和Yn-1的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者即為XY由此遞歸結(jié)構(gòu)容易看到最長(zhǎng)公共子序列問(wèn)題具有子問(wèn)題性質(zhì)。例如，在計(jì)算XY的最長(zhǎng)公共子序列時(shí)，可能要計(jì)算出X和Yn-1及Xm-1和Y的最長(zhǎng)公共子序列。而這兩個(gè)子問(wèn)題都包含一個(gè)公共子問(wèn)題，即計(jì)算Xm-1和Yn-1的最長(zhǎng)公共子c[i,j]Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中Xi=<x1x2xi>，Yj=<y1,y2,…,yji=0j=0Xi和Yj的最長(zhǎng)公共子序c[i,j]=0。其他情況下，由定理可建立遞歸關(guān)系如下：計(jì)算最優(yōu)直接利用(2.2)c[i,j]的遞歸算法，但其計(jì)算時(shí)間是隨輸θ(m*n)個(gè)不同計(jì)算最長(zhǎng)公共子序列長(zhǎng)度的動(dòng)態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=<x1,x2,…,xmY=<y1,y2,…,ync[0..m,0..nb[1..m,1..n]。其中c[i,j]Xi與Yj的最長(zhǎng)公共子序列的長(zhǎng)度，b[i,j]記c[i,j]要用到。最后，XYc[m,n]中。ProcedureLCS_LENGTH(X,Y);fori:=1tomdoc[i,j]:=0;forj:=1tondoc[0,j]:=0;fori:=1tomdoforj:=1tonifx[i]=y[j]thenc[i,j]:=c[i-1,j-elseifc[i-1,j]≥c[i,j-1]thenc[i,j]:=c[i-c[i,j]:=c[i,j-由于每個(gè)數(shù)組單元的計(jì)算耗費(fèi)Ο(1)時(shí)間，算法LCS_LENGTH耗時(shí)Ο(mn)構(gòu)造最長(zhǎng)公共子序LCS_LENGTHbX=<x1,x2,…,xm>Y=<y1,y2,…,ynb[m,n]開(kāi)始，沿著其中的箭頭所指的方向在數(shù)組bb[i,j]Xi與Yj的最長(zhǎng)公共子序列是由Xi-1與Yj-1的最長(zhǎng)公共子序列在尾部加上x(chóng)i得到的子序列；當(dāng)b[i,j]Xi與Yj的最長(zhǎng)公共子序列和Xi-1與Yj的最長(zhǎng)公共子b[i,j]Xi與Yj的最長(zhǎng)公共子序列和Xi與Yj-1下面的算法LCS(b,X,i,j)實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi與Yj的最長(zhǎng)公共子序列。通過(guò)算法的調(diào)用LCS(b,X,length[X],length[Y])，便可打印出序列X和Y的最ProcedureLCS(b,X,i,j);ifi=0orj=0thenifb[i,j]="↖"thenLCS(b,X,i-1,j-print(x[i]);x[i]}elseifb[i,j]="↑"thenLCS(b,X,i-elseLCS(b,X,i,j-LCSij1，O(m+n)X=<A，B，C，B，D，A，B>Y=<B，D，C，A，B，A>LCS_LENGTHLCS2 0 0 ↑ ↖1A│ 1← 1│ ↑ 2B│ 1←1← 2←2│↑↑↖↑↑3C│1 2←22│ ↑│4B│1 33│↑ ↑↑5D│1 33│↑ ↑↑│6A│1 34│ ↑↑7B│1 45圖 算法LCS的計(jì)算結(jié)算法的改LCS_LENGTHLCSbc[i,j]c[i-1,j-1]，c[i-1,j]c[i,j-1]三個(gè)值之一確定，而數(shù)b[i,j]c[i,j]LCS中，我們可以不借助于數(shù)組bcc[i,j]的值是由c[i-1,j-1]，c[i-1,j]c[i,j-1]Ο(1)時(shí)間。既然bLCSLCS_LENGTHθ(mn)LCS_LENGTHLCSΟ(mn)Ο(m+n)cΟ(mn)的空間，因此這里所作的少。事實(shí)上，在計(jì)算c[i,j]時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，只min(m,n)。6]凸多邊形的最優(yōu)三角問(wèn)題描多邊形首尾相接的直線(xiàn)段組成的。組成多邊形的各直線(xiàn)段稱(chēng)為該多邊形的邊。多邊形相接兩條邊的連接點(diǎn)稱(chēng)為多邊形的頂點(diǎn)。若多邊形的邊之間除了連接頂點(diǎn)外沒(méi)有別的公共點(diǎn)，則稱(chēng)該多邊形為簡(jiǎn)單多邊形3凸多邊形。也就是說(shuō)凸多邊形邊界上或內(nèi)部的任意兩點(diǎn)所連成的直線(xiàn)段上所有的點(diǎn)均在該凸多邊形的內(nèi)部或邊界P=<v0,v1vn-1>表示具有nv0v1，v1v2,vn-1vn的一個(gè)凸多邊形，其中，約定v0=vn。若vi與vj是多邊形上不相鄰的兩個(gè)頂點(diǎn)，則線(xiàn)段vivj稱(chēng)為多邊形的一條弦。弦將多邊形分割成凸的兩個(gè)子多邊形<vi,vi+1,…,vj>和<vj,vj+1vi>。多邊形的三角剖分是一個(gè)將多邊形分割成互不重迭的三角形的弦的集合T1 12在凸多邊形PT即PTTn的三角刮分中，恰好有n-3條弦和n-2P=<v0,v1,vn-1ω。要求確定該凸多可以定義三角形上各種各樣的權(quán)函數(shù)W ω(△vivjvk)=|vivj|+|vivk|+|vkvj|,其中，|vivj|是點(diǎn)vi到vj的歐氏距離。出。這里的所謂完全二叉樹(shù)是指葉結(jié)點(diǎn)以外的所有結(jié)點(diǎn)的度數(shù)都為2的二叉(注意與滿(mǎn)二叉樹(shù)和近似滿(mǎn)二叉樹(shù)的區(qū)別)3(a)所示。圖 表達(dá)式語(yǔ)法樹(shù)與三角剖分的對(duì)一個(gè)表示表達(dá)式E1的左，以及一個(gè)表示表達(dá)式Er的右，則以該結(jié)點(diǎn)為根的表示表達(dá)式(E1Er)。因此，有n個(gè)原子的完全加括號(hào)表達(dá)式對(duì)應(yīng)于唯一的一棵有n凸多邊形<v0,v1,…,vn-1>的三角剖分也可以用語(yǔ)法樹(shù)來(lái)表示。例如，3(a)3(b)所示的語(yǔ)法樹(shù)來(lái)表示。該語(yǔ)法樹(shù)的根結(jié)點(diǎn)為邊v0v6，三角剖分中的弦組成其余的內(nèi)部結(jié)點(diǎn)。多邊形中除v0v6邊外的每一條邊是語(yǔ)法樹(shù)的一個(gè)葉結(jié)點(diǎn)。樹(shù)根v0v6是三角形v0v3v6的一條邊，該三角形3v0v3v6，凸多邊形<v0,v1,…,v3>和凸多邊形<v3,v4v6>。三角形v0v3v6的另外兩條邊，即弦v3v6和v0v3為根的兩個(gè)兒子。以它們?yōu)楦姆謩e表示凸多邊形<v0,v1,…,v3>和凸多邊形<v3,v4v6在一般情況下，一個(gè)凸nn-1法樹(shù)。反之，也可根據(jù)一棵有n-1n三角剖分。也就是說(shuō)，凸nn-1一對(duì)應(yīng)關(guān)系。由于nn一對(duì)應(yīng)關(guān)系，因此n(n+1)邊形的三角剖分之間3(a)和(b)n=6。矩陣連乘積A1A2..A6中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1vi-1vi。三角剖分中的一條弦vivj，i<j-1，Ai+1..j。的一個(gè)特殊情形。對(duì)于給定的矩陣鏈A1A2..An，定義一個(gè)與之相應(yīng)的凸(n+1)P=<v0,v1,vn>，使得矩陣Ai與凸多邊形的邊vi-1vi一一對(duì)應(yīng)。若矩陣Ai的維數(shù)為pi-1×pi,i=1,2,…,n，則定義三角形vivjvk上的權(quán)函數(shù)值為：ω(△vivjvk)=pipjpkP語(yǔ)法樹(shù)給出矩陣鏈A1A2..An的最優(yōu)完全加括號(hào)方式。P=<v0,v1,…,vn>的一個(gè)最優(yōu)三角剖分Tv0vkvn，1≤k≤n-1，則T3v0vkvn的權(quán)，子多邊形<v0,v1vk>的權(quán)和<vk,vk+1vn>的權(quán)之和。可以斷言由T剖分也是最優(yōu)的，因?yàn)槿粲?lt;v0,v1,…,vk>或<vk,vk+1,…,vn>的更小權(quán)的三角剖分，將會(huì)導(dǎo)致T不是最優(yōu)三角剖分的。t[i,j]，1≤i<j≤n，為凸子多邊形<vi-1,vivj>的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)值，即最優(yōu)值。為方便起見(jiàn)，設(shè)的多邊形<Vi-1,vi>具0。據(jù)此定義，要計(jì)算的凸(n+1)Pt[i,j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。由于的2頂點(diǎn)多0，t[i,i]=0，i=1,2,…,n。當(dāng)ji≥11,vivj3,t[i,j]t[i,k]的值t[k+1,j]的值，再加上△vi-1vkvj的權(quán)值，并在i≤k≤j-1將(2.3)m[i,j]的(2.l)式要對(duì)計(jì)算m[i,j]的算法MATRIX_CHAIN_ORDER做很小的修改就完全適用于計(jì)算下面描述的計(jì)算凸(n+1)P=<v0,v1,vn>的三角剖分最優(yōu)權(quán)值的MINIMUM_WEIGHT_TRIANGULATION，輸入是凸多邊形P=<v0,v1,…,vnωt[i,j]和使得t[i,k]+t[k+1,j]+ω(△vi-1vkvj)達(dá)到最優(yōu)的位置(k=)s[i,j]，1≤i≤j≤nProceduren:=length[p]-fori:=1tondot[i,i]:=0;forll:=2tondofori:=1ton-ll+1doj:=i+ll-fork:=itoj-1doifq<t[i,j]thenMATRIX_CHAIN_ORDERMINIMUM_WEIGHT_TRIANGULATIONθ(n2)空間，耗時(shí)θ(n3)構(gòu)造最優(yōu)三角剖1≤i≤j≤n，算法MINIMUM_WEIGHT_TRIANGULATION<vi-1,vivj>的最優(yōu)t[i,j]s[i,j]中記錄了此最優(yōu)三角剖分中與邊(或弦)vi-1vj構(gòu)成的三角形的第三個(gè)頂點(diǎn)的位置。因此，利用最優(yōu)子結(jié)構(gòu)性s[i,j]，1≤i≤j≤n，凸(n+l)P=<v0,v1,…,vn>的最優(yōu)三角Ο(n)時(shí)間內(nèi)構(gòu)造出來(lái)。7計(jì)算PolygonisagameforoneyerthatstartsonapolygonwithNvertices,liketheoneinFigure1,whereN=4.Eachvertexislabelledwithanintegerandeachedgeislabelledwitheitherthesymbol+(addition)orthesymbol*(product).Theedgesarenumberedfrom1toN.Figure1.GraphicalrepresentationofaOnthefirstmove,oneoftheedgesisremoved.Subsequentmovesinvolvethefollowingsteps:pickanedgeEandthetwoverticesV_1andV_2thatarelinkedbyE;recethembyanewvertex,labelledwiththeresultofperformingtheoperationindicatedinEonthelabelsofV_1andV_2.Thegameendswhentherearenomoreedges,anditsscoreisthelabelofthesinglevertexremaining.SampleConsiderthepolygonofFigure1.Theyerstartedbyremoving3.TheeffectsaredepictedinFigureFigure2.RemovingedgeAfterthat,theyerpickededgeFigure3.PickingedgethenedgeFigure4.Pickingedgeand,finally,edge2.ThescoreisFigure5.PickingedgeWriteaprogramthat,givenapolygon,computesthehighestpossiblescoreandlistsalltheedgesthat,ifremovedonthefirstmove,canleadtoagamewiththatscore.InputFilePOLYGON.INdescribesapolygonwithNvertices.ItcontainstwoOnthefirstlineisthenumberThesecondlinecontainsthelabelsofedges1,...,N,interleavedwiththevertices'labels(firstthatofthevertexbetweenedges1and2,thenthatofthevertexbetweenedges2and3,andsoon,untilthatofthevertexbetweenedgesNand1),allseparatedbyonespace.Anedgelabeliseitherthelettert(representing+)ortheletterx(representing*).Sample4t-7t4x2xThisistheinputfileforthepolygonofFigure1.Thesecondlinestartswiththelabelofedge1.OutputOnthefirstlineoffilePOLYGON.OUTyourprogrammustwritethehighestscoreonecangetfortheinputpolygon.Onthesecondlineitmustwritethelistofalledgesthat,ifremovedonthefirstmove,canleadtoagamewiththatscore.Edgesmustbewritteninincreasingorder,separatedbyonespace.Sample1ThismustbetheoutputfileforthepolygonofFigure3<=N<=Foranysequenceofmoves,vertexlabelsareintherange[-參考解規(guī)劃的思想解決的。關(guān)鍵在于乘法運(yùn)算同號(hào)得正，異號(hào)得負(fù)，如果a,b都是負(fù)數(shù)，a*b以節(jié)點(diǎn)iLFmin(i,L)，最大值為Fmax(i,L)，i(imodn)+1的邊上的運(yùn)算符記為opr(i)，則可以得到以下遞歸：中(i+t)modn+1是節(jié)點(diǎn)it+1，V(i)為節(jié)點(diǎn)i，opr(i)i(imodn)+1的邊上的運(yùn)算符。根據(jù)這個(gè)，我們可以遞推求出所有的8問(wèn)題描述（英文原題2020"0"或"1"FONT.DAT27IMAGE.DAT至多有一行被(的行緊接其后字符圖像不會(huì)同時(shí)有一行被而同時(shí)又丟失一行，在測(cè)試數(shù)據(jù)中，任何一個(gè)字符圖像弄反"0"和"1"30%。在行被的情況中，行和被行都可能破損，但破損的情形可能是不用FONT.DAT提供的字體對(duì)IMAGE.DAT文件中的一個(gè)或者多個(gè)字符序列進(jìn)行識(shí)IMAGE.DAT兩個(gè)輸入文件都由整數(shù)N(19≤N≤1200)開(kāi)始，該整數(shù)下面的行數(shù)N(digit1)(digit2)(digit3)…(digit20)(digit1)(digit2)(digit3)……20文件FONT.DAT描述字體。FONT.DAT總是包含541行。每次FONT.DAT都可能是你的程序必須生成一個(gè)IMAGE.OUT文件。它應(yīng)該包含一串識(shí)別出的字符。它的格式是一行ASCII碼。輸出結(jié)果不應(yīng)含有任何分隔符，如果你的程序識(shí)別不出pletesampleshowingtheSampleIMAGE.DAT,beginningFigureFigure Recognisedesinglecharacter9問(wèn)題描y[1..n]X(delete)；被替換(rece)；或被到目標(biāo)串中去(copy)；字符也可操源copyacopyrecegbytdeletecopyinsertinsertinserttwiddleitintotiinsertkill要達(dá)到這個(gè)結(jié)果還可有其它一些操作序列。操作delete,rece，copy，insert，twiddlekillcost。例如cost(kill)=被刪除的串長(zhǎng)*cose(delete)-3*cost(copy)+cost(re=3*5+6+3+3*4+4+2*3-x[1..m],y[1..n]和一些操作代價(jià)集合，XYX轉(zhuǎn)化為Yx[1..m]至參考解我們按目標(biāo)串長(zhǎng)遞增的順序進(jìn)行變換：先變換Yn，再變換Yn-1YnY1Y2…Yn為止。C1——delete操作的代價(jià)；C2——rece操作的代價(jià)C3——copy操作的代價(jià) C4——insert操作的代價(jià)C5——twiddle；C6——kill*C1-c[i,j]——將Xj…Xm變換至Yi…Yndeleterece操作：源串中的Xj被替換到目標(biāo)串的Yi位置copyXj被拷貝到目標(biāo)串的Yi位置，使得insertYitwiddle操作：XjXj+1交換并到目標(biāo)串的YiYi+1位置，使得c[i,j]Xj…Xm與Yi…Yn中除參與變換的字符外的子串間的變換代價(jià)最小：即delete操作前Xj+1…Xm變換至Yi…Yn的代價(jià)和要最?。籸ece或copy操作前Xj+1…Xm變換至Yi+1…Yn的代價(jià)和最??；insert操作前Xj…Xm變換至Yi+1…Yn的代價(jià)和要最?。籺widdleXj+2…Xm變換至Yi+2…Yn的Xj…Xm至c[i,j]的遞歸式：2]+C5我們專(zhuān)門(mén)設(shè)置了一個(gè)表k[i,j]，以記下c[i,j]最小時(shí)的操作序號(hào)≤5)c[i,j]c[i,m+1]=(N-i+1)*C4；k[i,M+l]=4 (1≤i≤N)空時(shí)，要變換目標(biāo)串Yi…Yn必須進(jìn)行N-i+1insertkillkillXi…Xm(M-i+1delete1。3.c[n+1,m+1]=0；0c[i,j]c[i,j]最優(yōu)解的子問(wèn)題，包含了求c[i..n,j+1..M]c[i,j]的值最優(yōu)，必須保證這些子子問(wèn)題的值最優(yōu)，因此具有“最優(yōu)于結(jié)構(gòu)”和“子問(wèn)題”兩個(gè)要素，可用動(dòng)態(tài)規(guī)劃解決。我們從變換Yn字符出發(fā)，按目標(biāo)串長(zhǎng)度遞增的順序自下而上地依次計(jì)算c[n,1..m]→c[n-1,1..m]→…→c[1,1..m]，充分利用了子問(wèn)題，使得算法七、動(dòng)態(tài)規(guī)劃的技巧——階段的劃分和狀態(tài)的9]按照?qǐng)D中的虛線(xiàn)來(lái)劃分階段，即階段變量kxk表多段圖。用決策變量uk=0，uk=1row我們看到，這個(gè)狀態(tài)轉(zhuǎn)移方程需要根據(jù)k時(shí)，一般是不會(huì)這么做的，而代之以下面方法：（Distance目，而不存在明確的階段特征了。如果說(shuō)這種方法是以地圖中的行（A、B、C如果非得套用這種方法的話(huà)，則最優(yōu)指標(biāo)函數(shù)就需要有的下標(biāo)，并且難以處理兩條路徑"不能"的問(wèn)題。一維狀態(tài)變量就成了。即用xk=(ak,bkk置，相應(yīng)的，決策變量也增加一維，用uk=(xk,yk)分別表示兩條路徑的行走方10]LITTLESHOPOFFLOWERSYouwanttoarrangethewindowofyourflowershopinamostpleasantway.YouhaveFbunchesofflowers,eachbeingofadifferentkind,andatleastasmanyvasesorderedinarow.Thevasesaregluedontotheshelfandarenumberedconsecutively1throughV,whereVisthenumberofvases,fromlefttorightsothatthevase1istheleftmost,andthevaseVistherightmostvase.Thebunchesaremoveableandareuniquelyidentifiedbyintegersbetween1andF.Theseid-numbershaveasignificance:Theydeterminetherequiredorderofappearanceoftheflowerbunchesintherowofvasessothatthebunchimustbeinavasetotheleftofthevasecontainingbunchjwheneveri<j.Suppose,forexample,youhaveabunchofazaleas(id-number=1),abunchofbegonias(id-number=2)andabunchofcarnations(id-number=3).Now,allthebunchesmustbeputintothevaseskeetheirid-numbersinorder.Thebunchofazaleasmustbeinavasetotheleftofbegonias,andthebunchofbegoniasmustbeinavasetotheleftofcarnations.Iftherearemorevasesthanbunchesofflowersthentheexcesswillbeleftempty.Avasecanholdonlyonebunchofflowers.Eachvasehasadistinctcharacteristic(justlikeflowersdo).Hence,puttingabunchofflowersinavaseresultsinacertainaestheticvalue,expressedbyaninteger.Theaestheticvaluesarepresentedinatableasshownbelow.Leavingavaseemptyhasanaestheticvalueof0.VASE1234517--25-3-5--Accordingtothetable,azaleas,forexample,wouldlookgreatinvase2,buttheywouldlookawfulinvase4.Toachievethemostpleasanteffectyouhaveto izethesumofaestheticvaluesforthearrangementwhilekee therequiredorderingoftheflowers.Ifmorethanonearrangementhasthealsumvalue,anyoneofthemwillbeacceptable.Youhavetoproduceexactlyonearrangement.1<=F<=100whereFisthenumberofthebunchesofflowers.Thebunchesarenumbered1throughF.F<=V<=100whereVisthenumberof-50<=Aij<=50whereAijistheaestheticvalueobtainedbyputtingtheflowerbunchiintothevasej.TheinputisatextfilenamedThefirstlinecontainstwonumbers:F,ThefollowingFlines:EachoftheselinescontainsVintegers,sothatAisgivenasthejthnumberonthe(i+1)stlineoftheinputfile.Theoutputmustbeatextfilenamedflower.outconsistingoftwoThefirstlinewillcontainthesumofaestheticvaluesforyourarrangement.ThesecondlinemustpresentthearrangementasalistofFnumbers,sothatthek’thnumberonthislineidentifiesthevaseinwhichthebunchkisput.33723-5-24521-410-215-4-2024Yourprogramwillbeallowedtorun2Nopartialcreditcanbeobtainedforatest本題雖然是IOI’99動(dòng)態(tài)規(guī)劃呢？如何劃分階段，又如何選擇狀態(tài)呢？<方法以花束的編號(hào)來(lái)劃分階段。在這里，第kkFF+1F+1xk表示第k在的花瓶。而對(duì)于每一個(gè)狀態(tài)xk，決策ukk+1指標(biāo)函數(shù)fk(xkk束花到第nA(i,j)是花束ij,VF,<方法1xk+1≤uk≤V-(F-k)+1待改進(jìn)。還是以花束的編號(hào)來(lái)劃分階段，第kkxk表示第kF1uk表示第k-1標(biāo)fk(xkk；A(i,j)i花瓶j,VF可以看出，這種方法實(shí)質(zhì)上和方法1沒(méi)有區(qū)別，但是允許決策空間的表示變得<方法以花瓶的數(shù)目來(lái)劃分階段，第kkxk表示前kxk，決策就是第xk放在第kuk=10fk(xkkxk差不多的，但的時(shí)候，就像我們的例子一樣，兩種方在某個(gè)方面有些區(qū)別。所以，在用動(dòng)態(tài)規(guī)劃解題的時(shí)候，可以多想是否有其它的解法。對(duì)各種不同算法的比較中，我們可以更深刻地動(dòng)態(tài)規(guī)劃的構(gòu)思技巧。八、動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)中的問(wèn)能性不大，而相反地，動(dòng)態(tài)規(guī)劃需要很大的空間以中間產(chǎn)生的結(jié)果，這樣優(yōu)越性，但這是以犧牲空間為代價(jià)的，為了有效地已有結(jié)果，數(shù)據(jù)也不易壓縮，因而空間是比較突出的。另一方面，動(dòng)態(tài)規(guī)劃的高時(shí)效性往往一個(gè)思考方向是盡可能少占用空間。如從結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)上考慮，僅僅必不可少的內(nèi)容，以及數(shù)據(jù)范圍上精打細(xì)算(按位、壓縮等)。當(dāng)然方法是用一個(gè)與結(jié)點(diǎn)數(shù)一樣多的數(shù)組來(lái)每一步的決策，這對(duì)于倒推求得一空間緊張的情況下，我們就應(yīng)該抓住問(wèn)題的主要。省去這個(gè)決策的數(shù)用，如果能有效地使用這一，對(duì)于相當(dāng)大規(guī)模的問(wèn)題，空間也不至于溢出（為了求出最優(yōu)方案，保留每一步的決策仍是必要的，這同樣需要空間）Data1Data2Data1Data2后，將Data2通過(guò)覆蓋到Data1之上，如此反復(fù)，即可推得最終結(jié)果。這比較麻煩；而且，每遞推一級(jí)，就需要很多的內(nèi)容，與前面多個(gè)階段相關(guān)NData[0..N]，N這種內(nèi)存節(jié)約方式時(shí)對(duì)于階段k的只要對(duì)應(yīng)成對(duì)數(shù)組Data中下標(biāo)為k(N+1)的單元的就可以了。這種處理方法對(duì)于程序修改的代碼很少，速度幾內(nèi)存而進(jìn)行交換時(shí)，可以只對(duì)指針進(jìn)行交換，而不數(shù)據(jù)，這在實(shí)踐中也是九、動(dòng)態(tài)規(guī)劃與其他算法的比動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)動(dòng)態(tài)規(guī)劃可以看作求決策u1,u2,...,un，使指標(biāo)函數(shù)V1n(xl,u1,u2,...,un)達(dá)到最11]其中g(shù)k(uk解：按變量uk的序號(hào)knx1,x2,..xn，取問(wèn)題中的變量u1,u2,..,un為決策；狀態(tài)轉(zhuǎn)移方程為：取gk(uk12]Themorepointsstudentsscoreinourcontests,thehappierwehereattheUSACOare.Wetrytodesignourcontestssothatpeoplecanscoreasmanypointsaspossible,andwouldlikeyourassistance.Wehaveseveralcategoriesfromwhichproblemscanbechosen,wherea"category"isanunlimitedsetofcontestproblemswhichallrequirethesameamountoftimetosolveanddeservethesamenumberofpointsforacorrectsolution.YourtaskiswriteaprogramwhichlstheUSACOstaffhowmanyproblemsfromeachcategorytoincludeinacontestsoasto izethetotalnumberofpointsinthechosenproblemswhilekeethetotalsolutiontimewithinthelengthofthecontest.Theinputincludesthelengthofthecontest,M(1<=M<=10,000)(don'tworry,youwon'thavetocompeteinthelongercontestsuntiltrainingcamp)andN,thenumberofproblemcategories,where1<=<=EachofthesubsequentNlinescontainstwointegersdescribingacategory:thefirstintegerlsthenumberofpointsaproblemfromthatcategoryisworth(1<=points<=10000);thesecondlsthenumberofminutesaproblemfromthatcategorytakestosolve(1<=minutes<=10000).Yourprogramshoulddeterminethenumberofproblemsweshouldtakefromeachcategorytomakethehighest-scoringcontestsolvablewithinthelengthofthecontest.Remember,thenumberfromanycategorycanbeanynonnegativeinteger(0,one,ormany).Calculatetheumnumberofpossiblepoints.PROGRAMNAME:inflateINPUTFORMATLine1:M,N--contestminutesandnumberofproblemLines2-N+1:Twointegers:thepointsandminutesforeachSAMPLEINPUT(file435OUTPUTAsinglelinewiththeumnumberofpointspossiblegiventheSAMPLEOUTPUT(fileinflate.out)11k用數(shù)值方法求解時(shí)存在維數(shù)災(zāi)(curseofdimensionality)。若一維狀態(tài)變量有m個(gè)取值，那么對(duì)于n維問(wèn)題，狀態(tài)x就有mn個(gè)值，對(duì)于每個(gè)狀態(tài)值都要計(jì)算、函數(shù)fk(xk)，對(duì)于n稍大(即使n=3)的實(shí)際問(wèn)題的計(jì)k動(dòng)態(tài)規(guī)劃與遞推——?jiǎng)討B(tài)規(guī)劃是最優(yōu)化算[例 模四最優(yōu)路徑問(wèn)14mod4這個(gè)圖是一個(gè)多，而且是一個(gè)特殊的多。雖然這個(gè)圖的形式比一般的多要簡(jiǎn)單，但是這個(gè)最優(yōu)路徑問(wèn)題卻不能用動(dòng)態(tài)規(guī)劃來(lái)做。因?yàn)橐粭l從第1點(diǎn)到第4點(diǎn)的最優(yōu)路徑，在它走23點(diǎn)時(shí)，路徑長(zhǎng)度mod4的余1點(diǎn)的長(zhǎng)度mod4為sk的路徑是否存在，用fk(sk)來(lái)表示，則遞推如下：這里lenk,i表示從第k-1點(diǎn)到第k點(diǎn)之間的第i條邊的長(zhǎng)度，方括號(hào)表示“或(or)”運(yùn)算。最后的結(jié)果就是可以使f4(s4s4值。這個(gè)遞推法的遞推和動(dòng)態(tài)規(guī)劃的規(guī)劃方程非常相似，我們?cè)谶@里借用了動(dòng)14]n(n+1)/2(n+1)（n=5a）d，每個(gè)格子的寬度也都等于d，且除了最左端和最右端的格子外每個(gè)格子都正對(duì)著最下面一排讓一個(gè)直徑略小于d碰到一個(gè)釘子都可能落向左邊或右邊（1/2），且球的中心還會(huì)正對(duì)著下一顆將要碰上的釘子。例如圖b我們知道小球落在第i其中i0,1,...,n現(xiàn)在的問(wèn)題是計(jì)算拔掉某些釘子后，小球落在編號(hào)為mpm3路徑。圖 圖 圖1n（2<=n<=50）m（0<=m<=n）以下nn*在，‘.’表示釘子被拔去，注意在這n僅一行，是一個(gè)既約分?jǐn)?shù)(00/1)，mpm既約分?jǐn)?shù)的定義：A/BA、BAB5*.**.******15]數(shù)字三角形7 作為狀態(tài)，決策就是向左下走（0）或向右下走（1）。fk(xk)表示，那么遞推就是：在這里，雖然求和只有兩項(xiàng)，但我們?nèi)匀挥谩频男问奖硎?，就是為了突出這個(gè)遞推和上面的規(guī)劃方程的相似之處。這兩個(gè)的邊界條件都是一模用上面的思想，用fk(xk)表示小球落到第k行第xk個(gè)釘子上的概率，則遞推公這里函數(shù)Existk(xk)表示第k行第xk個(gè)釘子是否存在，存在則取1，不存在則0；可以看出這個(gè)較之上面的兩個(gè)式子雖然略有變化，但是其基本思想還是類(lèi)動(dòng)態(tài)規(guī)劃與搜索——?jiǎng)討B(tài)規(guī)劃是高效率、高消費(fèi)算圖(b)C2C2為得不采用搜索算法。