動(dòng)態(tài)規(guī)劃基礎(chǔ)詳解(二)概要

1動(dòng)態(tài)規(guī)劃—一些應(yīng)用實(shí)例2要點(diǎn):駕馭動(dòng)態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題性質(zhì)駕馭設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計(jì)算出最優(yōu)值。(4)依據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。3通過應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略。（1）矩陣連乘問題；（2）最大子段和（3）凸多邊形最優(yōu)三角剖分；（4）多邊形游戲；（5）圖像壓縮；（6）電路布線；（7）流水作業(yè)調(diào)度；（8）最優(yōu)二叉搜尋樹。4矩陣連乘問題給定n個(gè)矩陣，其中與是可乘的，?？疾爝@n個(gè)矩陣的連乘積由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有很多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積5（1）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積是完全加括號(hào)的，則可表示為2個(gè)完全加括號(hào)的矩陣連乘積和的乘積并加括號(hào)，即16000,10500,36000,87500,34500完全加括號(hào)的矩陣連乘積可遞歸地定義為：設(shè)有四個(gè)矩陣，它們的維數(shù)分別是：總共有五中完全加括號(hào)的方式完全加括號(hào)的矩陣連乘積6矩陣連乘問題給定n個(gè)矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1，2…，n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積須要的數(shù)乘次數(shù)最少。窮舉法：列舉出全部可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)須要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。算法復(fù)雜度分析：對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問題：(A1...Ak)(Ak+1…An)可以得到關(guān)于P(n)的遞推式如下：7矩陣連乘問題窮舉法動(dòng)態(tài)規(guī)劃將矩陣連乘積簡記為A[i:j]，這里i≤j考察計(jì)算A[i:j]的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j，則其相應(yīng)完全加括號(hào)方式為計(jì)算量：A[i:k]的計(jì)算量加上A[k+1:j]的計(jì)算量，再加上A[i:k]和A[k+1:j]相乘的計(jì)算量8特征：計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優(yōu)的。矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。分析最優(yōu)解的結(jié)構(gòu)9建立遞歸關(guān)系設(shè)計(jì)算A[i:j]，1≤i≤j≤n，所須要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為m[1,n]當(dāng)i=j時(shí)，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n當(dāng)i<j時(shí)，可以遞歸地定義m[i,j]為：這里的維數(shù)為

的位置只有種可能10計(jì)算最優(yōu)值對(duì)于1≤i≤j≤n不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問題。因此，不同子問題的個(gè)數(shù)最多只有由此可見，在遞歸計(jì)算時(shí)，很多子問題被重復(fù)計(jì)算多次。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。用動(dòng)態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題答案。每個(gè)子問題只計(jì)算一次，而在后面須要時(shí)只要簡潔查一下，從而避開大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法11用動(dòng)態(tài)規(guī)劃法求最優(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++)for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[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]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}A1A2A3A4A5A63035351515551010202025算法困難度分析：算法matrixChain的主要計(jì)算量取決于算法中對(duì)r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間明顯為O(n2)。12凸多邊形最優(yōu)三角剖分用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P={v0,v1,…,vn-1}表示具有n條邊的凸多邊形。若vi與vj是多邊形上不相鄰的2個(gè)頂點(diǎn)，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個(gè)多邊形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。13三角剖分的結(jié)構(gòu)及其相關(guān)問題一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹，稱為表達(dá)式的語法樹。例如，完全加括號(hào)的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應(yīng)的語法樹如圖(a)所示。凸多邊形{v0,v1,…vn-1}的三角剖分也可以用語法樹表示。例如，圖(b)中凸多邊形的三角剖分可用圖(a)所示的語法樹表示。矩陣連乘積中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，i<j，對(duì)應(yīng)于矩陣連乘積A[i+1:j]。14最優(yōu)子結(jié)構(gòu)性質(zhì)凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實(shí)上，若凸(n+1)邊形P={v0,v1,…,vn}的最優(yōu)三角剖分T包含三角形v0vkvn，1≤k≤n-1，則T的權(quán)為3個(gè)部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形{v0,v1,…,vk}和{vk,vk+1,…,vn}的權(quán)之和?？梢詳嘌?，由T所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衶v0,v1,…,vk}或{vk,vk+1,…,vn}的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的沖突。15最優(yōu)三角剖分的遞歸結(jié)構(gòu)定義t[i][j]，1≤i<j≤n為凸子多邊形{vi-1,vi,…,vj}的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。為便利起見，設(shè)退化的多邊形{vi-1,vi}具有權(quán)值0。據(jù)此定義，要計(jì)算的凸(n+1)邊形P的最優(yōu)權(quán)值為t[1][n]。t[i][j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。當(dāng)j-i≥1時(shí)，凸子多邊形至少有3個(gè)頂點(diǎn)。由最優(yōu)子結(jié)構(gòu)性質(zhì)，t[i][j]的值應(yīng)為t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的權(quán)值，其中i≤k≤j-1。由于在計(jì)算時(shí)還不知道k的精確位置，而k的全部可能位置只有j-i個(gè)，因此可以在這j-i個(gè)位置中選出訪t[i][j]值達(dá)到最小的位置。由此，t[i][j]可遞歸地定義為：16多邊形游戲多邊形游戲是一個(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連接著的2個(gè)頂點(diǎn)V1和V2；(2)用一個(gè)新的頂點(diǎn)取代邊E以及由E連接著的2個(gè)頂點(diǎn)V1和V2。將由頂點(diǎn)V1和V2的整數(shù)值通過邊E上的運(yùn)算得到的結(jié)果賜予新頂點(diǎn)。最終，全部邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。問題:對(duì)于給定的多邊形，計(jì)算最高得分。17最優(yōu)子結(jié)構(gòu)性質(zhì)在所給多邊形中，從頂點(diǎn)i(1≤i≤n)起先，長度為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]處將鏈分割為2個(gè)子鏈p(i，s)和p(i+s，j-s)。設(shè)m1是對(duì)子鏈p(i，s)的隨意一種合并方式得到的值，而a和b分別是在全部可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的隨意一種合并方式得到的值，而c和d分別是在全部可能的合并中得到的最小值和最大值。依此定義有a≤m1≤b，c≤m2≤d(1)當(dāng)op[i+s]='+'時(shí)，明顯有a+c≤m≤b+d(2)當(dāng)op[i+s]='*'時(shí)，有min{ac，ad，bc，bd}≤m≤max{ac，ad，bc，bd}換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。18圖像壓縮圖象的變位壓縮存儲(chǔ)格式將所給的象素點(diǎn)序列{p1,p2,…,pn},0≤pi≤255分割成m個(gè)連續(xù)段S1,S2,…,Sm。第i個(gè)象素段Si中(1≤i≤m)，有l(wèi)[i]個(gè)象素,且該段中每個(gè)象素都只用b[i]位表示。設(shè)則第i個(gè)象素段Si為設(shè)，則hib[i]8。因此須要用3位表示b[i],假如限制1l[i]255，則須要用8位表示l[i]。因此，第i個(gè)象素段所需的存儲(chǔ)空間為l[i]*b[i]+11位。按此格式存儲(chǔ)象素序列{p1,p2,…,pn}，須要位的存儲(chǔ)空間。

圖象壓縮問題要求確定象素序列{p1,p2,…,pn}的最優(yōu)分段，使得依此分段所需的存儲(chǔ)空間最少。每個(gè)分段的長度不超過256位。19圖像壓縮設(shè)l[i]，b[i]，是{p1,p2,…,pn}的最優(yōu)分段。自不待言，l[1]，b[1]是{p1,…,pl[1]}的最優(yōu)分段，且l[i]，b[i]，是{pl[1]+1,…,pn}的最優(yōu)分段。即圖象壓縮問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè)s[i]，1≤i≤n，是象素序列{p1,…,pn}的最優(yōu)分段所需的存儲(chǔ)位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)易知：其中算法困難度分析：由于算法compress中對(duì)k的循環(huán)次數(shù)不超這256，故對(duì)每一個(gè)確定的i，可在時(shí)間O(1)內(nèi)完成的計(jì)算。因此整個(gè)算法所需的計(jì)算時(shí)間為O(n)。20電路布線在一塊電路板的上、下2端分別有n個(gè)接線柱。依據(jù)電路設(shè)計(jì)，要求用導(dǎo)線(i,π(i))將上端接線柱與下端接線柱相連，如圖所示。其中π(i)是{1,2,…,n}的一個(gè)排列。導(dǎo)線(i,π(i))稱為該電路板上的第i條連線。對(duì)于任何1≤i<j≤n，第i條連線和第j條連線相交的充分且必要的條件是π(i)>π(j)。電路布線問題要確定將哪些連線支配在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導(dǎo)線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。21記。N(i,j)的最大不相交子集為MNS(i,j)。Size(i,j)=|MNS(i,j)|。(1)當(dāng)i=1時(shí)，(2)當(dāng)i>1時(shí)，2.1j<π(i)。此時(shí)，。故在這種狀況下，N(i,j)=N(i-1,j)，從而Size(i,j)=Size(i-1,j)。2.2j≥π(i)，(i,π(i))∈MNS(i,j)。則對(duì)隨意(t,π(t))∈MNS(i,j)有t<i且π(t)<π(i)。在這種狀況下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。2.3若，則對(duì)隨意(t,π(t))∈MNS(i,j)有t<i。從而。因此，Size(i,j)≤Size(i-1,j)。另一方面，故又有Size(i,j)≥Size(i-1,j)，從而Size(i,j)=Size(i-1,j)。電路布線(1)當(dāng)i=1時(shí)(2)當(dāng)i>1時(shí)22流水作業(yè)調(diào)度n個(gè)作業(yè){1，2，…，n}要在由2臺(tái)機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的依次都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi。流水作業(yè)調(diào)度問題要求確定這n個(gè)作業(yè)的最優(yōu)加工依次，使得從第一個(gè)作業(yè)在機(jī)器M1上起先加工，到最終一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少。分析：直觀上，一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器M1沒有空閑時(shí)間，且機(jī)器M2的空閑時(shí)間最少。在一般狀況下，機(jī)器M2上會(huì)有機(jī)器空閑和作業(yè)積壓2種狀況。設(shè)全部作業(yè)的集合為N={1，2，…，n}。SN是N的作業(yè)子集。在一般狀況下，機(jī)器M1起先加工S中作業(yè)時(shí)，機(jī)器M2還在加工其它作業(yè)，要等時(shí)間t后才可利用。將這種狀況下完成S中作業(yè)所需的最短時(shí)間記為T(S,t)。流水作業(yè)調(diào)度問題的最優(yōu)值為T(N,0)。23流水作業(yè)調(diào)度設(shè)是所給n個(gè)流水作業(yè)的一個(gè)最優(yōu)調(diào)度，它所需的加工時(shí)間為a(1)+T’。其中T’是在機(jī)器M2的等待時(shí)間為b(1)時(shí)，支配作業(yè)(2)，…，(n)所需的時(shí)間。記S=N-{(1)}，則有T’=T(S,b(1))。證明：事實(shí)上，由T的定義知T’T(S,b(1))。若T’>T(S,b(1))，設(shè)’是作業(yè)集S在機(jī)器M2的等待時(shí)間為b(1)狀況下的一個(gè)最優(yōu)調(diào)度。則(1)，’(2)，…，’(n)是N的一個(gè)調(diào)度，且該調(diào)度所需的時(shí)間為a(1)+T(S,b(1))<a(1)+T’。這與是N的最優(yōu)調(diào)度沖突。故T’T(S,b(1))。從而T’=T(S,b(1))。這就證明白流水作業(yè)調(diào)度問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。由流水作業(yè)調(diào)度問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，24Johnson不等式對(duì)遞歸式的深化分析表明，算法可進(jìn)一步得到簡化。設(shè)是作業(yè)集S在機(jī)器M2的等待時(shí)間為t時(shí)的任一最優(yōu)調(diào)度。若(1)=i,(2)=j。則由動(dòng)態(tài)規(guī)劃遞歸式可得:T(S,t)=ai+T(S-{i},bi+max{t-ai,0})=ai+aj+T(S-{i,j},tij)其中，假如作業(yè)i和j滿足min{bi,aj}≥min{bj,ai}，則稱作業(yè)i和j滿足Johnson不等式。25流水作業(yè)調(diào)度的Johnson法則交換作業(yè)i和作業(yè)j的加工依次，得到作業(yè)集S的另一調(diào)度，它所需的加工時(shí)間為T’(S,t)=ai+aj+T(S-{i,j},tji)其中，當(dāng)作業(yè)i和j滿足Johnson不等式時(shí)，有由此可見當(dāng)作業(yè)i和