北航 動態(tài)規(guī)劃03級考試題目

本文格式為Word版，下載可任意編輯——北航動態(tài)規(guī)劃03級考試題目算法分析講課張引第一小節(jié)動態(tài)規(guī)劃問題

——最短路徑問題

一在正式提出動態(tài)規(guī)劃法前我們先看一個數(shù)學例子：

例1：在x1+x2+x3+…+xn=a是約束條件下，求z?x1?x2???xn的極大值.令f1(a)?maxx?a(0?x?a)f2(a)?max(x?f1(a?x))?max(x?a?x)令y?x?a?x且dy?1?dx2x12a?x?a?x?x2x(a?x)?0

可得a?x=x,所以x=a/2

aa??2a22同理f3(a)?max(x?f2(a?x)?max(x?2(a?x))

故f2(a)?令y?x?2(a?x)

dy12a?x?2x????0dx2x2a?x2x(a?x)所以a?x=2x,x=a/3所以f3(a)=f3(a)?111a?2a?3a?3a333用數(shù)學歸納法可以證明：fn(a)=na,x1=x2=x3=…=xn=證明：1：n=1…

2：設fn(a)=na,x1=x2=x3=…=xn=fn+1(a)=max(令y=y’=

anx+fn(a-x))=max(

a成立，則nx?n(a?x))

x?n(a?x)

1n2a?x2xan?1=

a?x?nx2x(a?x)?0

所以nx=a-x,(n+1)x=ax=

fn+1(a)=

aa+n=(n?1)an?1n?1我們方才的解題策略是：“摸著石頭過河〞，f2利用f1的結果，f3又利用f2的結果。。。。。。

類似于游戲中的一個勇士擊敗了一些敵人后得到一件武器，然后去擊敗另一個強大一些的對手，得到一件更好的武器，接著擊敗更強大的敵人。。。。。最終取得勝利。。。

在實際生活中，有這么一類問題，它們的活動過程可分為若干個階段，而且在任一階段后的行為僅依靠于第I階段的過程狀態(tài)，而與I階段之前的過程如何達到這種過程如何達到這種狀態(tài)的方式無關，這樣的過程就構成了一個多階段決策過程。在50年代，貝爾曼（RichardBellman）等人根據(jù)這類問題的多階段決策的特性，提出了解決問題的“最優(yōu)性原理〞從而創(chuàng)立了最優(yōu)化問題的一種最新的算法設計方法——動態(tài)規(guī)劃。分治法和動態(tài)規(guī)劃法的比較

動態(tài)規(guī)劃算法與分治法類似，其根本思想也是將待求解問題分解成若干個子問題，先求第1頁

算法分析講課張引

解子問題，然后從這些子問題的解得到原問題的解，與分治法不同的是，適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是相互獨立的.以從16個數(shù)據(jù)中找出最大者為例，說明分治法的“靜〞和動態(tài)規(guī)劃法的“動〞的區(qū)別。

下面我們以具體的例子來說明如何運用動態(tài)規(guī)劃算法來求解問題，并分析可用動態(tài)規(guī)劃算法解的問題的所應具備的一般特征。

對教材68頁上的里子給予簡要說明（由于書上的文字表達有些含混晦澀，對符號的說明不明了）

y2K3P1S2UF

下面精講一個例子212232G3L4Q5TC34123DHMR22134A323

1

O

1.介紹這個圖的特點…..從而說明從O到A的最短路徑必由7段而不是更多或更少段組成。

其行進路線必然是x和y單調遞增的（非嚴格單調）。從O(0,0)到U（4，3）點的每一

4條路徑對應于由4個x上的和3個y上的字符構成的字符串，這種字符串的數(shù)目為C7=35.

假使采用窮舉法進行探尋，需要進行35*6=210次加法，34次比較。

2.下面我們采用動態(tài)規(guī)劃法來解決這一問題。令O為起點到U的最短距離為Do，以A為

起點到U的最短距離為DA---,用dij表示（i,j）邊的長度。顯然Ds=dsu=2,Dt=dTU=3,

DQ=min{2+2,5+3}=4DP=1+Ds=1+2=3DR=3+DT=3+3=6

DL=min{Dlq+DQ,dLP+DP}=min{4+DQ,2+Dp}=min{4+4,2+3}=5Dk=3+Dp=3+3=6

DM=min{2+DQ,4+DR}=min{2+4,4+6}=6DN=4+DR=4+6=10DF=2+DK=2+6=8

DG=min{1+DK,3+DL}=min{1+6,3+5}=7DH=min{1+5,1+6}=6

DJ=min{3+DM,3+DN}=min{3+6,3+10}=9DC=min{2+DF,2+DG}=min{2+8,2+7}=9DD=min{4+DG,2+DH}=min{4+7,2+6}=8DE=min{1+DH,2+DJ}=min{1+6,2+9}=7DA=min{3+DC,2+DD}=min{3+9,2+8}=10DB=min{2+DD,3+DE}==min{2+8,3+7}=10Do==min{1+DB,2+DA}=min{1+10,2+10}=11

共進行了29次加法，12次比較。由Do=1+DB=11回溯，可得到最短路徑為

O—>B-?D->H?L—>P-?S-?UO-?B-?E-?H-?L-?P-?S-?U

推廣到x軸m段y軸n段的情形：用動態(tài)規(guī)劃法需要做2mn+（m+n-2）次加法，mm次比第2頁

算法分析講課張引

較；而假使用窮舉法，需要

若m=n,動態(tài)規(guī)劃法要做2n2+2n-2次加法，n2次比較，因此繁雜度為O(n2);而窮舉法需要

(m?n)!(m?n)!*(m?n?1)次加法，?1次比較。m!n!m!n!(2n)!(2n)!*(2n?1)次加法，?1次比較，>O(n2n+1)。n!n!n!n!其次小節(jié)動態(tài)規(guī)劃問題

——貨郎擔問題

1.動態(tài)規(guī)劃方法的思想

動態(tài)規(guī)劃是一種將問題實例分解為更小的、相像的子問題，并存儲子問題的解而避免計算重復的子問題，以解決最優(yōu)化問題的算法策略。2.貨郎擔問題：

某售貨員要到若干個村莊售貨，各村莊之間的路程是已知的，為了提高效率，售貨員決定從所在商店出發(fā)，到每個村莊售一次貨然后返回商店，問他應選擇一條什么路線才能使所走的總路程最短？

實質從某點出發(fā),遍歷其余點,再回到原點,求總路徑消耗最少的路線.

[例]設共有4個要經(jīng)過的點---1，2，3，4各個點之間的花費如下：1>2:10;1>3:15;1>4:20;2>1:5;2>3:9;2>4:10;3>1:6;3>2:13;3>4:12;4>1:8;4>2:8;4>3:9;（最短路徑：1>2>4>3>1））

12254678557885343.問題的解決1.)問題的描述:?T(V1;V)表示從V1出發(fā),經(jīng)過頂點集合V中的點各一次,再回到點

V1的最短路徑.第3頁

算法分析講課張引

2.)動態(tài)規(guī)劃函數(shù):

T(vi;V)=min{dij+T(vj;V-{vj})}(vj屬于V)

?T(vi;V):就是從V中任何一點vi出發(fā),經(jīng)過V中的點各一次,再回到

點vi的最短路徑.

?Dij:表示從點vi出發(fā),到某點vj的花費(有方向性).

?注:這是一個遞歸定義的函數(shù),關鍵是每次的函數(shù)T(vi;V)它所處理的點

集逐漸減少.

3.)實例:(如上圖)求從v1出發(fā)的貨郎擔問題.解:T(v1;V)=T(v1;v1,v2,v3,v4)

=min{d12+T(v2;v3,v4),d13+T(v3;v2,v4),d14+T(v4;v2,v3)}

//實例意義:初始的貨郎擔問題是從點v1出發(fā),涉及其余3點

v2,v3,v4;那依照動態(tài)規(guī)劃“分而治之〞的思想(這里就是把問題規(guī)?？s小,而問題的數(shù)量可多一些),我們可先計算分別從v2,v3,v4出發(fā),涉及(v2,v3,v4)三點的三條貨郎擔路線的路耗,再各自加上相應的dij,這樣,最終就得到3個總路耗,再做一個min運算,就可求出初始問題的解.

T(v2;v3,v4)=min{d23+T(v3;v4),d24+T(v4;v3)}T(v3;v4)=d34+T(v4,@)T(v4;v3)=d43+T(v3,@)T(v4,@)=d41T(v3,@)=d31

T(v3;v4)=d34+d41=6+9=15T(v4;v3)=d43+d31=8+8=16

T(v2;v3,v4)=min{d23+d34+d41,d24+d43+d31}=min{7+6+9,6+8+8}=22

同理:

T(v3;v2,v4)=min{d32+d24+d41,d34+d42+d21}=min{5+6+9,6+5+4}=15

T(v4;v2,v3)=min{d42+d23+d31,d43+d32+d21}=min{5+7+8,8+5+4}=17則最終:T(v1;v1,v2,v3,v4)

=min{d12+T(v2;v3,v4),

d13+T(v3;v2,v4),

d14+T(v4;v2,v3)}

=min{2+22,5+15,8+17}=20所選的路線是:1->3->4->2->1

第三小節(jié)動態(tài)規(guī)劃問題

——投資問題

一問題描述：投資問題就是考慮如何把有限資源分派給若干個工程的問題。

二給定條件：1.資源總數(shù)（設為a）

2.工程個數(shù)（設為n）3.每項工程投資的利潤（不同數(shù)目的投資所獲得的利潤不同），用向量Gi(1≦i第4頁

算法分析講課張引

≦n)表示。n三問題求解：求出一個a的分劃x1,x2,…..,xn,0≦xi≦a,且∑xi≦a,使得以下式表示的利潤為最大：i=1nG(a)=∑Gi(xj)0≦xj≦a

i=1

其中Gi(xj)是把資源xj分派給第I項工程能獲得的最大利潤。

四問題分析：

i）若Gi是x的線性函數(shù)，則為線性規(guī)劃問題。

ii）若Gi不是線性函數(shù)，則要用動態(tài)規(guī)劃求最正確分派。

用總量為a的資金在n個項目上進行投資以取得最大的利潤，可以轉化為下述的問題：

將總量資金a分為兩部分z(0≦z≦a)及a-z，分別用在第n個項目及剩下的n-1個項目上進行投資，獲得的最大利潤G(a)=max(第n個項目上資金量為z的利潤與用a-z的資金在n-1個項目上投資的最大利潤之和)。這樣問題就轉化為〞求用a-z的資金在n-1個項目上投資的最大利潤〞，與我們的原問題〞求總量為a的資金在n個項目上進行投資以取得最大的利潤〞性質完全一致，僅僅是問題的規(guī)模比原問題少了一個項目，如此將問題的規(guī)模細化下去，一直到項目數(shù)為1為止，則問題迎刃而解。我們在對原問題進行〞分而治之〞的過程當中，最終實現(xiàn)了最優(yōu)化的求解。

五問題解決方案：設fi(x)：前i個項目共投資資金x所產生的最大利潤；di(x)：產生fi(x)在項目i上的資金數(shù)。

由上分析可給出投資問題的動態(tài)規(guī)劃函數(shù)方程：f1(x)=G1(x);

d1(x)=xx=0,1……a

fi(x)=max[Gi(z)+fi-1(x-z)]z=0,1……x;x=0,1……adi(x)=產生fi(x)的z值i=2,3…..n;

六問題舉例：設有8（萬元）的投資可分給3個項目，每個項目的利潤函數(shù)如下表（一）所示：表（一）利潤函數(shù)表x012345678G1(x)0