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

第五章動態(tài)規(guī)劃第五章動態(tài)規(guī)劃11海盜分金問題5名海盜搶得了窖藏的100塊金子，并打算瓜分這些戰(zhàn)利品。這是一些講民主的海盜（當然是他們自己特有的民主），他們的習慣是按下面的方式進行分配：最厲害的一名海盜提出分配方案，然后所有的海盜（包括提出方案者本人）就此方案進行表決。如果50%或更多的海盜贊同此方案，此方案就獲得通過并據(jù)此分配戰(zhàn)利品。否則提出方案的海盜將被扔到海里，然后下一名最厲害的海盜又重復上述過程。1海盜分金問題5名海盜搶得了窖藏的100塊金子，并打算瓜分2所有的海盜都樂于看到他們的一位同伙被扔進海里，不過，如果讓他們選擇的話，他們還是寧可得一筆現(xiàn)金。他們當然也不愿意自己被扔到海里。所有的海盜都是聰明絕頂?shù)?，而且知道其他的海盜也是聰明絕頂?shù)摹４送?，沒有兩名海盜是同等厲害的——這些海盜按照完全由上到下的等級排好了座次，并且每個人都清楚自己和其他所有人的等級。這些金塊不能再分，也不允許幾名海盜共有金塊，因為任何海盜都不相信他的同伙會遵守關于共享金塊的安排。這是一伙每人都只為自己打算的海盜。所有的海盜都樂于看到他們的一位同伙被扔進海里，不過，如果讓他3最兇的一名海盜應當提出什么樣的分配方案才能使他獲得最多的金子呢？我們按照這些海盜的威望值來給他們編號。最怯懦的海盜為1，最厲害的海盜編號為5。編號為5的海盜會提出什么分配方案呢？最兇的一名海盜應當提出什么樣的分配方案才能使他獲得最多的金子4如果從游戲的開頭出發(fā)進行分析，那是走不了多遠的。其原因在于，所有的戰(zhàn)略決策都是要確定：“如果我這樣做，那么下一個人會怎樣做？”因此在你以下海盜所做的決定對你來說是重要的，而在你之前的海盜所做的決定并不重要，因為你反正對這些決定也無能為力了。如果從游戲的開頭出發(fā)進行分析，那是走不了多遠的。5最厲害的5號海盜需要知道其他4名海盜是怎么想的.......好難猜！對4號海盜來說，如果5號海盜被扔進海里喂鯊魚了，他只需要猜透其余3名海盜的算盤。對3號海盜而言，他只須猜透1號和2號海盜對2號海盜而言，他只須猜透1號海盜那我們就倒過來，由易到難最厲害的5號海盜需要知道其他4名海盜是怎么想的.......6我們的出發(fā)點應當是游戲進行到只剩兩名海盜——即1號和2號——的時候。這時最厲害的海盜是2號，而他的最佳分配方案是一目了然的：100塊金子全歸他一人所有，1號海盜什么也得不到。3號海盜的分配方案：3號海盜分得99塊金子，2號海盜一無所獲，1號海盜得1塊金子。1號海盜知道，如果3號的方案被否決，那么最后將只剩2個海盜，而1號將肯定一無所獲——此外，3號也明白1號了解這一形勢。因此，只要3號的分配方案給1號一點甜頭使他不至于空手而歸，那么不論3號提出什么樣的分配方案，1號都將投贊成票。因此3號需要分出盡可能少的一點金子來賄賂1號海盜我們的出發(fā)點應當是游戲進行到只剩兩名海盜——即1號和2號——74號的分配方案應是：99塊金子歸自己，3號一塊也得不到，2號得1塊金子，1號也是一塊也得不到。4號海盜的策略也差不多。他需要有50%的支持票，因此同3號一樣也需再找一人做同黨。他可以給同黨的最低賄賂是1塊金子，而他可以用這塊金子來收買2號海盜。因為如果4號被否決而3號得以通過，則2號將一文不名。4號的分配方案應是：99塊金子歸自己，3號一塊也得不到，2號85號海盜的分配方案應該是：98塊金子歸自己，1塊金子給3號，1塊金子給1號。5號海盜的策略稍有不同。他需要收買另兩名海盜，因此至少得用2塊金子來賄賂，才能使自己的方案得到采納。討論：為什么賄賂1號和3號而不是4號和2號？5號海盜的分配方案應該是：98塊金子歸自己，1塊金子給3號，9總結分析所有這類策略游戲的奧妙就在于應當從結尾出發(fā)倒推回去。游戲結束時，你容易知道何種決策有利而何種決策不利?？偨Y10在現(xiàn)實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。這種把一個問題看作是一個前后關聯(lián)具有鏈狀結構的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策問題。

多階段決策問題在現(xiàn)實生活中，有一類活動的過程，由于它的特殊性，可將過程分成117E52D1D23738C1C2C3B1B2

A755586757下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費用，單向通行由A->E。試用動態(tài)規(guī)劃的最優(yōu)化原理求出A->E的最省費用。2最短距離問題7E52D1378C1C2B1B2A755675712如圖從A到E共分為4個階段，即第一階段從A到B，第二階段從B到C，第三階段從C到D，第四階段從D到E。除起點A和終點E外，其它各點既是上一階段的終點又是下一階段的起點。例如從A到B的第一階段中，A為起點，終點有B1，B2兩個，因而這時走的路線有兩個選擇，一是走到B1，一是走到B2。若選擇B2的決策，B2就是第一階段在我們決策之下的結果，它既是第一階段路線的終點，又是第二階段路線的始點。在第二階段，再從B2點出發(fā)，對于B2點就有一個可供選擇的終點集合(C1，C2，C3)；若選擇由B2走至C2為第二階段的決策，則C2就是第二階段的終點，同時又是第三階段的始點。同理遞推下去，可看到各個階段的決策不同，線路就不同。如圖從A到E共分為4個階段，即第一階段從A到B，第二13很明顯，當某階段的起點給定時，它直接影響著后面各階段的行進路線和整個路線的長短。故此問題的要求是：在各個階段選取一個恰當?shù)臎Q策，使由這些決策組成的一個決策序列所決定的一條路線，其總路程最短。如何解決這個問題呢？

要求在各階段選取一個恰當?shù)臎Q策很明顯，當某階段的起點給定時，它直接影響著后面各階14用枚舉法

把所有由A->E可能的每一條路線的距離算出來，然后互相比較，找出最短者，相應地得出了最短路線。

用枚舉法

把所有由A->E可能的每一條路線的距離算出來，然后15用動態(tài)規(guī)劃法求解

決策過程：

（1）由目標狀態(tài)E向前推，可以分成四個階段，即四個子問題。DECEBEAE

（2）策略：每個階段到E的最省費用為本階段的決策路徑。

用動態(tài)規(guī)劃法求解

決策過程：

（1）由目標狀態(tài)E向前推，可以16（3）D1，D2是第一次輸入的結點。他們到E都只有一種費用：f(D1)=5f(D2)=2E52D1D2目前無法定下，哪一個點將在全程最優(yōu)策略的路徑上。第二階段計算中，5，2都應分別參加計算（3）D1，D2是第一次輸入的結點。他們到E都只有一種費用：17（4）C1，C2，C3是第二次輸入結點，他們到D1，D2各有兩種費用。此時應計算C1，C2，C3分別到E的最少費用。

f(C1)=min{C1D1+f(D1)，C1D2+f(D2)}。計算結果是f(C1)=C1D1+f(D1)=8（D1)同理C2的決策路徑計算結果是C2+D2+E,f(C2)=7。

同理C3的決策路徑計算結果是C3+D2+E，f(C3)=10。E8752D1D23738C1C2C35710此時也無法定下第一，二階段的城市那二個將在整體的最優(yōu)決策路徑上。

（4）C1，C2，C3是第二次輸入結點，他們到D1，D2各有18（5）第三次輸入結點為B1，B2，而決策輸出結點可能為C1，C2，C3。仿前計算可得Bl，B2的決策路徑為如下情況。

Bl:B1C1費用f(B1)=5+8=13，B2:B2C1費用f(B2)=6+8=14，75B1B25867E8752D1D23738C1C2C357101314此時也無法定下第一，二，三階段的城市那三個將在整體的最優(yōu)決策路徑上。（5）第三次輸入結點為B1，B2，而決策輸出結點可能為C1，19（6）第四次輸入結點為A，決策輸出結點可能為B1，B2。同理可得決策路徑為A：AB2，費用5+14=19此時才正式確定每個子問題的結點中，那一個結點將在最優(yōu)費用的路徑上。子問題的決策中，只對同一城市（結點）比較優(yōu)劣。而同一階段的城市（結點）的優(yōu)劣要由下一個階段去決定。75B1B25867E8752D1D23738C1C2C357101314A1975（6）第四次輸入結點為A，決策輸出結點可能為B1，B2。7520如何用計算機實現(xiàn)上述算法？用數(shù)組來存儲中間結果，用空間代價換取時間效率先自底向上構造中間結果，再自頂向下作出最優(yōu)決策如何用計算機實現(xiàn)上述算法？用數(shù)組來存儲中間結果，用空間代價換21ABCDEf(A)f(B1)f(C1)f(D1)0f(B2)f(C2)f(D2)f(C3)ABCDE1913850147210ABCDEB2C1D1EC1D2ED2由表二和表三作出最優(yōu)決策：AB2C1D1E表一：表二：各城市到E的最短距離表三：各城市的最優(yōu)后繼（使其到E最近）ABCDEf(A)f(B1)f(C1)f(D1)0f(B2)22小結及比較

與窮舉法相比，動態(tài)規(guī)劃的方法有兩個明顯的優(yōu)點:

(1)大大減少了計算量

(2)豐富了計算結果

從上例的求解結果中，我們不僅得到由A點出發(fā)到終點E的最短路線及最短距離，而且還得到了從所有各中間點到終點的最短路線及最短距離，這對許多實際問題來講是很有用的。

小結及比較

與窮舉法相比，動態(tài)規(guī)劃的方法有兩個明顯的優(yōu)點:

23動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題3.動態(tài)規(guī)劃總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若24但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用遞歸法求解時，有些子問題被重復計算了許多次。算法總體思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常25如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答26是先把問題分成多個子問題（一般地每個子問題是互相關聯(lián)和影響的），再依次研究逐個問題的決策。決策就是某個階段的狀態(tài)確定后，從該狀態(tài)演變到下一階段狀態(tài)的選擇。當全體子問題都解決時，整體問題也隨之解決。最優(yōu)子結構性質子問題重疊性質

動態(tài)規(guī)劃的解題思路是先把問題分成多個子問題（一般地每個子問題是互相關聯(lián)和影響的27最優(yōu)子結構性質一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結構性質。例如上圖中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。這可用反證法證明：假設有另一路徑J'是B到C的最優(yōu)路徑，則A到C的路線取I和J'比I和J更優(yōu)，矛盾。從而證明J'必是B到C的最優(yōu)路徑。最優(yōu)子結構性質一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足28子問題的重疊性動態(tài)規(guī)劃的關鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。動態(tài)規(guī)劃實質上是一種以空間換時間的技術，它在實現(xiàn)的過程中，不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以它的空間復雜度要大于其它的算法。選擇動態(tài)規(guī)劃算法是因為動態(tài)規(guī)劃算法在空間上可以承受，而搜索算法在時間上卻無法承受，所以我們舍空間而取時間。子問題的重疊性動態(tài)規(guī)劃的關鍵在于解決冗余，這是動態(tài)規(guī)劃算法的29動態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質，并刻劃其結構特征。遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。動態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質，并刻劃其結構特征。30思考與練習若城市路徑示意圖如下圖所示，

圖中，每條邊上的數(shù)字是通過這段道路所須的平均時間。條件：從A地出發(fā)，只允許向右或向上走。試尋找一條從A地到B地所需時間最短路徑和總時間。思考與練習若城市路徑示意圖如下圖所示，314、數(shù)塔問題

有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結點可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。4、數(shù)塔問題 有形如下圖所示的數(shù)塔，從頂32用暴力的方法，可以嗎？用暴力的方法，可以嗎？33 這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如31），則需要列舉出的路徑條數(shù)將是一個非常龐大的數(shù)目（2^30=1024^3>10^9=10億）。試想一下： 這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如34

拒絕暴力，倡導和諧～拒絕暴力，倡導和諧～35

從頂點出發(fā)時到底向左走還是向右走應取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。 可見，由下層的子問題可以得到上層的子問題，所以，可從底層開始，層層遞進，最后得到最大值。結論：自頂向下的分析，自底向上的計算。考慮一下： 從頂點出發(fā)時到底向左走還是向右走應取決于是從左走能取到最365海盜盜寶問題海盜有一背包，能容納10公斤物品，現(xiàn)有三件寶物：重量分別是6，5，5公斤,價值分別是30萬，20萬，15萬請給出裝載方案，使背包價值達到最大。5海盜盜寶問題海盜有一背包，能容納10公斤物品370-1背包問題給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?目標：使裝入背包中物品的總價值最大約束條件：裝入的物品總重不得超過C0-1背包問題給定n種物品和一背包。物品i的重量是w38海盜盜寶問題海盜有一背包，最大容積為9，現(xiàn)有5件寶物：體積si分別是2、3、4、5和4公斤價值vi分別是3、7、5、9和8請給出裝載方案，使背包價值達到最大。S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8C=9海盜盜寶問題海盜有一背包，最大容積為9，現(xiàn)有5件寶39一開始，見物品就裝，物品1、2、3全裝入，背包裝滿了，得到背包總價值為15，這是不是最大價值呢？S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8考慮只有前三個物品的情況一開始，見物品就裝，物品1、2、3全裝入，背包裝滿了，得到背40物品4該不該裝？有兩個選擇：（1）不裝，背包價值不變，為15S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9（2）裝入，它占去的體積為5，得到價值為9，剩下容積4最多可以裝下多大價值？考慮只有前4個物品的情況物品4該不該裝？有兩個選擇：S1=2S2=3S3=4S4=541這是一個n=3(從前三個物品中選擇），容量c=4的子問題。目前最優(yōu)：裝入物品2和物品4，總價值為16若已知這個子問題的解是：裝物品2，得價值為7。S1=2v1=3S3=4v3=5S4=5v4=9（2）裝入物品4，它占去的體積為5，得到價值為9，剩下容積4最多可以裝下多大價值？S2=3v2=7這是一個n=3(從前三個物品中選擇），容量c=4的子問題。目42S1=2v1=3S3=4v3=5S4=5v4=9S5=4v5=8考慮5個物品的情況S2=3v2=7物品5該不該裝？(1)不裝，得到背包價值仍為16S1=2S3=4S4=5S5=4考慮5個物品的情況S2=3物43（2）若裝入物品5，占用體積為4，得價值為8，背包剩余容積為5。如何在前4個物品中選擇裝入，使背包價值最大化？這是n=4,c=5的一個子問題。若得到該子問題的解為：裝入物品1、2，得價值為10S1=2v1=3S3=4v3=5S5=4v5=8考慮5個物品的情況S2=3v2=7目前最優(yōu)：裝入物品5和1、2，總價值為18>16S4=5v4=9（2）若裝入物品5，占用體積為4，得價值為8，背包剩余容積為44子問題的構造當n=1時:只有一個物品，s1=2,v1=3若背包容量c=0、1，則無法裝入物品1，得到背包價值為0若背包容量c=2、3、4、5、6，7，8，9則可裝入物品1，得到背包價值為3。C[1][0]=0C[1][1]=0C[1][2]=3C[1][3]=3C[1][4]=3C[1][5]=3C[1][6]=3C[1][7]=3C[1][8]=3C[1][9]=3子問題的構造當n=1時:只有一個物品，s1=2,v1=3C45考慮兩個物品的情況當n=2時，有兩個物品，s1=2,v1=3，s2=3,v2=7若背包容量c=0、1，得到背包價值為0若背包容量c=2，可裝入物品1，得總價值m[2][2]=3若背包容量c=3，m[2][3]=7若背包容量c=4,m[2][4]=7若背包容量c=5,m[2][5]=10若不裝物品2，m[2][3]=m[1][3]=3若裝入物品2，m[2][3]=v[2]+m[1][3-3]=7+0=7m[2][6]=10m[2][7]=10m[2][8]=10m[2][9]=10若不裝物品2，m[2][5]=m[1][5]=3若裝入物品2，m[2][5]=v[2]+m[1][5-3]=7+3=7考慮兩個物品的情況當n=2時，有兩個物品，s1=2,v1=46遞推關系的建立用m[i][j]來表示從前i個物品中選取物品裝入容量為j的背包所得的最大價值。則要尋求的是m[n][c]。m[i][j]是以下兩個值的最大值

（1）m[i-1][j]:即不裝入物品i,背包價值與僅考慮前i-1個物品時情況相同；（2）v[i]+m[i-1][j-s[i]]:即裝入物品i,再從前i-1個物品中選取，使背包剩余容積j-s[i]價值最大化。遞推關系的建立用m[i][j]來表示從前i個物品中選取物品裝47構造價值數(shù)組S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=80123456789000000000001020304050背包容量j從前i個物品中選取構造價值數(shù)組S1=2S2=3S3=4S4=5S5=4012348S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8012345678900000000000100333333332003771010101010300377101012121540037710101216165018背包容量j從前i個物品中選取S1=2S2=3S3=4S4=5S5=4012345678949構造最優(yōu)解0123456789000000000001003333333320037710101010103003771010121215400377101012161650037