課件算法第六次

1第六章動態(tài)規(guī)劃(DynamicProgramming)6.1動態(tài)規(guī)劃方法的基本步驟描述問題的最優(yōu)解(optimalsolution)結(jié)構(gòu)特征遞歸定義最優(yōu)解值自底向上計算最優(yōu)解值從已計算得到的最優(yōu)解值信息中構(gòu)造最優(yōu)解26.2裝配線調(diào)度問題(Assembly-lineScheduling)問題的提出

S1,1S1,2S1,n

line1進(jìn)入退出

line2

S2,1S2,2S2,n其中：Si,j表示第i條裝配線中第j個裝配站，i=1,2,…..,n ai,j表示在第i條裝配線、第j個裝配站裝配某個部件所需的時間 ti,j表示從裝配線i、裝配站j切換到裝配線j所需的時間

ei表示進(jìn)入裝配線i所需的時間

xi表示退出裝配線i所需的時間問題是如何找一條從開始到退出的最快路線？（如圖15-2，P193）a11a12a1na21a22a2nt11t21t12t22t1n-1t2n-1x1x2e1e232.枚舉法求解3.動態(tài)規(guī)劃方法求解step1:描述問題的最優(yōu)解結(jié)構(gòu)特征觀察從開始到某個裝配站S1,j的最優(yōu)路線①ifj=1then從開始到S1,1只有一條路線②ifj=2then從開始到S1,2有兩條路線，一條是S1,1直接到達(dá)S1,2，另一條是從S2,1切換到達(dá)S1,2。同理可知，從開始到S1,j也只有兩條路線，一條是從S1,j-1直接到達(dá)，另一條是從S2,j-1切換到達(dá)。那么從開始到達(dá)S1,j的最優(yōu)解結(jié)構(gòu)特征是什么呢？分析如下：假設(shè)從開始到S1,j的一條最優(yōu)路線是從開始到S1,j-1再直接到達(dá)S1,j的，那么子路徑P1從開始到S1,j-1也一定是最優(yōu)的。4proof:（采用cutandpaste方法證明）

∵如果子路徑P1從開始到S1,j-1不是最優(yōu)的，那么一定存在一條從開始到S1,j-1的更優(yōu)子路徑P2，當(dāng)用P2去替換原子路徑P1后，將得到一條比原路徑更優(yōu)的路線，這與假設(shè)從開始到S1,j是一條最優(yōu)路線矛盾。

∴子路徑P1一定也是最優(yōu)的同理可知，若從開始到S1,j的一條最優(yōu)路線是從開始到S2,j-1再切換到達(dá)S1,j的，那么子路徑從開始到S2,j-1也一定是最優(yōu)的。5以上這種最優(yōu)解結(jié)構(gòu)特征有稱為最優(yōu)子結(jié)構(gòu)(optimalsubstructure)性質(zhì)，即如果問題的解是最優(yōu)的，則所有子問題的解也是最優(yōu)的。step2：遞歸定義最優(yōu)路線的最快時間令fi[j]為經(jīng)過裝配站Si,j的最快時間則f1[n]表示經(jīng)過裝配站S1,n的最快時間則f2[n]表示經(jīng)過裝配站S2,n的最快時間∴從開始進(jìn)入到退出的最快時間為：

f*=min(f1[n]+x1，f2[n]+x2)要得到f*值，需要計算fi[j]的每個值

f1[j]=min{f1[j-1]+a1,j，f2[j-1]+t2,j-1+a1,j} f2[j]=min{f2[j-1]+a2,j，f1[j-1]+t1,j-1+a2,j}6遞歸初始值為：

f1[1]=e1+a1,1

f2[1]=e2+a2,1step3：自底向上計算最快時間先確定此問題的底，然后再自底向上計算最優(yōu)解值算法Fastest-Way見書P196。容易看出該算法的時間為Θ(n)。step4：構(gòu)造最優(yōu)解結(jié)構(gòu)（輸出最優(yōu)路線）算法Print-Station見書P196。76.3矩陣鏈乘(Matrix-chainMultiplication)問題的提出給定一個矩陣序列<A1,A2,…,An>，其中矩陣Ai的維數(shù)為Pi-1×Pi，要求計算A1×A2×…×An矩陣鏈乘的乘法次數(shù)最少？例：四個矩陣相乘A1×A2×A3×A4的鏈乘順序有：

(A1(A2(A3A4))) 又稱為矩陣完全加括號形式 (A1((A2A3)A4)) fullyparenthesized ((A1A2)(A3A4)) ((A1(A2A3))A4) (((A1A2)A3)A4)共有五種鏈乘順序8例：假設(shè)有三個矩陣A1×A2×A3，其中矩陣的維數(shù)為：10×100，100×5，5×50。對于矩陣鏈乘問題首先檢查枚舉法是否可行？2.動態(tài)規(guī)劃方法求解此問題step1:問題的最優(yōu)子結(jié)構(gòu)假設(shè)子問題Aij的解(AiAi+1…Aj)是一個最優(yōu)解，則在Aij中一定存在一個最佳分裂點k(i≤k<j)，使得子鏈Aik和Ak+1j的解(AiAi+1…Ak)和(Ak+1…Aj)也是最優(yōu)的。9proof:cutandpaste方法證明

假設(shè)子鏈Aik=(AiAi+1…Ak)不是最優(yōu)的完全加括號形式，則一定存在一種更優(yōu)的完全加括號形式Aik’=(AiAi+1…Ak),使得Aik’的乘法次數(shù)比Aik更少，即|Aik’|<|Aik|，那么當(dāng)我們用Aik’去替換Aik后將得到一個比原問題Aij更少乘法的完全加括號形式。即：原最優(yōu)解Aij

=((Aik)(Ak+1j))，乘法次數(shù)為|Aij|=|Aik|+|Ak+1j|

+Pi-1×Pk×Pj

新的解Aij’=((Aik’)(Ak+1j))，乘法次數(shù)為|Aij’|=|Aik’|+|Ak+1j|+Pi-1×Pk×Pj∵|Aik’|<|Aik|∴|Aij’|<|Aij|，這與Aij最優(yōu)是矛盾的∴子鏈Aik一定是最優(yōu)的同理可證子鏈Ak+1j也一定是最優(yōu)的10step2:遞歸定義最優(yōu)解值令m[i,j]存放子鏈Aij=(AiAi+1…Aj)的乘法次數(shù)則m[1,n]表示所有n個矩陣鏈乘的乘法次數(shù)∵if

i=jthen只有一個矩陣∴m[i,i]=0，i=1,2….n∵ifi<jthen根據(jù)矩陣鏈乘的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，此時存在一個最佳分裂點k，使得Aij可分裂為二個子鏈

Aik和

Ak+1j∴m[i,j]=m[i,k]+m[k+1,j]+Pi-1×Pk×Pj∵原問題是求最少的乘法次數(shù)11step3:自底向上計算最優(yōu)解值 matrix-chain-order(P) nlength[p]-1 fori1ton dom[i,i]0 forl=2ton //l為鏈長 dofori1ton-l+1 //具有n-l+1個鏈長為l的組合 doji+l-1 m[i,j]∞

forkitoj-1 //找最佳分裂點k doqm[i,k]+m[k+1,j]+Pi-1PkPj ifq<m[i,j] thenm[i,j]q s[i,j]k //記錄最佳分裂點 returnmands12算法時間分析：∵算法matrix-chain-order包含三重循環(huán)又∵每重循環(huán)的次數(shù)≤n∴算法時間為O(n3)。step4:輸出最優(yōu)解結(jié)構(gòu)算法見書P201根據(jù)S數(shù)組記錄的最佳分裂點k值可構(gòu)造出n個矩陣鏈乘的最優(yōu)加括號形式如書P200，圖15－3所示。136.4動態(tài)規(guī)劃的要素最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)是應(yīng)用動態(tài)規(guī)劃方法的必要前提，即所解問題必須具有最優(yōu)子結(jié)構(gòu)性質(zhì)才能用動態(tài)規(guī)劃方法求解。所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指一個問題的最優(yōu)解中所包含的所有子問題的解都是最優(yōu)的。對于一個問題發(fā)現(xiàn)其最優(yōu)子結(jié)構(gòu)性質(zhì)的幾個因素：①檢查問題的解所面臨的選擇②假定某種選擇為一最優(yōu)解③分析這種選擇將產(chǎn)生多少子問題④證明子問題的解也是最優(yōu)的14最優(yōu)子結(jié)構(gòu)的細(xì)節(jié)問題：特別需要指出的是當(dāng)問題本身不具有最優(yōu)子結(jié)構(gòu)性質(zhì)時不能濫用最優(yōu)子結(jié)構(gòu)性質(zhì)。例如：對于一個有向圖G=(V,E).如果問題是找圖G中頂點u,v∈V的最短路徑152.重疊子問題雖然問題分解后是否存在重疊子問題不是應(yīng)用動態(tài)規(guī)劃方法的必要前提，但存在重疊子問題應(yīng)用動態(tài)規(guī)劃方法可以提高算法效率。Recursive-matrix-chain(P,i,j)

ifi=jthenreturn0 m[i,j]∞

forkitoj doqRecursive-matrix-chain(P,i,k) +Recursive-matrix-chain(P,k+1,j)+Pi-1PkPj ifq<m[i,j] thenm[i,j]q returnm[i,j]1617183.記憶法(Memorization)記憶法是動態(tài)規(guī)劃方法的一種變