第四章 動(dòng)態(tài)規(guī)劃-old

計(jì)算機(jī)算法設(shè)計(jì)與分析NorthChinaElectricPowerUniversityComputerAlgorithmsDesign&Analysis華北電力大學(xué)計(jì)算機(jī)科學(xué)與工程系Dept.ofComputerScience&EngineeringofNorthChinaElectricPowerUniversity第四章動(dòng)態(tài)規(guī)劃法NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity§1引言最短路徑問題：

現(xiàn)有一張地圖，各結(jié)點(diǎn)代表城市，兩結(jié)點(diǎn)間連線代表道路，線上數(shù)字表示城市間的距離。如圖所示，試找出從結(jié)點(diǎn)A到結(jié)點(diǎn)E的最短距離?？梢杂盟阉鞣▉?lái)解決此問題，該問題的遞歸式為其中

是與v相鄰的節(jié)點(diǎn)的集合，w(v,u)表示從v到u的邊的長(zhǎng)度。NorthChinaElectricPowerUniversityintMinDistance(intv){if(v==E)return0else{min=maxint;for所有沒有訪問過的節(jié)點(diǎn)i{ifv和i相鄰{標(biāo)記i訪問過了;t=v到i的距離+MinDistance(i);標(biāo)記i未訪問過;if(t<min)min=t;}}}}

開始時(shí)標(biāo)記所有的頂點(diǎn)未訪問過，MinDistance(A)就是從A到E的最短距離?？梢钥吹?，每次除了已經(jīng)訪問過的城市外，其他城市都要訪問，所以時(shí)間復(fù)雜度為O(n!)，這是一個(gè)“指數(shù)級(jí)”的算法。NorthChinaElectricPowerUniversity觀察一下這個(gè)算法。在求從B1到E的最短距離的時(shí)候，先求出從C2到E的最短距離；而在求從B2到E的最短距離的時(shí)候，又求了一遍從C2到E的最短距離。也就是說，從C2到E的最短距離我們求了兩遍。同樣可以發(fā)現(xiàn)，在求從C1、C2到E的最短距離的過程中，從D1到E的最短距離也被求了兩遍。而在整個(gè)程序中，從D1到E的最短距離被求了四遍。如果在求解的過程中，同時(shí)將求得的最短距離"記錄在案"，隨時(shí)調(diào)用，就可以避免這種情況。于是，可以改進(jìn)該算法，將每次求出的從v到E的最短距離記錄下來(lái)，在算法中遞歸地求MinDistance(v)時(shí)先檢查以前是否已經(jīng)求過了MinDistance(v)，如果求過了則不用重新求一遍，只要查找以前的記錄就可以了。這樣，由于所有的點(diǎn)有n個(gè)，因此不同的狀態(tài)數(shù)目有n個(gè)，該算法的數(shù)量級(jí)為O(n)。更進(jìn)一步，可以將這種遞歸改為遞推，這樣可以減少遞歸調(diào)用的開銷。NorthChinaElectricPowerUniversity可以發(fā)現(xiàn)，A只和Bi相鄰，Bi只和Ci相鄰,...，依此類推。這樣，可以將原問題的解決過程劃分為4個(gè)階段，設(shè)S1={A},S2={B1,B2},S3={C1,C2,C3,C4},S4={D1,D2,D3}，F(xiàn)k(u)表示從Sk中的點(diǎn)u到E的最短距離，則并且有邊界條件：

顯然可以遞推地求出F1(A)，也就是從A到E的最短距離。這種算法的復(fù)雜度為O(n)，因?yàn)樗械臓顟B(tài)總數(shù)（結(jié)點(diǎn)總數(shù)）為n，對(duì)每個(gè)狀態(tài)都只要遍歷一次，而且程序很簡(jiǎn)潔。NorthChinaElectricPowerUniversity動(dòng)態(tài)規(guī)劃算法描述如下：voidDynamicProgramming(){F5[E]:=0;for(i=4;i>0;i--){foreachu∈Sk{Fk[u]:=maxint;foreachv∈Sk+1∩δ(u)ifFk[u]>w(u,v)+Fk+1[v]Fk[u]:=w(u,v)+Fk+1[v];}}輸出F1[A];}其中，δ(u)表示和u鄰接的頂點(diǎn)的集合。這種高效算法，就是動(dòng)態(tài)規(guī)劃算法。NorthChinaElectricPowerUniversity§2動(dòng)態(tài)規(guī)劃的基本概念

動(dòng)態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。1957年出版了他的名著DynamicProgramming，這是該領(lǐng)域的第一本著作。多階段決策問題多階段決策過程，是指這樣的一類特殊的活動(dòng)過程，問題可以按時(shí)間順序分解成若干相互聯(lián)系的階段，在每一個(gè)階段都要做出決策，全部過程的決策是一個(gè)決策序列。要使整個(gè)活動(dòng)的總體效果達(dá)到最優(yōu)的問題，稱為多階段決策問題。NorthChinaElectricPowerUniversity動(dòng)態(tài)規(guī)劃模型的基本要素1.階段階段(step)是對(duì)整個(gè)過程的自然劃分。通常根據(jù)時(shí)間順序或空間特征來(lái)劃分階段，以便按階段的次序解優(yōu)化問題。階段變量一般用k=1,2,..,n表示。2.狀態(tài)狀態(tài)(state)表示每個(gè)階段開始時(shí)過程所處的自然狀況。它應(yīng)該能夠描述過程的特征并且具有無(wú)后向性，即當(dāng)某階段的狀態(tài)給定時(shí)，這個(gè)階段以后過程的演變與該階段以前各階段的狀態(tài)無(wú)關(guān)，即每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié)。通常還要求狀態(tài)是直接或間接可以觀測(cè)的。描述狀態(tài)的變量稱狀態(tài)變量(statevariable)。變量允許取值的范圍稱允許狀態(tài)集合(setofadmissiblestates)。用xk表示第k階段的狀態(tài)變量，它可以是一個(gè)數(shù)或一個(gè)向量。用Xk表示第k階段的允許狀態(tài)集合。在引言的例子中x2可取B1，B2，X2={B1,B2}。n個(gè)階段的決策過程有n+1個(gè)狀態(tài)變量，xn+1表示xn演變的結(jié)果，在引言的例子中x5取E。NorthChinaElectricPowerUniversity3.決策當(dāng)一個(gè)階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個(gè)狀態(tài)，這種選擇手段稱為決策(decision)。描述決策的變量稱決策變量(decisionvariable)。變量允許取值的范圍稱允許決策集合(setofadmissibledecisions)。用uk(xk)表示第k階段處于狀態(tài)xk時(shí)的決策變量，它是xk的函數(shù)，用Uk(xk)表示了xk的允許決策集合。在引言的例子中u2(B1)可取C1,C2,C3。決策變量簡(jiǎn)稱決策。4.策略決策組成的序列稱為策略(policy)。由初始狀態(tài)x1開始的全過程的策略記作p1n(x1)，即p1n(x1)={u1(x1),u2(x2),...，un(xn)}。由第k階段的狀態(tài)xk開始到終止?fàn)顟B(tài)的后部子過程的策略記作pkn(xk)，即pkn(xk)={uk(xk),uk+1(xk+1),...，un(xn)}。類似地，由第k到第j階段的子過程的策略記作pkj(xk)={uk(xk),uk+1(xk+1),...，uj(xj)}。對(duì)于每一個(gè)階段k的某一給定的狀態(tài)xk，可供選擇的策略pkj(xk)有一定的范圍，稱為允許策略集合(setofadmissiblepolicies)，用P1n(x1),Pkn(xk),Pkj(xk)表示。NorthChinaElectricPowerUniversity5.狀態(tài)轉(zhuǎn)移方程在確定性過程中，一旦某階段的狀態(tài)和決策為已知，下階段的狀態(tài)便完全確定。用狀態(tài)轉(zhuǎn)移方程(equationofstate)表示這種演變規(guī)律，寫作：引言中例子的狀態(tài)轉(zhuǎn)移方程為：xk+1=uk(xk)6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)(objectivefunction)是衡量過程優(yōu)劣的數(shù)量指標(biāo)，它是關(guān)于策略的數(shù)量函數(shù)，從階段k到階段n的指標(biāo)函數(shù)用Vkn(xk,pkn(xk))表示，k=1,2,...,n。能夠用動(dòng)態(tài)規(guī)劃解決的問題的指標(biāo)函數(shù)應(yīng)具有可分離性，即Vkn可表為xk,uk,Vk+1n的函數(shù)，記為：例：某工廠擬在今后三年內(nèi)購(gòu)買某種設(shè)備5臺(tái)，考慮到設(shè)備維護(hù)、現(xiàn)金貼現(xiàn)等各種因素后，預(yù)計(jì)在第一、第二、第三年初購(gòu)買該設(shè)備可獲純利潤(rùn)如下表所示。問如何指定購(gòu)買計(jì)劃才能使該廠獲得最大利潤(rùn)。純利與購(gòu)買設(shè)備時(shí)間、臺(tái)數(shù)的關(guān)系萬(wàn)元設(shè)

備

臺(tái)

數(shù)

012345設(shè)備

購(gòu)買

時(shí)

間

第一年初

第二年初

第三年初

037912130510111111046111212解：為應(yīng)用動(dòng)態(tài)規(guī)劃方法求解，先應(yīng)明確一下問題：1)以購(gòu)買設(shè)備時(shí)間為順序，將問題劃分成3個(gè)階段；2)引進(jìn)4個(gè)狀態(tài)變量x1,x2,x3,x4，其中，xk(k=1,2,3,4)表示第k年初至第三年末可購(gòu)買的設(shè)備臺(tái)數(shù)，并且規(guī)定上一年末與下一年初為同一時(shí)刻；NorthChinaElectricPowerUniversity3)決策變量yk表示第k年初購(gòu)買設(shè)備臺(tái)數(shù)；4)狀態(tài)轉(zhuǎn)移方稱為xk+1=xk-yk;5)階段指標(biāo)Pk(yk)表示第k年購(gòu)買yk臺(tái)設(shè)備所獲純利潤(rùn)；最優(yōu)指標(biāo)函數(shù)fk(xk)表示第k年初至第三年末購(gòu)買xk臺(tái)設(shè)備所能獲得的最大利潤(rùn);6)由以上所設(shè)可得本題的動(dòng)態(tài)規(guī)劃的基本方程為：由上式可得k=2時(shí)，對(duì)應(yīng)x2=0、1、2、3、4、5可分別計(jì)算如下：NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity§4動(dòng)態(tài)規(guī)劃的適用條件1.最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）

一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

例如上圖中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。這可用反證法證明：假設(shè)有另一路徑J'是B到C的最優(yōu)路徑，則A到C的路線取I和J'比I和J更優(yōu)，矛盾。從而證明J'必是B到C的最優(yōu)路徑。NorthChinaElectricPowerUniversity

最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算。動(dòng)態(tài)規(guī)劃的最優(yōu)化理在其指標(biāo)函數(shù)的可分離性和單調(diào)性中得到體現(xiàn)。根據(jù)最優(yōu)化原理導(dǎo)出的動(dòng)態(tài)規(guī)劃基本方程是解決一切動(dòng)態(tài)規(guī)劃問題的基本方法。2.無(wú)后向性將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)，它以前各階段的狀態(tài)無(wú)法直接影響它未來(lái)的決策，而只能通過當(dāng)前的這個(gè)狀態(tài)。換句話說，每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié)。這就是無(wú)后向性，又稱為無(wú)后效性。如果用前面的記號(hào)來(lái)描述無(wú)后向性，就是：對(duì)于確定的xk，無(wú)論p1,k-1如何，最優(yōu)子策略pkn*是唯一確定的，這種性質(zhì)稱為無(wú)后向性。NorthChinaElectricPowerUniversity3.子問題的重疊性

在引言的例子中我們看到，動(dòng)態(tài)規(guī)劃將原來(lái)具有指數(shù)級(jí)復(fù)雜度的搜索算法改進(jìn)成了具有多項(xiàng)式時(shí)間的算法。其中的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。

設(shè)原問題的規(guī)模為n，容易看出，當(dāng)子問題樹中的子問題總數(shù)是n的超多項(xiàng)式函數(shù)，而不同的子問題數(shù)只是n的多項(xiàng)式函數(shù)時(shí)，動(dòng)態(tài)規(guī)劃法顯得特別有意義，此時(shí)動(dòng)態(tài)規(guī)劃法具有線性時(shí)間復(fù)雜性。所以，能夠用動(dòng)態(tài)規(guī)劃解決的問題還有一個(gè)顯著特征：子問題的重疊性。這個(gè)性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無(wú)法滿足，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)。NorthChinaElectricPowerUniversity§5動(dòng)態(tài)規(guī)劃的基本思想

前文主要介紹了動(dòng)態(tài)規(guī)劃的一些理論依據(jù)，我們將前文所說的具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的動(dòng)態(tài)規(guī)劃稱為標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃，這種標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃是在研究多階段決策問題時(shí)推導(dǎo)出來(lái)的，具有嚴(yán)格的數(shù)學(xué)形式，適合用于理論上的分析。在實(shí)際應(yīng)用中，許多問題的階段劃分并不明顯，這時(shí)如果刻意地劃分階段法反而麻煩。一般來(lái)說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解(即滿足最優(yōu)子化原理)，則可以考慮用動(dòng)態(tài)規(guī)劃解決。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲(chǔ)子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。NorthChinaElectricPowerUniversity

因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問題，只在第一次遇到時(shí)加以求解，并把答案保存起來(lái)，讓以后再遇到時(shí)直接引用，不必重新求解?！?動(dòng)態(tài)規(guī)劃算法的基本步驟

設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法，通?？砂匆韵聨讉€(gè)步驟進(jìn)行：劃分階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。注意這若干個(gè)階段一定要是有序的或者是可排序的（即無(wú)后向性），否則問題就無(wú)法用動(dòng)態(tài)規(guī)劃求解。2.選擇狀態(tài)：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿足無(wú)后效性。NorthChinaElectricPowerUniversity

3.確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來(lái)了。但事實(shí)上，我們常常是反過來(lái)做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來(lái)確定決策。

4.寫出規(guī)劃方程（包括邊界條件）：動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。一般說來(lái)，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡(jiǎn)單的。

動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。根據(jù)動(dòng)態(tài)規(guī)劃的基本方程可以直接遞歸計(jì)算最優(yōu)值，但是一般將其改為遞推計(jì)算.NorthChinaElectricPowerUniversity

但是，實(shí)際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計(jì)動(dòng)態(tài)規(guī)劃，而是按以下幾個(gè)步驟進(jìn)行：分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。

步驟(1)--(3)是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟(4)可以省略，若需要求出問題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟(4)。此時(shí)，在步驟(3)中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟(4)中，根據(jù)所記錄的信息，快速地構(gòu)造出一個(gè)最優(yōu)解。NorthChinaElectricPowerUniversity§7動(dòng)態(tài)規(guī)劃實(shí)例分析1)矩陣連乘問題問題描述給定n個(gè)矩陣{A1,A2,….An}，其中Ai與Ai+1是可乘的，我們要計(jì)算這n個(gè)矩陣的連乘積。連乘積的計(jì)算次序不同，計(jì)算連乘積的計(jì)算量也不同。NorthChinaElectricPowerUniversity§7動(dòng)態(tài)規(guī)劃實(shí)例分析1)矩陣連乘問題兩個(gè)矩陣標(biāo)準(zhǔn)乘法：ra,ca和rb,cb分別表示矩陣A和B的行數(shù)和列數(shù)。voidmatrixMultiply(int**a,int**b,int**c,intra,intca,intrb,intcb){if(ca!=rb)error(“矩陣不可乘”)for(inti=0;i<ra;i++)for(intj=0;j<cb;j++){intsum=a[i][0]*b[0][j];for(intk=1;k<ca;k++)sum+=a[i][k]*b[k][j];c[i][j]=sum;}}NorthChinaElectricPowerUniversity§7動(dòng)態(tài)規(guī)劃實(shí)例分析1)矩陣連乘問題矩陣計(jì)算次序不同，對(duì)計(jì)算量有很大影響，如何計(jì)算才能確定一種最好的計(jì)算次序，使得最后的計(jì)算量最??？即矩陣連乘積的最優(yōu)計(jì)算次序問題。方法1窮舉搜索法找出所有可能的計(jì)算次序。然后計(jì)算出相應(yīng)的乘法次數(shù)。這是不現(xiàn)實(shí)的！計(jì)算量太大，算法復(fù)雜性為指數(shù)級(jí)別。方法2動(dòng)態(tài)規(guī)劃法求解1、分析最優(yōu)解的結(jié)構(gòu)（問題是否具有最優(yōu)子結(jié)構(gòu)）A[i：j]表示矩陣AiAi+1….Aj原問題變?yōu)榍驛[1:n]的一個(gè)最優(yōu)次序。矩陣Ai的維數(shù)為pi-1PiNorthChinaElectricPowerUniversity§7動(dòng)態(tài)規(guī)劃實(shí)例分析1)矩陣連乘問題2、建立遞歸關(guān)系設(shè)計(jì)算A[i][j]所需的最少乘法次數(shù)為m[i][j]，原問題最優(yōu)解為m[1][n]。下面對(duì)m[i][j]分析：當(dāng)i==j時(shí)A[i][j]為一個(gè)單個(gè)矩陣，無(wú)需計(jì)算當(dāng)i<j時(shí)，假設(shè)最優(yōu)次序是在Ak和Ak+1之間斷開則m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj如何確定K的值呢？NorthChinaElectricPowerUniversity§7動(dòng)態(tài)規(guī)劃實(shí)例分析1)矩陣連乘問題3、計(jì)算最優(yōu)值上述公式是一個(gè)遞歸公式，顯然我們可以設(shè)計(jì)一個(gè)遞歸算法來(lái)計(jì)算m[1][n]，然而我們也會(huì)注意到問題的重復(fù)計(jì)算。我們可以由低向上來(lái)計(jì)算，在計(jì)算過程中，保存已經(jīng)解決的子問題答案，每個(gè)子問題只計(jì)算一次，再后面計(jì)算時(shí)，只需要簡(jiǎn)單查一下即可。下面給出具體算法：輸入?yún)?shù){p0,p1,p2,….pn}存儲(chǔ)在數(shù)組p中，S數(shù)組存儲(chǔ)最優(yōu)斷開位置k的值。NorthChinaElectricPowerUniversity§7動(dòng)態(tài)規(guī)劃實(shí)例分析1)矩陣連乘問題3、計(jì)算最優(yōu)值VoidMatrixChain(int*p,intn,int**m,int**s){for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)//r為問題規(guī)模for(inti=1;i<=n-r+1;r++)//規(guī)模為r的子問題個(gè)數(shù){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}

}NorthChinaElectricPowerUniversity§7動(dòng)態(tài)規(guī)劃實(shí)例分析1)矩陣連乘問題4、構(gòu)造最優(yōu)解上述算法只是給出了一個(gè)最優(yōu)值,并沒有給出最優(yōu)解.我們知道了所需要的最少乘法次數(shù),但并不知道應(yīng)該如何做才能達(dá)到這個(gè)效果.我們?cè)跇?gòu)造最優(yōu)值的同時(shí),把最優(yōu)斷開位置k保存在數(shù)組s[][]中，我們可以利用它來(lái)構(gòu)造最優(yōu)解。我們可以利用類似于二叉樹的后序遍歷算法來(lái)實(shí)現(xiàn)。voidTraceback(inti,intj,int**s){if(i==j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<s[i][j];}NorthChinaElectricPowerUniversity動(dòng)態(tài)規(guī)劃法基本要素：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ī)劃法每個(gè)子問題只解一次。動(dòng)態(tài)規(guī)劃將原來(lái)具有指數(shù)級(jí)復(fù)雜度的搜索算法改進(jìn)成了具有多項(xiàng)式時(shí)間的算法。其中的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。

NorthChinaElectricPowerUniversity

設(shè)原問題的規(guī)模為n，容易看出，當(dāng)子問題樹中的子問題總數(shù)是n的超多項(xiàng)式函數(shù)，而不同的子問題數(shù)只是n的多項(xiàng)式函數(shù)時(shí)，動(dòng)態(tài)規(guī)劃法顯得特別有意義，此時(shí)動(dòng)態(tài)規(guī)劃法具有線性時(shí)間復(fù)雜性。所以，能夠用動(dòng)態(tài)規(guī)劃解決的問題還有一個(gè)顯著特征：子問題的重疊性。這個(gè)性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無(wú)法滿足，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)?？纯从闷胀ㄟf歸算法解矩陣連乘積最優(yōu)計(jì)算次序問題。NorthChinaElectricPowerUniversityIntRecurMatrixChain(inti,intj){if(i==j)return0;intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}returnu;}

NorthChinaElectricPowerUniversity§7動(dòng)態(tài)規(guī)劃實(shí)例分析3、備忘錄方法備忘錄方法是動(dòng)態(tài)規(guī)劃法的一個(gè)變形。備忘錄方法往往用一個(gè)表格或者數(shù)組把已經(jīng)解決的子問題保存起來(lái)，下次解時(shí)，察看該子問題的解，而不必計(jì)算，備忘錄方法采用的是由頂向下的方式，動(dòng)態(tài)規(guī)劃法采用的是由低向上的方式，備忘錄方法的控制結(jié)構(gòu)與遞歸算法相同。區(qū)別僅在于在遞歸解決之前先看看問題是否已經(jīng)解決。初始時(shí)，我們可以為每一個(gè)子問題建立一個(gè)記錄項(xiàng)，存入一個(gè)特殊值，表示子問題尚未解決。求解過程中，看該記錄項(xiàng)是否為特殊值，如果是，則該子問題第一次求解，解決并保存，反之，則說明已經(jīng)解決過，可以直接使用。intMemorizedMatrixChain(intn,int**m,int**s){for(inti=1;i<=n;i++)for(intj=i;j<=n;j++)m[i][j]=0returnLookupChain(1,n);}

NorthChinaElectricPowerUniversity§7動(dòng)態(tài)規(guī)劃實(shí)例分析3、備忘錄方法

IntLookupChain(inti,intj){if(m[i][j]>0)returnm[i][j]if(i==j)return0;intu=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;returnu;}

NorthChinaElectricPowerUniversity§7動(dòng)態(tài)規(guī)劃實(shí)例分析1)生產(chǎn)計(jì)劃問題問題描述工廠生產(chǎn)某種產(chǎn)品，每單位(千件)的成本為1(千元)，每次開工的固定成本為3(千元)，工廠每季度的最大生產(chǎn)能力為6(千件)。經(jīng)調(diào)查，市場(chǎng)對(duì)該產(chǎn)品的需求量第一、二、三、四季度分別為2，3，2，4(千件)。如果工廠在第一、二季度將全年的需求都生產(chǎn)出來(lái)，自然可以降低成本(少付固定成本費(fèi))，但是對(duì)于第三、四季度才能上市的產(chǎn)品需付存儲(chǔ)費(fèi)，每季每千件的存儲(chǔ)費(fèi)為0.5(千元)。還規(guī)定年初和年末這種產(chǎn)品均無(wú)庫(kù)存。試制訂一個(gè)生產(chǎn)計(jì)劃，即安排每個(gè)季度的產(chǎn)量，使一年的總費(fèi)用(生產(chǎn)成本和存儲(chǔ)費(fèi))最少。NorthChinaElectricPowerUniversity

這是一個(gè)明顯的多階段問題，我們按照計(jì)劃時(shí)間自然劃分階段，狀態(tài)定義為每階段開始時(shí)的存儲(chǔ)量xk，決策為每個(gè)階段的產(chǎn)量uk，記每個(gè)階段的需求量（已知）為dk，則狀態(tài)轉(zhuǎn)移方程為：

設(shè)每個(gè)階段開工固定成本費(fèi)用為a，生產(chǎn)單位數(shù)量產(chǎn)品的成本為b，每階段單位數(shù)量產(chǎn)品的存儲(chǔ)費(fèi)用為ｃ，階段指標(biāo)為階段的生產(chǎn)成本費(fèi)用和存儲(chǔ)費(fèi)用之和，即：

指標(biāo)函數(shù)Vkn為vk之和，最優(yōu)值函數(shù)fk(xk)為從第k階段的狀態(tài)xk出發(fā)到過程終結(jié)的最小費(fèi)用，滿足NorthChinaElectricPowerUniversity

其中允許決策集合Uk由每階段的最大生產(chǎn)能力決定，設(shè)過程終結(jié)時(shí)允許存儲(chǔ)量為x0n+1，則終端條件為：§8最長(zhǎng)公共子序列問題描述：一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=<x1,x2,…,xm>，則另一序列Z=<z1,z2,…,zk>是X的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列<i1,i2,…,ik>，使得對(duì)于所有j=1,2,…,k有

例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列，相應(yīng)的遞增下標(biāo)序列為<2,3,5,7>。給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。例如，若X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>，則序列<B,C,A>是X和Y的一個(gè)公共子序列，序列<B,C,B,A>也是X和Y的一個(gè)公共子序列。而且，后者是X和Y的一個(gè)最長(zhǎng)公共子序列，因?yàn)閄和Y沒有長(zhǎng)度大于4的公共子序列。NorthChinaElectricPowerUniversity最長(zhǎng)公共子序列(LCS)問題：給定兩個(gè)序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>，要求找出X和Y的一個(gè)最長(zhǎng)公共子序列。1.最長(zhǎng)公共子序列的結(jié)構(gòu)

解最長(zhǎng)公共子序列問題時(shí)最容易想到的算法是窮舉搜索法，即對(duì)X的每一個(gè)子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并且在檢查過程中選出最長(zhǎng)的公共子序列。X的所有子序列都檢查過后即可求出X和Y的最長(zhǎng)公共子序列。X的一個(gè)子序列相應(yīng)于下標(biāo)序列{1,2,…,m}的一個(gè)子序列，因此，X共有2m個(gè)不同子序列，從而窮舉搜索法需要指數(shù)時(shí)間。事實(shí)上，最長(zhǎng)公共子序列問題也有最優(yōu)子結(jié)構(gòu)性質(zhì)。NorthChinaElectricPowerUniversity定理:LCS的最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的一個(gè)最長(zhǎng)公共子序列Z=<z1,z2,…,zk>，則：若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列；2.若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長(zhǎng)公共子序列；3.若xm≠yn且zk≠yn，則Z是X和Yn-1的最長(zhǎng)公共子序列。其中Xm-1=<x1,x2,…,xm-1>，Yn-1=<y1,y2,…,yn-1>，Zk-1=<z1,z2,…,zk-1>。證明:用反證法。若zk≠xm，則<z1,z2,…,zk,xm>是X和Y的長(zhǎng)度為k十1的公共子序列。這與Z是X和Y的一個(gè)最長(zhǎng)公共子序列矛盾。因此，必有zk=xm=yn。由此可知Zk-1是Xm-1和Yn-1的一個(gè)長(zhǎng)度為k-1的公共子序列。若Xm-1和Yn-1有一個(gè)長(zhǎng)度大于k-1的公共子序列W，則將xm加在其尾部將產(chǎn)生X和Y的一個(gè)長(zhǎng)度大于k的公共子序列。此為矛盾。故Zk-1是Xm-1和Yn-1的一個(gè)最長(zhǎng)公共子序列。NorthChinaElectricPowerUniversity2.由于zk≠xm，Z是Xm-1和Y的一個(gè)公共子序列。若Xm-1和Y有一個(gè)長(zhǎng)度大于k的公共子序列W，則W也是X和Y的一個(gè)長(zhǎng)度大于k的公共子序列。這與Z是X和Y的一個(gè)最長(zhǎng)公共子序列矛盾。由此即知Z是Xm-1和Y的一個(gè)最長(zhǎng)公共子序列。3.與2.類似。這個(gè)定理告訴我們，兩個(gè)序列的最長(zhǎng)公共子序列包含了這兩個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2.子問題的遞歸結(jié)構(gòu)由最長(zhǎng)公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的最長(zhǎng)公共子序列，可按以下方式遞歸地進(jìn)行：當(dāng)xm=yn時(shí)，找出Xm-1和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個(gè)最長(zhǎng)公共子序列。當(dāng)xm≠yn時(shí)，必須解兩個(gè)子問題，即找出Xm-1和Y的一個(gè)最長(zhǎng)公共子序列及X和Yn-1的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者即為X和Y的一個(gè)最長(zhǎng)公共子序列。NorthChinaElectricPowerUniversity由此遞歸結(jié)構(gòu)容易看到最長(zhǎng)公共子序列問題具有子問題重疊性質(zhì)。例如，在計(jì)算X和Y的最長(zhǎng)公共子序列時(shí)，可能要計(jì)算出X和Yn-1及Xm-1和Y的最長(zhǎng)公共子序列。而這兩個(gè)子問題都包含一個(gè)公共子問題，即計(jì)算Xm-1和Yn-1的最長(zhǎng)公共子序列。與矩陣連乘積最優(yōu)計(jì)算次序問題類似，我們來(lái)建立子問題的最優(yōu)值的遞歸關(guān)系。用c[i,j]記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中Xi=<x1,x2,…,xi>，Yj=<y1,y2,…,yj>。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列，故c[i,j]=0。其他情況下，由定理可建立遞歸關(guān)系如下：NorthChinaElectricPowerUniversity3.計(jì)算最優(yōu)值

直接利用上式容易寫出一個(gè)計(jì)算c[i,j]的遞歸算法，但其計(jì)算時(shí)間是隨輸入長(zhǎng)度指數(shù)增長(zhǎng)的。由于在所考慮的子問題空間中，總共只有θ(m*n)個(gè)不同的子問題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。計(jì)算最長(zhǎng)公共子序列長(zhǎng)度的動(dòng)態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>作為輸入。輸出兩個(gè)數(shù)組c[0..m,0..n]和b[1..m,1..n]。其中c[i,j]存儲(chǔ)Xi與Yj的最長(zhǎng)公共子序列的長(zhǎng)度，b[i,j]記錄指示c[i,j]的值是由哪一個(gè)子問題的解達(dá)到的，這在構(gòu)造最長(zhǎng)公共子序列時(shí)要用到。最后，X和Y的最長(zhǎng)公共子序列的長(zhǎng)度記錄于c[m,n]中。NorthChinaElectricPowerUniversityvoidLcs_length(charx[],chary[]);

{m=length[x];

n=length[y];

for(inti=1;i<=m;i++)c[i][0]=0;

for(intj=1;j<=n;j++)c[0][j]=0;

for(i=1;i<=m;i++)

{for(j=1;j<=n;j++)

if(x[i]==y[j])

{c[i][j]=c[i-1][j-1]+1;b[i][j]="↖";}

elseif(c[i-1][j]≥c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]="↑";}

else

{c[i][j]:=c[i][j-1];b[i][j]="←“;}

}

}算法描述如下：NorthChinaElectricPowerUniversity4.構(gòu)造最長(zhǎng)公共子序列

由算法Lcs_length計(jì)算得到的數(shù)組b可用于快速構(gòu)造序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的最長(zhǎng)公共子序列。首先從b[m,n]開始，沿著其中的箭頭所指的方向在數(shù)組b中搜索。當(dāng)b[i,j]中遇到"↖"時(shí)，表示Xi與Yj的最長(zhǎng)公共子序列是由Xi-1與Yj-1的最長(zhǎng)公共子序列在尾部加上xi得到的子序列；當(dāng)b[i,j]中遇到"↑"時(shí)，表示Xi與Yj的最長(zhǎng)公共子序列和Xi-1與Yj的最長(zhǎng)公共子序列相同；當(dāng)b[i,j]中遇到"←"時(shí)，表示Xi與Yj的最長(zhǎng)公共子序列和Xi與Yj-1的最長(zhǎng)公共子序列相同。

下面的算法LCS(b,X,i,j)實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi與Yj的最長(zhǎng)公共子序列。通過算法的調(diào)用LCS(X,length[X],length[Y])，便可打印出序列X和Y的最長(zhǎng)公共子序列。NorthChinaElectricPowerUniversityvoidLCS(X,i,j);

{if((i==0)||(j==0)return;

if(b[i][j]=="↖")

{LCS(X,i-1,j-1);

cout<<x[i];{打印x[i]}

}elseif(b[i][j]=="↑")LCS(b,X,i-1,j)elseLCS(b,X,i,j-1);

}NorthChinaElectricPowerUniversityj0123456iyjBDCABA┌─────────────┐0xi│000000││↑↑↑↖↖│1A│00001←11││↖↑↖│2B│01←1←112←2││↑↑↖↑↑│3C│0112←222││↖↑↑↑↖│4B│011223←3││↑↖↑↑↑↑│5D│0122233││↑↑↑↖↑↖│6A│0122334││↖↑↑↑↖↑│7B│0122345│└─────────────┘

j0123456iyjBDCABA┌─────────────┐0xi│000000││↑↑↑↖↖│1A│00001←11││↖↑↖│2B│01←1←112←2││↑↑↖↑↑│3C│0112←222││↖↑↑↑↖│4B│011223←3││↑↖↑↑↑↑│5D│0122233││↑↑↑↖↑↖│6A│0122334││↖↑↑↑↖↑│7B│0122345│└─────────────┘

j0123456iyjBDCABA┌─────────────┐0xi│000000││↑↑↑↖↖│1A│00001←11││↖↑↖│2B│01←1←112←2││↑↑↖↑↑│3C│0112←222││↖↑↑↑↖│4B│011223←3││↑↖↑↑↑↑│5D│0122233││↑↑↑↖↑↖│6A│0122334││↖↑↑↑↖↑│7B│0122345│└─────────────┘

例如，設(shè)所給的兩個(gè)序列為X=<A，B，C，B，D，A，B>和Y=<B，D，C，A，B，A>。由算法LCS_LENGTH和LCS計(jì)算出的結(jié)果如圖所示。NorthChinaElectricPowerUniversity問題描述：多邊形游戲是一個(gè)單人玩的游戲，開始時(shí)有一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的多邊形。每個(gè)頂點(diǎn)賦予一個(gè)整數(shù)值，每條邊賦予一個(gè)運(yùn)算符“+”或“*”。所有邊依次用整數(shù)從1到n編號(hào)。游戲第1步，將一條邊刪除；隨后n-1步按以下方式操作：1)選擇一條邊E以及由E連接著的兩個(gè)頂點(diǎn)v1和v2；2)用一個(gè)新的頂點(diǎn)取代邊E以及由E連接著的兩個(gè)頂點(diǎn)v1和v2，將頂點(diǎn)v1和v2的整數(shù)值通過邊E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上整數(shù)值。編程任務(wù)：

對(duì)于給定的多邊形，編程計(jì)算出最高分，并且列出所有得到這個(gè)最高得分首次被刪除的邊的序號(hào)。NorthChinaElectricPowerUniversity§9多邊形游戲1.最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)所給的多邊形的頂點(diǎn)和邊的順時(shí)針序列為op[1],v[1],op[2],v[2],…,op[n],v[n]其中，op[i]表示第i條邊所相應(yīng)的運(yùn)算符，v[i]表示第i個(gè)頂點(diǎn)上的數(shù)值，i=1,2,..,n。在所給多邊形中，從頂點(diǎn)i開始,長(zhǎng)度為j(鏈中有j個(gè)頂點(diǎn))的順時(shí)針鏈p(i,j)可表示為:v[i],op[i+1],…,v[i+j-1]如果這條鏈的最后一次合并運(yùn)算在op[i+s]處發(fā)生(1≤s≤j-1),則可在op[i+s]處將鏈分割為兩個(gè)子鏈p(i,s)和p(i+s,j-s)。設(shè)m1時(shí)對(duì)子鏈p(i,s)的任意一種合并方式得到的值，而a,b分別是在所有可能的合并中得到的最小值和最大值。m2是p(i+s,j-s)的任意一種合并方式得到的值，而c和d分別是在所有可能的合并中得到的最小值和最大值。依此定義有：a≤m1≤b,c≤m2≤d

由于子鏈p(i,s)和p(i+s,j-s)的合并方式?jīng)Q定了p(i,j)在op[i+s]處斷開后的合并方式，在op[i+s]處合并后其值為:NorthChinaElectricPowerUniversitym=(m1)op[i+s](m2)1)當(dāng)op[i+s]=‘+’時(shí)，顯然有a+c≤b+d。

換句話說，由鏈p(i,j)合并的最優(yōu)性可推出子鏈p(i,s)和p(i+s,j-s)的最優(yōu)性，且最大值對(duì)應(yīng)于子鏈的最大值，最小值對(duì)應(yīng)于子鏈的最小值。2)當(dāng)op[i+s]=‘*’時(shí)，情況有所不同。

由于v[i]可取負(fù)整數(shù)，子鏈的最大值相乘未必能得到主鏈的最大值。但我們注意到最大值一定在邊界點(diǎn)達(dá)到，即min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd}

換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。例如，當(dāng)m=ac時(shí)，最大主鏈由兩個(gè)最小子鏈組成；同理當(dāng)m=bd時(shí)，最大主鏈由它的兩個(gè)最大子鏈組成。無(wú)論哪種情形發(fā)生，由主鏈的最優(yōu)性均可推出子鏈的最優(yōu)性。

綜上所述，可知多邊形游戲問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。NorthChinaElectricPowerUniversity2.遞歸求解由前面的分析可知，為了求鏈合并的最大值，必須同時(shí)求子鏈合并的最大值和最小值。因此在整個(gè)計(jì)算過程中，應(yīng)同時(shí)計(jì)算最大值和最小值。

設(shè)m[i,j,0]是鏈p(i,j)合并的最小值，而m[i,j,1]是最大值。若最優(yōu)合并在op[i+s]處將p(i,j)分為2個(gè)長(zhǎng)度小于j的子鏈p(i,s)和p(i+s,j-s)，且從頂點(diǎn)i開始的長(zhǎng)度小于j的子鏈的最大值和最小值均已計(jì)算出。為敘述方便，記：

a=m[i,s,0],b=m[i,s,1],c=m[i+s,j-s,0],d=m[i+s,j-s,1]。1)當(dāng)op[i+s]=‘+’時(shí)，m[i,j,0]=a+cm[i,j,1]=b+d2)當(dāng)op[i+s]=‘*’時(shí)，

m[i,j,0]=min{ac,ad,bc,bd}m[i,j,1]=max{ac,ad,bc,bd}綜合(1)和(2)，將p(i,j)在op[i+s]處斷開的最大值記為maxf(i,j,s)，最小值記為minf(i,j,s),則NorthChinaElectricPowerUniversityminf(i,j,s)=a+cop[i+s]=‘+’min{ac,ad,bc,bd}op[i+s]=‘*’maxf(i,j,s)=b+dop[i+s]=‘+’max{ac,ad,bc,bd}op[i+s]=‘*’由于最優(yōu)斷開位置s有1≤s≤j-1的j-1種情況，由此可知初始值顯然為m[i,1,0]=v[i]1≤i≤nm[i,1,1]=v[i]1≤i≤n由于多邊形是封閉的，在上面的計(jì)算中，當(dāng)i+s>n時(shí)，頂點(diǎn)i+s實(shí)際編號(hào)為(i+s-1)%n+1。按上述遞推關(guān)系計(jì)算出的m[i,n,1]即為游戲首次刪去第i條邊后得到的最大值。NorthChinaElectricPowerUniversity算法描述如下(求得minf(i,j,s)和maxf(i,j,s))voidMin_max(intn,inti,ints,intj,int&minf,int&maxf){inte[4];inta=m[i][s][0],b=m[i][s][1],r=(i+s-1)%n+1;intc=m[r][j-s][0];intd=m[r][j-s][1];if(op[r]==‘t’){minf=a+c;maxf=b+d;}else{e[1]=a*c;e[2]=a*d;e[3]=b*c;e[4]=b*d;minf=e[1];maxf=e[1];for(intr=2;r<5;r++){if(minf>e[r])minf=e[r];if(maxf>e[r])maxf=e[r];}}}NorthChinaElectricPowerUniversityintPoly_max(intn){intminf,maxf;for(intj=2;j<=n;j++)//鏈中有j個(gè)頂點(diǎn)的時(shí)候for(inti=1;i<=n;i++)//鏈以頂點(diǎn)i為開始結(jié)點(diǎn)時(shí)for(ints=1;s<j;s++)//s的取值范圍為1<=s<=j-1{Min_max(n,i,s,j,minf,maxf);if(m[i][j][0]>minf)m[i][j][0]=minf;if(m[i][j][1]<maxf)m[i][j][1]=maxf;}inttemp=m[1][n][1];for(inti=2;i<=n;i++)if(temp<m[i][n][1])temp=m[i][n][1];returntemp;}算法的時(shí)間復(fù)雜性為O(n3)。NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity攔截導(dǎo)彈(問題來(lái)源:1999年全國(guó)青少年信息學(xué)(計(jì)算機(jī))奧林匹克分區(qū)聯(lián)賽)

某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊,發(fā)展出一種導(dǎo)彈攔截系統(tǒng).但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷:雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度,但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度.某天,雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲.由于該系統(tǒng)還在試用階段,所以只有一套系統(tǒng),因此有可能不能攔截所有的導(dǎo)彈.輸入導(dǎo)彈依次飛來(lái)的高度(雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)),計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈,并依次輸出被攔截的導(dǎo)彈飛來(lái)時(shí)候的高度.例如:INPUT

38920715530029917015865

OUTPUT

6(最多能攔截的導(dǎo)彈數(shù))

38930029917015865

NorthChinaElectricPowerUniversity因?yàn)橹挥幸惶讓?dǎo)彈攔截系統(tǒng),并且這套系統(tǒng)除了第一發(fā)炮彈能到達(dá)任意高度外,以后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度;所以,被攔截的導(dǎo)彈應(yīng)該按飛來(lái)的高度組成一個(gè)非遞增序列.題目要求我們計(jì)算這套系統(tǒng)最多能攔截的導(dǎo)彈數(shù),并依次輸出被攔截導(dǎo)彈的高度,實(shí)際上就是要求我們?cè)趯?dǎo)彈依次飛來(lái)的高度序列中尋找一個(gè)最長(zhǎng)非遞增子序列.NorthChinaElectricPowerUniversity問題描述：

給定由n個(gè)整數(shù)（可能為負(fù)整數(shù)）組成的序列a1,a2,…an，求該序列形如的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為0。最優(yōu)值為max{0,max}其中1<=i<=j<=n

§10最大子段和問題NorthChinaElectricPowerUniversity

1、簡(jiǎn)單算法對(duì)所有的子段和進(jìn)行比較，取得最大值，并記錄取最大值時(shí)的i值和j值。§10最大子段和問題算法描述如下：intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++)for(intj=i;j<=n;j++){intthissum=0;for(k=i;k<=j;k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}returnsum;}算法的時(shí)間復(fù)雜性為O(n3)。NorthChinaElectricPowerUniversity

2、算法該進(jìn)仔細(xì)觀察算法本身，可以把最內(nèi)層for循環(huán)去掉§10最大子段和問題算法描述如下：intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++){thissum+=a[j];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}returnsum;}算法的時(shí)間復(fù)雜性為O(n2)。NorthChinaElectricPowerUniversity3、分治算法

§10最大子段和問題算法描述如下：intMaxSubSum(intn,int*a,intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);intrightsum=MaxSubSum(a,center+1,right);ints1=0;intlefts=0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}

NorthChinaElectricPowerUniversity3、分治算法

§10最大子段和問題算法描述如下：ints2=0;intrights=0;for(inti=center+1;i<=right;i++){rights+=a[i];if(rights>s2)s2=rights;}sum=s1+s2;if(sum<leftsum)sum=leftsum;if(sum<rightsum)sum=rightsum;}returnsum;}T(n)=O(1)n<=c2T(n/2)+O(n)n>cT(n)=O(nlogn)NorthChinaElectricPowerUniversity4、動(dòng)態(tài)規(guī)劃算法

§10最大子段和問題算法描述如下：intMaxSum(intn,int*a){intsum=0;intb=0;for(inti=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}returnsum;}NorthChinaElectricPowerUniversity§110-1背包問題算法描述如下：

voidKnapsack(intv[],intw[],intc,intn,intm[6][N])

{

inti,j,jMax,k;

jMax=(w[n]-1<C;<span="">

for(i=0;i<=jMax;i++)

{

m[n][i]=0;

}

for(i=w[n];i<=c;i++)

{

m[n][i]=v[n];

}

NorthChinaElectricPowerUniversity

for(i=n-1;i>1;i--)

{

jMax=(w[i]-1<C;<span="">

for(j=0;j<=jMax;j++)

{

m[i][j]=m[i+1][j];

}

for(j=w[i];j<=c;j++)

{

k=j-w[i];

if(m[i+1][j]<M[I+1][K]+V[I])<span=""/>

m[i][j]=m[i+1][k]+v[i];

else

m[i][j]=m[i+1][j];

}

}

NorthChinaElectricPowerUniversity

m[1][c]=m[2][c];

if(c>=w[1])

{

k=c-w[1];

m[1][c]=(m[2][c]>m[2][k]+v[1])?m[2][c]:m[2][k]+v[1];

}

}

NorthChinaElectricPowerUniversity

voidTraceback(int**m,intw[],intc,intn,intx[])

{

inti;

for(i=1;i<n;i++)

{

if(m[i][c]==m[i+1][c])

x[i]=0;

else{

x[i]=1;

c-=w[i];

}

}

x[n]=(m[n][c])?1:0;

}

NorthChinaElectricPowerUniversity設(shè)f(T,2)表示對(duì)于一棵樹T，在T的樹根上布置守衛(wèi)的情況下，監(jiān)控T的全部節(jié)點(diǎn)所需的最少的費(fèi)用；假設(shè)T的兒子節(jié)點(diǎn)為T1,T2,…,Tn；則我們可以得到遞歸公式：如果T的根不布置守衛(wèi)，并且要求監(jiān)控T的所有結(jié)點(diǎn)，則必須保證T的子結(jié)點(diǎn)中有一個(gè)結(jié)點(diǎn)Tk的根上布置了一個(gè)守衛(wèi)，這樣在Tk的根上的守衛(wèi)可以同時(shí)看守T的根。至于T的其他子結(jié)點(diǎn)(i=1,2,..n,i≠k)，可以在樹根上布置守衛(wèi)，也可以不布置，但是必須監(jiān)控住自己所有的結(jié)點(diǎn)(因?yàn)門的根上沒有守衛(wèi))，因此選擇最優(yōu)的方案min{f(Ti,0),f(Ti,2)}。這樣就得到了(1)式；如果T的根不布置守衛(wèi)，并且要求監(jiān)控除了T的根結(jié)點(diǎn)以外的其他全部節(jié)點(diǎn)，則必須保證T的所有的子結(jié)點(diǎn)Ti都被監(jiān)控，而不用管Ti的根上是否有守衛(wèi)。于是每個(gè)子節(jié)點(diǎn)Ti取最優(yōu)的方案min{f(Ti,0),f(Ti,2)}。這樣就得到了(2)式。

如果規(guī)定T的根布置了守衛(wèi)，則T的所有的子結(jié)點(diǎn)上可以布置也可以不布置守衛(wèi)，而且T的所有的子結(jié)點(diǎn)Ti的根原來(lái)可以被監(jiān)控也可以不被監(jiān)控，這是因?yàn)槿绻瓉?lái)Ti的根沒有被監(jiān)控，則可以被T的根上布置的那個(gè)守衛(wèi)監(jiān)控。因此Ti選擇最優(yōu)的方案min{f(Ti,0),f(Ti,1),f(Ti,2)}。這樣就得到了(3)式,這里ω(T)表示在根結(jié)點(diǎn)T上布置守衛(wèi)的代價(jià)。

如果T是整棵樹的樹根的話，只要求出f(T,0),f(T,2)取較小者就是結(jié)果。對(duì)于T沒有兒子的情況（結(jié)點(diǎn)T為葉子），我們給出上面遞歸公式的邊界條件：NorthChinaElectricPowerUniversity注意，這里我們做了一點(diǎn)特殊規(guī)定，因?yàn)楦鶕?jù)前面對(duì)f(T,0)f(T,1)f(T,2)的定義可以知道，在T是葉子的情況下不在T的樹根上布置守衛(wèi)的情況下而要監(jiān)控T的全部節(jié)點(diǎn)是不可能的，f(T,0)實(shí)際上是不存在的，但是為了使上面的公式(1)-(3)能夠適用于邊界條件，我們規(guī)定了(4)式對(duì)于T是葉子的情況成立。這并不影響公式(1)-(3)的正確性。(5)說明在T是葉子的情況下，不在T的樹根上布置守衛(wèi)的情況下并監(jiān)控除了T的根結(jié)點(diǎn)以外的其他全部節(jié)點(diǎn)