算法設(shè)計與分析：第四章5-動態(tài)規(guī)劃1

11一月20231第四章4.5動態(tài)規(guī)劃

11一月20232學習要點理解動態(tài)規(guī)劃算法的概念。掌握動態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題理解動態(tài)規(guī)劃算法與貪心算法的差異理解動態(tài)規(guī)劃算法的一般理論通過應用范例學習動態(tài)規(guī)劃設(shè)計策略。什么是動態(tài)規(guī)劃動態(tài)規(guī)劃與多段圖資源分配問題

0/1背包問題可靠性設(shè)計貨郎擔問題流水線調(diào)度問題

11一月20233

動態(tài)規(guī)劃是解決最優(yōu)化問題的方法之一。動態(tài)規(guī)劃是現(xiàn)代管理中一種重要的決策方法,它可以廣泛地用于解決最短路徑問題、資源分配問題、生產(chǎn)計劃與庫存問題、投資問題、裝載問題、排序問題及生產(chǎn)過程的最優(yōu)控制等。由于它具有獨特的解題思路因此在處理某些優(yōu)化問題時常比線性規(guī)劃等方法更為有效。11一月20234123458761110912st97324227111118654356524問題的提出首先，例舉一個典型的且很直觀的決策問題:

[例]下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費用，單向通行由s->t。求s->t最省的費用。采用的求解方法，可以用窮舉法。11一月20235

從上例的求解中，我們不僅得到由s點出發(fā)到終點t的最短路線及最短距離，而且還得到了從所有各中間點到終點的最短路線及最短距離，這對許多實際問題來講是很有用的。與窮舉法相比，動態(tài)規(guī)劃的方法有兩個明顯的優(yōu)點:

(1)大大減少了計算量

(2)豐富了計算結(jié)果

動態(tài)規(guī)劃的最優(yōu)化概念是在一定條件下，找到一種途徑，在對各階段的效益經(jīng)過按問題具體性質(zhì)所確定的運算以后，使得全過程的總效益達到最優(yōu)。

應用動態(tài)規(guī)劃要注意階段的劃分是關(guān)鍵，必須依據(jù)題意分析，尋求合理的劃分階段(子問題)方法。而每個子問題是一個比原問題簡單得多的優(yōu)化問題。而且每個子問題的求解中，均利用它的一個后部子問題的最優(yōu)化結(jié)果，直到最后一個子問題所得最優(yōu)解，它就是原問題的最優(yōu)解。顯然，用枚舉的方法從所有可能的決策序列中去選取最優(yōu)決策序列是一種最笨拙的方法。采用動態(tài)規(guī)劃法，常常能得到一個比枚舉法有效的算法123458761110912st9732422711111865435652411一月202364.1一般方法在實際生活中，有一類問題的活動過程可以分為若干個階段，而且在任一階段后的行為都依賴于該階段的狀態(tài)，而與該階段之前的過程是如何達到這種狀態(tài)的方式無關(guān)，這類問題的解決就構(gòu)成了一個多階段決策過程。在50年代，貝爾曼等人提出了解決這類問題的“最優(yōu)化原理”，從而創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計——動態(tài)規(guī)劃。動態(tài)規(guī)劃方法是處理分段過程最優(yōu)化問題的一類及其有效的方法。

最優(yōu)性原理(PrincipleofOptimality)

多階段過程的最優(yōu)決策序列應當具有如下性質(zhì)：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個最優(yōu)決策序列。1kn4.1.1一般概念11一月20237

如果對于所求解的問題最優(yōu)性原理成立；則說明用動態(tài)規(guī)劃方法有可能解決該問題。而解決問題的關(guān)鍵在于獲取各階段間的遞推關(guān)系式。

任何多階段過程問題，只有證明其最優(yōu)化原理成立，才可能用動態(tài)規(guī)劃的方法予以解決。

最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。動態(tài)規(guī)劃的最優(yōu)化理論在其指標函數(shù)的可分離性和單調(diào)性中得到體現(xiàn)。根據(jù)最優(yōu)化原理導出的動態(tài)規(guī)劃基本方程是解決一切動態(tài)規(guī)劃問題的基本方法。123458761110912st9732422711111865435652411一月20238

在多階段決策過程的每一個階段，都可能有多種選擇的決策，但必須從中選取一種決策。一旦各種階段的決策選定之后，就構(gòu)成了解決這一問題的一個決策序列。決策序列不同，導致的問題結(jié)果也不同。所以動態(tài)規(guī)劃的目標就是要在所有容許選擇的決策序列中選取一個會獲得問題最優(yōu)解的決策序列，即最優(yōu)決策序列。123458761110912st9732422711111865435652411一月20239

對于一個多階段過程問題，上述最優(yōu)決策是否存在,依賴于該問題是否有最優(yōu)子結(jié)構(gòu)性質(zhì),而能否采用動態(tài)規(guī)劃的方法，還要看該問題的子問題是否具有重疊性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：原問題的最優(yōu)解包含了其子問題的最優(yōu)解?！獫M足最優(yōu)性原理子問題重疊性質(zhì)：每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。動態(tài)規(guī)劃算法的適用條件

動態(tài)規(guī)劃不是萬能的，它只適于解決一定條件的最優(yōu)策略問題。

很多問題都可以用動態(tài)規(guī)劃法來求解，因為這個范圍內(nèi)的問題極多，還有許多看似不是這個范圍中的問題都可以轉(zhuǎn)化成這類問題。而問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是采用動態(tài)規(guī)劃算法的兩個基本要素。11一月2023101.最優(yōu)子結(jié)構(gòu)性質(zhì)：

在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導致矛盾。11一月202311例如圖中，若路線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)路徑。11一月202312

——利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提。注意：同一個問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快(空間占用小，問題的維度低)。123458761110912st9732422711111865435652411一月202313遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。通常不同的子問題個數(shù)隨問題的大小呈多項式增長。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效率。2重疊子問題123458761110912st9732422711111865435652411一月202314動態(tài)規(guī)劃算法和貪心選擇算法、分治法的比較動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)解。其中貪心法的當前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇。具有最優(yōu)子結(jié)構(gòu)，但不具有子問題重疊。而分治法中的各個子問題是獨立的

(即不包含公共的子問題)，因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的是，如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優(yōu)解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題。分治法主要是求解11一月202315

解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應用于最優(yōu)化問題，這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃可找出其中最優(yōu)(最大或最小)值的解。若存在若干個取最優(yōu)值的解的話，它只取其中的一個(可能不唯一)。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優(yōu)解，但與分治法和貪心法不同的是，動態(tài)規(guī)劃允許這些子問題不獨立，(亦即各子問題可包含公共的子問題)也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結(jié)果保存起來，避免每次碰到時都要重復計算。因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應的子問題樹中的子問題呈現(xiàn)大量的重復。動態(tài)規(guī)劃法的關(guān)鍵就在于，對于重復出現(xiàn)的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。11一月202316

如何用動態(tài)規(guī)劃法求解動態(tài)規(guī)劃的設(shè)計方法對不同問題，有各具特色的表達方式。這是由于各種問題的性質(zhì)不同，因此判定最佳解的條件也不相同。不存在一種萬能的動態(tài)規(guī)劃算法。但是，我們可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法的研究來學習這一設(shè)計方法。向前處理法（逆序法）：從最后階段開始，以逐步向前遞推的方式列出求前一階段決策值的遞推關(guān)系式，即根據(jù)xi+1,…,xn的那些最優(yōu)決策序列來列出求取xi決策值的關(guān)系式。向后處理方法（順序法）：從初始階段開始，逐步向后遞推，根據(jù)x1,…,xi-1的那些最優(yōu)決策序列列出求xi的遞推關(guān)系式。11一月202317一般地說，兩種解法在本質(zhì)上沒有什么不同，通常情況下，當初始狀態(tài)給定時用向前處理解法較方便，當終止狀態(tài)給定時用向后處理解法較方便。但若初始狀態(tài)雖已給定，然而終點狀態(tài)較多，需比較到達不同終點狀態(tài)的各個路徑及指標函數(shù)值，以選取總效益最佳的終點狀態(tài)時，以使用向后處理解法比較方便。另外在初始狀態(tài)和終止狀態(tài)均為已知，但當使用不同方法第一步需處理的狀態(tài)不同時，以選擇第一步需處理較多狀態(tài)的方法為比較合適，這樣可以減少運算工作量（可以自行試驗他們的工作量）。靈活地選用這兩種方法之一，可以使求解過程簡化。

還需要注意以下區(qū)別：1.狀態(tài)變量的含義不同2.決策過程和結(jié)果不同3.狀態(tài)轉(zhuǎn)移方式不同4.指標函數(shù)的定義不同5.基本方程形式不同11一月2023181找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。2遞歸地定義最優(yōu)解。3以自底向上(由后向前推)的方式計算最優(yōu)解。4根據(jù)計算最優(yōu)解時得到的信息，構(gòu)造一個最優(yōu)解。動態(tài)規(guī)劃算法的基本步驟前三步是基本的步驟，若要構(gòu)造問題的一個最優(yōu)解，必須執(zhí)行步驟4。設(shè)計一個動態(tài)規(guī)劃算法，在應用中通?？砂匆韵聨讉€步驟進行：根據(jù)上述動態(tài)規(guī)劃設(shè)計的步驟，也可得到大體解題框架如下:

1.初始化(邊界條件)

2.fori:=2ton(向后處理法)

或fori:=n-1to1(向前處理法)

對i階段的每一個決策點求局部最優(yōu)

3.確定和輸出結(jié)束狀態(tài)的值.

11一月202319

動態(tài)規(guī)劃算法的時間復雜度特性

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

以旅行路線問題為例，與使用搜索算法來比較：動態(tài)規(guī)劃算法搜索算法時間：T(n)=O(n2)T(n)=O(n!)

空間：S(n)=O(n2)S(n)=O(n)搜索算法的S(n)反而優(yōu)于動態(tài)規(guī)劃算法。選擇動態(tài)規(guī)劃算法是因為動態(tài)規(guī)劃算法在空間上可以承受，而搜索算法在時間上卻無法承受，所以我們舍空間而取時間。11一月2023201.多段圖問題描述（課本圖4.1）123458761110912st97324227111118654356524V1V2V3V4V54.1.2多段圖問題11一月2023211.多段圖問題描述（課本圖4.1）123458761110912st97324227111118654356524V1V2V3V4V54.1.2多段圖問題多段圖G＝(V,E)是—個帶權(quán)的有向圖。它具有如下特性：

圖中的結(jié)點被劃分成k≥2個不相交的集合Vi,1≤i≤k,其中V1和Vk分別只有一個結(jié)點s(源點)和t(匯點)。圖中所有的邊<u,v>的始點和終點都在兩個子集Vi和Vi+1中：即u∈Vi，v∈Vi+1,1≤i≤k,且每條邊<u,v>均附有成本c(u,v)。

從s到t的一條路徑成本是這條路徑上邊的成本和。多段圖問題(multistagegraphproblem)是求由s到t的最小成本路徑。11一月2023221.多段圖問題描述多段圖G＝(V,E)是—個帶權(quán)的有向圖。它具有如下特性：

圖中的結(jié)點被劃分成k≥2個不相交的集合Vi,1≤i≤k,其中V1和Vk分別只有一個結(jié)點s(源點)和t(匯點)。圖中所有的邊<u,v>的始點和終點都在兩個子集Vi和Vi+1中：即u∈Vi，v∈Vi+1,1≤i≤k,且每條邊<u,v>均附有成本c(u,v)。從s到t的一條路徑成本是這條路徑上邊的成本和。多段圖問題(multistagegraphproblem)是求由s到t的最小成本路徑。11一月202323假設(shè)s,v2,v3,…,vk-1,t是一條由s到t的最短路徑，還假設(shè)從源點s(初始狀態(tài))開始，已作出了到頂點vi的決策(初始決策)，因此vi

就是初始決策產(chǎn)生的狀態(tài)。若將vi看成是原問題的子問題的初始狀態(tài)，解這個子問題就是找一條由vi到t的最短路徑。這條最短路徑一定是vi,…,vk-1,t。否則，設(shè)vi,qi+1,…,qk-1,t是一條由vi到t的更短的路徑，則s,…,vi,qi+1,…,qk-1,t是一條由s到t的比s,…,vi,…,vk-1,t更短的路徑。與前面的假設(shè)矛盾。這說明多段圖問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，可以用動態(tài)規(guī)劃的方法求最優(yōu)解。sViVk-1t最短路經(jīng)最短路經(jīng)2.多段圖問題最優(yōu)化原理證明sViVk-1t最短路經(jīng)最短路經(jīng)qi+1

……甲丙乙11一月202324背包問題中的xj限定只能取0或1值，用KNAP(1,j,X)來表示這個問題效益值背包容量

則0/1背包問題就是KNAP(1,n,M)4.1.30/1背包問題1.背包問題描述:給定n種物品和一個容量為X的背包。物品i的重量是Wi，其價值為pi。假定將物品i的放入背包產(chǎn)生pixi的效益,應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？不許分割11一月2023252.0/1背包問題最優(yōu)化原理證明若y1,y2,…,yn是最優(yōu)解，則y2,y3,…,yn

將是0/1背包問題的子問題的最優(yōu)解。不然，若y2’,y3’,…,yn’是上式子問題的最優(yōu)解，且使得則y1,y2’

,y3’

,…,yn’將是原問題的可行解，并且使得max∑pixi并且∑wixi≤C-w1xi{0,1},i=2,…,n2≤i≤n2≤i≤n∑piy’i>∑piyi2≤i≤n2≤i≤np1y1+∑piy’i>∑piyi2≤i≤j1≤i≤jy1=0時,y2,y3,…,yn必為相對于C的最優(yōu)解;y1=1時,y2,y3,…,yn為相對于C-w1的最優(yōu)解.這與假設(shè)y1,y2,…,yn是最優(yōu)解相矛盾。因此，0/1背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)得以證明，可以用動態(tài)規(guī)劃的方法求最優(yōu)解。11一月202326設(shè)P(i,j)是一條從Vi中的節(jié)點j到匯點t的最小成本路徑，COST(i,j)表示這條路徑的成本，根據(jù)向前處理方法有公式4.5：因為，若<j,t>∈E成立,有COST(k-1,j)=c(j,t),若<j,t>∈E不成立，則有COST(k-1,j)=∞，所以可以通過如下步驟解式公式（4.5），并求出COST(1,s)。首先對于所有j∈Vk-2，計算COST(k-2,j)，然后對所有的j∈Vk-3，計算計算COST(k-3,j)等等，最后計算出計算COST(1,s)COST(i,j)=min{c(j,r)+COST(i+1,r)}r∈vi+1<j,r>∈E4.2多段圖4.2.1多段圖的向前處理算法

在實際應用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)化原理），則可以考慮用動態(tài)規(guī)劃解決。123458761110912st97324227111118654356524V1V2V3V4V511一月202327123458761110912st97324227111118654356524V1V2V3V4V5COST(4,9)=4COST(4,10)=2COST(4,11)=5實現(xiàn)步驟：123458761110912st97324227111118654356524V1V2V3V4V5123458761110912st97324227111118654356524V1V2V3V4V511109COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=78762345COST(2,2)=min{4+COST(3,6),2+COST(3,7),

1+COST(3,8)}=7COST(2,3)=min{2+COST(3,6),7+COST(3,7)}=9COST(2,4)=18COST(2,5)=151COST(1,1)=min{9+COST(2,2),7+COST(2,3),

3+COST(2,4),2+COST(2,5)}=16COST(4,9)=4COST(4,10)=2COST(4,11)=5COST(3,6)=7COST(3,7)=5COST(3,8)=7COST(2,2)=7COST(2,3)=9COST(2,4)=18COST(2,5)=15COST(i,j)=min{c(j,r)+COST(i+1,r)}r∈vi+1<j,r>∈E11一月202328例子中5段圖的實現(xiàn)計算步驟：COST(4,9)=4COST(4,10)=2COST(4,11)=5COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=7COST(2,2)=min{4+COST(3,6),2+COST(3,7),1+COST(3,8)}=7COST(2,3)=min{2+COST(3,6),7+COST(3,7)}=9COST(2,4)=18COST(2,5)=154.2.1多段圖的向前處理算法123458761110912st97324227111118654356524COST(1,1)=min{9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)}=1611一月20232911一月202330LineprocedureFGRAP(E,k,n,P) realCOST(n),integerD(n-1),P(k),r,j,k,n COST(n)0 forjn-1to1by–1do

設(shè)r是一個這樣的結(jié)點,<j,r>∈E且使c(j,r)+COST(r)取小值

COST(j)c(j,r)+COST(r) D(j)r repeat P(1)1;P(k)n forj2tok-1do P(j)D(P(j-1)) repeatEndFGRAPH計算出COST(j)的值，并找出一條最小成本路徑O(n+e)找出最小成本路徑上的第j個結(jié)點O(k)4.2.1多段圖的向前處理算法P(i,j)是一條從Vi中的結(jié)點j到t的最小成本路徑，COST(i,j)是這條路的成本。D(i,j)記錄了結(jié)點j的決策——使c(j,r)+COST(i+1,r)取最小值的j結(jié)點。當Vi+1中結(jié)點的編號均大于Vi中結(jié)點的編號，可省略第一下標。次序按遞減計算。COST(i,j)=min{c(j,r)+COST(i+1,r)}j∈vi,r∈vi+1<j,r>∈E11一月202331向后處理方法(backwardapproach)就是根據(jù)x1,…,xi-1的那些最優(yōu)決策序列列出求xi的遞推關(guān)系式。123458761110912st97324227111118654356524V1V2V3V4V54.2.2多段圖的向后處理算法11一月202332設(shè)BP(i,j)是一條由源點s到Vi中結(jié)點j的最小成本路徑，BCOST(i,j)表示BP(i,j)的成本，由向后處理方法得到如下公式：即由源點s到Vi中結(jié)點j的最小成本，等于由源點s到Vi-1中任一結(jié)點r

的最小成本加上Vi-1中結(jié)點r

到Vi中結(jié)點j的邊長,所得的所有和中最小的那個值。因為，若<1,j>∈E成立,BCOST(2,j)=c(1,j),若<1,j>∈E不成立，則有BCOST(2,j)=∞，所以可以通過如下步驟解式公式（4.6），首先對i＝3計算BCOST，然后對i＝4計算BCOST等，最后計算出BCOST(k，t)。BCOST(2，2)=9；BCOST(2，3)=7；BCOST(2，4)=3；BCOST(2，5)=2；BCOST(i,j)=min{BCOST(i-1,r)+c(r,j)}r∈vi-1<r,j>∈E4.2.2多段圖的向后處理算法123458761110912st9732422711111865435652411一月202333BCOST(3,6)=min{BCOST(2,2)+4,BCOST(2,3)+2}=9BCOST(3,7)=min{BCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11}=11BCOST(3,8)=min{BCOST(2,2)+1,BCOST(2,4)+11,BCOST(2,5)+8}=10123458761110912st973242271111186543565241632728V1V2V3V4V5BCOST(2，2)=9；BCOST(2，3)=7；BCOST(2，4)=3；BCOST(2，5)=2；BCOST(i,j)=min{BCOST(i-1,r)+c(r,j)}r∈vi-1<r,j>∈E11一月202334123458761110912st973242271111186543565241632728BCOST(4,9)=min{BCOST(3,6)+6,BCOST(3,7)+4}=15BCOST(4,10)=min{BCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5}=14BCOST(4,11)=1691011V1V2V3V4V5BCOST(2，2)=9；BCOST(2，3)=7；BCOST(2，4)=3；BCOST(2，5)=2；BCOST(3,6)=9BCOST(3,7)=11BCOST(3,8)=1011一月202335123458761110912st97324227111118654356524163272891011BCOST(5,12)=min{BCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5}=1612V1V2V3V4V5BCOST(2，2)=9；BCOST(2，3)=7；BCOST(2，4)=3；BCOST(2，5)=2；BCOST(3,6)=9BCOST(3,7)=11BCOST(3,8)=10BCOST(4,9)=15BCOST(4,10)=14BCOST(4,11)=1611一月202336

在計算每一個BCOST(i,j)的同時，記下每個狀態(tài)(結(jié)點j)所做出的決策(即,使BCOST(i-1,j)+c(m,j)取最小值的m

值),設(shè)為D(i,j)，則可容易地求出這條最小成本路徑。求這條最小成本路徑：4.2.2多段圖的向后處理算法11一月202337

對于實例中的最小成本路徑如下所示：

D(3,6)=3;D(3,7)=2;D(3,8)=2;D(4,9)=6;D(4,10)=6;D(4,11)=8;D(5,12)=10123458761110912st9732422711111865435652416327289101112V1V2V3V4V511一月202338LineprocedureBGRAP(E,k,n,P) realBCOST(n),integerD(n-1),P(k),r,j,k,n BCOST(1)0 forj2tondo

設(shè)r是一個這樣的結(jié)點，<r,j>∈E且使BCOST(r)+c(r,j)取小值

BCOST(j)BCOST(r)+c(r,j) D(j)r repeat P(1)1;P(k)n forjk-1to2by-1do P(j)D(P(j+1)) repeatEndBGRAPH計算出BCOST(j)的值，并找出一條最小成本路徑找出最小成本路徑上的第j個結(jié)點4.2.2多段圖的向后處理算法時間復雜性問題11一月202339補4.3資源分配問題4.3.1問題描述設(shè)資源總數(shù)為m，工程的個數(shù)為n，給每項工程分配的資源數(shù)額不同，所獲得的利潤也不同。在給定各工程的資源利潤表和資源總數(shù)，怎樣分配資源，才能獲得最大利潤呢？這個問題的實質(zhì)是要求能夠給出資源總數(shù)a的一個劃分x1,x2,…,xn，0≤xi≤m，且x1+x2+…+xn≤m，使得利潤G(a)=G1(x1)+G2(x2)+…+Gn(xn)最大。這里Gi(xi)是把資源數(shù)xi分配給第i項工程的最大利潤，1≤i≤n，Gi(x)是給定的已知函數(shù)。討論將有限資源分配給若干個工程的問題。11一月202340fn(x)={Gn(xn)+fn-1(x-xn)}

這樣，一個資源分配問題就轉(zhuǎn)化為可用動態(tài)規(guī)劃求解的多段決策過程。f3(x)={G3(x3)+f2(x-x3)}......f1(x)={G1(x1)}f2(x)={G2(x2)+f1(x-x2)}4.3.2解決方案在Gi(x)并非x的線性函數(shù)時，我們可以利用動態(tài)規(guī)劃求解最佳分配方案。用fi(x)表示對前1項，前2項，…，前i項工程投資x時的最大利潤，那么

11一月2023414.3.3實例例有資金6萬元，擬投資A、B和C三種產(chǎn)品，利潤函數(shù)G(x)的值給定如下表。求最佳投資方案。投資利潤表單位：萬元xi

0123456GA(x1)01.21.51.852.42.83.3GB(x1)01.82.02.252.42.52.6GC(x1)0

1.31.92.22.452.73.0①只投資一種產(chǎn)品，根據(jù)上表可知投入A獲利最大。f1(x)=max{GA(x)}=f1(6)=3.311一月202342②考慮投資A和B兩種產(chǎn)品，根據(jù)

f2(x)={GB(x2)+f1(x-x2)｝得下表：x2

m0123456f2(m)00011.21.81.821.53.02.03.031.853.33.22.253.342.43.653.53.452.43.6552.84.23.853.753.62.54.263.34.64.44.13.93.72.64.6各種投資額對第二種產(chǎn)品的各種投資額對投資兩種產(chǎn)品時的利潤此時為0：不給B投資，只給A投資，等于表1欄GA(x)總額a=4,即B投資1萬，而A投資3萬時的利潤。即1.85+1.8=3.65所以，只對A和B兩種產(chǎn)品投資時，產(chǎn)生的最大利潤是4.6萬元。

f2(x)=max{GB(x2)+f1(x-x2)}=GB(1)+f1(5)=1.8+2.8=4.644xi

0123456GA(x1)01.21.51.852.42.83.3GB(x1)01.82.02.252.42.52.6GC(x1)0

1.31.92.22.452.73.011一月202343x2

m0123456f2(m)00011.21.81.821.53.02.03.031.853.33.22.253.342.43.653.53.452.43.6552.84.23.853.753.62.54.263.34.64.44.13.93.72.64.6所以，只對A和B兩種產(chǎn)品投資時，產(chǎn)生的最大利潤是4.6萬元。

f2(x)=max{GB(x2)+f1(x-x2)}=GB(1)+f1(5)=1.8+2.8=4.611一月202344③考慮投資A、B和C三種產(chǎn)品，根據(jù)

f3(x)={GC(x3)+f2(x-x3)}由表1和表2可以求得表3

：x3

0123456GC(x3)0

1.31.92.22.452.73.0f2(6-x3)

4.6

4.2

3.653.33.01.80f3(6)4.65.55.555.55.454.53.0可得

f3(x)=max{GC(x3)+f2(m-x3)}=GC(2)+f2(4)=GC(2)+(GB(1)+GA(3))=1.9+(1.8+1.85)=5.55由此得出獲得最大利潤的方案為:對A產(chǎn)品投資3萬元，對B產(chǎn)品投資1萬元，對C產(chǎn)品投資2萬元。11一月2023454.3.4算法描述設(shè)投資總額為m，工程個數(shù)為n，對工程i投資j的利潤G(i,j)已知，1≤i≤n，0≤j≤m。用AM表示總利潤，x[i]表示對工程i的資源分配結(jié)果，1≤i≤n，F(xiàn)[i,j]表示fi(j)的最大利潤,P[i,j]表示使fi(j)最大時，給第i項工程的資源數(shù)。有限資源的最佳分配算法如下。①生成表1——O(n)②生成表2、3——O(m2·n)③其它——O(n)11一月202346算法：有限資源最佳分配

PROCEDUREALLOT（m，n，AM，x）；1fori←0tomdo//初始化

F[1,i]←G[1,i]；P[1,i]←irepeat2W[1]←max{F[1,0],F[1,1],...,F[1,m]}；3Q[1]←k；//k是F[1,k］中最大值的下標4fori←2tondoF[i,0]←G[i,0]＋F[i-1,0]；//生成表2的第1列

P[i,0]←0；

forj←1tomdo//生成表2的其他列,包括表3

設(shè)k是使得G[i,k]+F[i-1,j-k]取最大值(0≤k≤j)；

F[i,j]←G[i,k]+F[i-1,j-k]；7P[i,j]←k；

repeat8

W[j]←max{F[i,0],F[i,2]，…，F(xiàn)[i,m]}；9Q[i]←r；｛r使F[i，r]=W[i]｝

repeat

這兩句可計算出F[i,j]，它是投資j給前i項工程的最佳方案。計算對前i項工程投資的最大收益，F(xiàn)[i,r]是最佳方案。G(i,j)對工程i投資j的利潤G(i,j)已知，1≤i≤n，0≤j≤m。x[i]表示對工程i的資源分配結(jié)果，1≤i≤n，F(xiàn)[i,j]表示fi(j)的最大利潤,P[i,j]表示使fi(j)最大時，給第i項工程的資源數(shù)。11一月20234710AM←max｛W[1],W[2],…,W[n]｝；//計算最大利潤//11設(shè)s是使AM取最大的W[s]的下標;//找出對各項工程的投資數(shù)12ifs≠nthenfori←s＋1tondox[i]←0repeatendif13x[s］←P[s,Q[s]]；14j←m-x[s]；15fori←s-1to1by-1dox[i]←P[i,j]；j←j-x[i]repeatend｛ALLOT｝定理:算法ALLOT能在O(m2·n)的時間內(nèi)找出資源的最佳分配方案。

可用歸納法證明其算法的正確性G(i,j)對工程i投資j的利潤G(i,j)已知，1≤i≤n，0≤j≤m。x[i]表示對工程i的資源分配結(jié)果，1≤i≤n，F(xiàn)[i,j]表示fi(j)的最大利潤,P[i,j]表示使fi(j)最大時，給第i項工程的資源數(shù)。11一月202348背包問題中的xj限定只能取0或1值，用KNAP(1,j,X)來表示這個問題效益值背包容量

則0/1背包問題就是KNAP(1,n,M)4.40/1背包問題4.4.10/1背包問題——問題描述11一月202349若y1,y2,…,yn是最優(yōu)解，則y2,y3,…,yn

將是0/1背包問題的子問題的最優(yōu)解。不然，若y2’,y3’,…,yn’是上式子問題的最優(yōu)解，且使得則y1,y2’

,y3’

,…,yn’將是原問題的可行解，并且使得這與假設(shè)y1,y2,…,yn是最優(yōu)解相矛盾。因此，0/1背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)得以證明，可以用動態(tài)規(guī)劃的方法求最優(yōu)解。2.0/1背包問題最優(yōu)化原理證明max∑pixi并且∑wixi≤C-w1xi{0,1},i=2,…,n2≤i≤n2≤i≤n∑piy’i>∑piyi2≤i≤n2≤i≤np1y1+∑piy’i>∑piyi2≤i≤j1≤i≤jy1=0時,y2,y3,…,yn必為相對于C的最優(yōu)解;y1=1時,y2,y3,…,yn為相對于C-w1的最優(yōu)解.11一月202350根據(jù)問題描述，可通過作出變量x1,x2,…,xn的一個決策序列來得到它的解。假定決策x的次序為x1,x2,…,xn,則在對x1作出決策后，問題處于下列兩種狀態(tài)：X1=0,背包的剩余容量為M，沒有產(chǎn)生任何效益X1=1,背包剩余容量為M-w1，效益值增加了p1顯然，剩下來對x2,…,xn的決策相對于決策了x1后所產(chǎn)生的問題狀態(tài)應該是最優(yōu)的，否則，x1,x2,…,xn就不可能是最優(yōu)的決策序列。4.4.20/1背包問題——解決方法使用向后處理法求解。用背包剩余空間來決策的思想沒有放入背包放入背包11一月2023514.4.20/1背包問題——解決方法設(shè)fi(y)是KNAP(1,i,y)最優(yōu)解的值則fn(M)(KNAP(1,n,M))可表示為：

fn(M)=max{fn-1(M),fn-1(M-wn)+pn

}則對于任意的fi(y)(KNAP(1,i,y))可表示公式4.14為：

fi(y)=max{fi-1(y),fi-1(y-wi)+pi

}這里i>0,0≤y≤M,不放入的決策放入的決策注意y的含義！fi(y)fi-1(y)pi11一月202352為了能由前向后遞推而最后求解出fn(M),須從f0(y)開始對于所有的y≥0，有

f0(y)=0；當y<0時，有

f0(y)=-∞

根據(jù)遞推關(guān)系式，馬上可求出0≤y<w1和y≥w1情況下的f1(y)的值，以及f2,…,fn的值。y是相對于背包的剩余空間11一月202353設(shè)初始值f0(X)