算法設計與分析第四章動態規劃目錄概述（基本思想、解題步驟、基本要素）矩陣連乘問題凸多邊形最優三角剖分最長公共子序列問題加工順序問題0-1背包問題最優二叉查找樹教學目標理解動態規劃的思想掌握動態規劃、分治法及貪心法的異同掌握動態規劃的基本要素掌握動態規劃的設計步驟通過實例學習，掌握動態規劃設計的策略動態規劃應用應用領域：經濟管理、生產調度、工程技術和最優控制等方面如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題主要用于求解以時間劃分階段的動態過程的優化問題。動態規劃算法通常用于求解具有某種最優性質的問題。

動態規劃動態規劃的基本思想。動態規劃解題步驟。動態規劃基本要素。矩陣連乘問題問題：給定n個矩陣{A1,A2,A3,…,An}，其中Ai與Ai+1(i=1,2,3,…,n-1)是可乘的。用加括號的方法表示矩陣連乘的次序，不同加括號的方法所對應的計算次序是不同的。找出一種最優的計算次序，使得n個矩陣元素相乘的次數最小。實例：A1（10×100）、A2（100×5）、A3（5×50）窮舉算法A1(A2A3)乘法次數：100×50×5+10×50×100=75000(A1A2)A3乘法次數：10×5×100+10×50×5=7500窮舉算法是否可行？n個矩陣連乘，計算次序有多少種？（少則可行，太多則不可行）n=1，不用運算，1種計算次序n=2，有1種計算次序n=3，有2種計算次序n=4，A1|A2A3A4A1A2|A3A4

A1A2A3|A4

121121共5中計算次序窮舉算法是否可行？n=5，A1|A2A3A4A5

A1A2|A3A4A5

1512

A1A2A3|A4A5

A1A2A3A4|A52151共5+2+2+5=14種由此，我們可以得到計算次序數，用p(n)表示，則p(n)的表達式為：著名的Catalan數卡特蘭數是組合數學中一個常出現在各種計數問題中的數列。以比利時的數學家歐仁·查理·卡塔蘭(1814–1894)的名字來命名。Catalan數的定義令h(1)=1，Catalan數滿足遞歸式：h(n)=h(1)*h(n-1)+h(2)*h(n-2)+...+h(n-1)h(1)n>=2該遞推關系的解為：h(n)=C(2n-2,n-1)/n，n=1,2,3,...（其中C(2n-2,n-1)表示2n-2個中取n-1個的組合數）動態規劃算法n個矩陣連乘問題是最優性質的問題。把它劃分為與時間相關的多個階段規模為1時，不用運算，初始狀態，乘法次數為0第一個階段：依據初始狀態，計算2個矩陣相乘的最少乘法次數，做出決策。第二個階段：依據第一階段計算的結果計算3個矩陣相乘的最少乘法次數，做決策。以此類推，直到最后一個階段得到n個矩陣連乘最少計算次數，做決策。實例：求A1（3×2）、A2（2×5）、A3（5×10）、A4（10×2）和A5（2×3）最佳計算次序m[i][j]A1A2A3A4A5s[i][j]A1A2A3A4A5A1030160132150A101111A20100120132A20224A30100130A3034A4060A404A50A50A1|A2A3100+2×10×3=160A1A2|A330+3×5×10=180A2|A3A4100+5×2×2=120

A2A3|A4100+2×10×2=140A3|A4A560+10×3×5=210

A3A4|A5100+5×2×3=130A1|A2A3A4120+3×2×2=132A1A2|A3A430+100+5×2×3=160A1A2A3|A4160+3×10×2=220A2|A3A4A5130+2×5×3=160A2A3|A4A5100+60+2×10×3=220A2A3A4|A5120+2×2×3=132A1|A2A3A4A5132+3×2×3=150A1A2|A3A4A530+130+3×5×3=205A1A2A3|A4A5160++60+3×10×3=310A1A2A3A4|A5132+3×2×3=150A1（（A2（A3A4））A5）動態規劃的基本思想（1）經分解得到的各個子問題往往不是相互獨立的。比如:A1A2A3與A2A3A4有共同的子問題A2A3（2）在求解過程中，將已解決的子問題的最優值進行保存，在需要時可以輕松找出。（3）通常采用表的形式記錄子問題的最優值，即在實際求解過程中，一旦某個子問題被計算過，不管該問題以后是否用得到，都將其計算結果填入該表，需要的時候就從表中找出該子問題的最優值。（4）根據最優值，記錄最優決策，構造最優解。動態規劃的解題步驟（1）分析最優解的性質，刻畫最優解的結構特征——考察是否適合采用動態規劃法。（2）遞歸定義最優值（即建立遞歸式或動態規劃方程）。（3）以自底向上的方式計算出最優值，并記錄相關信息。（4）根據計算最優值時得到的信息，構造出最優解。動態規劃的基本要素最優子結構性質子問題重疊性質自底向上的求解方式小結動態規劃的基本思想。動態規劃解題步驟。動態規劃基本要素。矩陣連乘最優子結構性質分析設：Ai(pi×qi）設n個矩陣連乘的最佳計算次序為（A1A2…Ak）(Ak+1Ak+2…An)，則（A1A2…Ak）連乘的計算次序一定是最優的，(Ak+1Ak+2…An)連乘的計算次序也一定是最優的。反證法：假設（A1A2…Ak）連乘的計算次序不是最優的，或(Ak+1Ak+2…An)連乘的計算次序不是最優的。令a：（A1A2…Ak）連乘的乘法次數

b：（Ak+1Ak+2…An)連乘的乘法次數

c：（A1A2…Ak)(Ak+1Ak+2…An)連乘的乘法次數則c=a+b+p1qnqk由于a不是最小的或b不是最小的，則c肯定不是最小的，（A1A2…Ak)(Ak+1Ak+2…An)不是最優決策，矛盾，故假設不真，兩個子問題的計算次序都是最優的。建立最優值的遞歸關系式描述子問題：AiAi+1…Aj，其中矩陣Am的行數為pm，列數為qm(m=i,i+1,…,j)描述子問題的最少乘法次數（最優值）用i和j兩個參數描述問題規模設從k處分開為最優決策m[i][j]：（AiAi+1…Ak)(Ak+1…Aj）連乘的乘法次數m[i][k]：AiAi+1…Ak的最佳計算次序對應的乘法次數m[k+1][j]：Ak+1Ak+2…Aj的最佳計算次序對應的乘法次數當i=j時，只有一個矩陣,故m[i][i]=0；當i<j時，m[i][j]=m[i][k]+m[k+1][j]+piqjqk把n個矩陣的行列存儲到數組P中：0123...n-2n-1np1q1q2q3......qn-2qn-1qn建立最優值的遞歸關系式自底向上求解m[i][j]j=1j=2j=3j=...j=ns[i][j]j=1j=2j=3j=...j=ni=10i=10i=20i=20i=30i=30i=...0i=...0i=n0i=n0遞歸構造最優解算法分析計算最優值：填寫二維表格n2，取最小n，故：O(n3)構造最優解：

解此遞歸式得T(n)=O(n)。小結矩陣連乘問題的動態規劃算法分析最優子結構性質建立最優值的遞歸關系式自底向上求解構造最優解時間復雜度分析凸多邊形最優三角剖分基本概念凸多邊形：一個簡單多邊形及其內部構成一個閉凸集。凸多邊形三角剖分：將一個凸多邊形分割成互不相交的三角形的弦的集合，如{弦1，弦2，弦3}弦1弦2弦3凸多邊形三角剖分凸多邊形三角剖分唯一嗎？給定凸多邊形及定義在邊、弦構成的三角形的權函數w(i,j,k)。最優三角剖分：不同剖分方法所劃分的各三角形上權函數之和最小的三角剖分。三角形剖分的結構（A1A2)(A3(A4A5))A1A2A3A4A5最優子結構性質分析設v0vkvn是將n+1邊形P={v0,v1,…,vn}分成三部分{v0,v1,…,vk}、{vk,vk+1,…,vn}和{v0,vk,vn}的最佳剖分方法，那么凸多邊形{v0,v1,…,vk}的剖分一定是最優的，{vk,vk+1,…,vn}的剖分也一定是最優的。最優子結構性質分析反證法：設凸多邊形{v0,v1,…,vk}的剖分不是最優的或{vk,vk+1,…,vn}的剖分不是最優的。令c：{v0,v1,…,vn}三角剖分的權函數之和a：{v0,v1,…,vk}三角剖分的權函數之和b：{vk,vk+1,…,vn}三角剖分的權函數之和w(v0vkvn)：三角形v0vkvn的權函數則c=a+b+w(v0vkvn)。w(v0vkvn)固定不變，根據假設知：a不是最小的或不是最小的，則c一定不是最小的，這說明c對應的{v0,v1,…,vn}的三角剖分不是最優的，矛盾。建立最優值的遞歸關系式描述子問題：vi-1vi…vj描述子問題的最優值：m[i][j]表示vi-1vi…vj最優三角剖分權函數之和m[i][k]表示vi-1vi…vk最優三角剖分權函數之和m[k+1][j]表示vkvi…vj最優三角剖分權函數之和當i=j時表示一條直線段，將其看作退化多邊形，其權函數為0。則自底向上求解定義三角形的權函數：defget_weight(i,j,k):ifk<n:returnweights[i][j]+weights[j][k]+weights[k][i]#計算最優值并記錄最優決策defMinest_weight_val(n):#n邊形的三角剖分問題相當于n-1個矩陣連乘問題。m=np.zeros((n,n))#存放最優值s=np.zeros((n,n))#存放最優決策foriinrange(1,n):m[i][i]=0s[i][i]=0forrinrange(2,n):foriinrange(1,n-r+1):j=i+r-1m[i][j]=m[i+1][j]+get_weight(i-1,i,j)s[i][j]=iforkinrange(i+1,j):t=m[i][k]+m[k+1][j]+get_weight(i-1,k,j)ift<m[i][j]:m[i][j]=ts[i][j]=kreturnm,s構造最優解res=[]defTraceback(i,j,s,res):ifi==j:returnelse:Traceback(i,int(s[i][j]),s,res)Traceback(int(s[i][j]+1),j,s,res)

res.append('v'+str(i-1)+',v'+str(j)+',v'+str(int(s[i][j])))小結基本概念分析了與矩陣連乘問題的聯系動態規劃解題步驟最優子結構性質分析建立最優值遞歸關系式自底向上求解最優值，記錄相關信息根據相關信息構造最優解最長公共子序列問題基本概念（1）子序列給定序列X={x1,x2,…,xn}、Z={z1,z2,…,zk}，若Z是X的子序列，當且僅當存在一個嚴格遞增的下標序列{i1,i2,…,ik}，對j∈{1,2,…,k}有zj=xik如：X={A,B,C,B,D,A,B}{A,B}{B,C,A}{A,B,C,D,A}{B,B,C}（2）公共子序列給定序列X和Y，序列Z是X的子序列，也是Y的子序列，則稱Z是X和Y的公共子序列。X={A,B,C,B,D,A,B}Y={A,C,B,E,D,B}的公共子序列有：{A,B}{C,B,D}{A,C,B,D,B}（3）最長公共子序列包含元素最多的公共子序列即為最長公共子序列。

最長公共子序列問題最優子結構性質分析設Zk={z1,z2,…,zk}是序列Xm={x1,x2,…,xm}和序列Yn={y1,y2,…,yn}的最長公共子序列。a)若zk=xm=yn，則Zk-1={z1,z2,…,zk-1}是Xm-1和Yn-1的最長公共子序列。證明：設Zk-1不是Xm-1和Yn-1的最長公共子序列，則對序列Xm-1和Yn-1來說，應該有它們的最長公共子序列，設其最長公共子序列為M。因此有：|Zk-1|<|M|。在Xm-1和Yn-1的最后均添加一個相同的字符zk=xm=yn，則Zk-1+{zk}和M+{zk}均是Xm和Yn的公共子序列。又由于|Zk-1+{zk}=Zk|<|M+{zk}|，故Zk不是Xm和Yn的最長公共子序列，與前提矛盾，假設不真。最優子結構性質分析b)若xm≠yn,xm≠zk，則Zk是Xm-1和Yn的最長公共子序列。證明：設Zk不是Xm-1和Yn的最長公共子序列，則對序列Xm-1和Yn來說，應該有它們的最長公共子序列，設其最長公共子序列為M。由此有：|Zk|<|M|。在Xm-1的最后添加一個字符xm，則M也是Xm和Yn的公共子序列。又由于|Zk|<|M|，故Zk不是Xm和Yn的最長公共子序列，與前提矛盾，得證。最優子結構性質分析c)若xm≠yn,yn≠zk，則Zk是Xm和Yn-1的最長公共子序列。證明：設Zk不是Xm和Yn-1的最長公共子序列，則對序列Xm和Yn-1來說，應該有它們的最長公共子序列，設其最長公共子序列為M。由此有：|Zk|<|M|。在Yn-1的最后添加一個字符yn，則M也是Xm和Yn的公共子序列。又由于|Zk|<|M|，故Zk不是Xm和Yn的最長公共子序列，與前提矛盾，得證。建立最優值的遞歸關系式描述子問題：Xi、Yj描述最長公共子序列長度：c[i][j]自底向上填表求解，記錄相關信息根據相關信息構造最優解res=[]defprintLCS(s,A,i,j):if(i==0orj==0):return0ifs[i][j]==0:printLCS(s,A,i-1,j-1)res.append(A[i])elifs[i][j]==1:printLCS(s,A,i-1,j)else:printLCS(s,A,i,j-1)實例給定序列X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}，求它們的最長公共子序列。小結最長公共子序列問題最優子結構性質分析建立最優值遞歸關系式自底向上求解最優值，記錄相關信息根據相關信息構造最優解實例加工順序問題問題：設有n個工件需要在機器M1和M2上加工，每個工件的加工順序都是先在M1上加工，然后在M2上加工。t1j、t2j分別表示工件j在M1、M2上所需的加工時間(j=1,2,…,n)。問應如何在兩機器上安排生產，使得第一個工件從在M1上加工開始到最后一個工件在M2上加工完所需的總加工時間最短？處理過程：最優子結構性質分析整體最優：將n個工件的集合看作N={1,2,…,n}，設(p1,p2,...,pn)是M1開始處理集合N時，機器M2經過t時間才能夠停下來的最優調度方案。子問題最優：(p2,...,pn)是M1開始處理集合N-{p1}時，機器M2經過max{t-t1p1,0}+t2p1時間才能夠停下來的最優調度方案。證明：(p2,...,pn)不是M1開始處理集合N-{p1}時，機器M2經過max{t-t1p1,0}+t2p1時間才能夠停下來的最優調度方案。令T(S，t)：表示集合S中的工件開始在M1上加工時，機器M2需要t時間才能停下來到情況下所消耗的總加工時間。則：T(N，t)：調度方案(p1,p2,...,pn)總加工時間。T(N-{p1},max{t-t1p1,0}+t2p1)是(p2,...,pn)總加工時間。T(N,t)=t1p1+T(N-{p1},max{t-t1p1,0}+t2p1)由于T(N-{p1},max{t-t1p1,0}+t2p1)不是最小的所以T(N,t)肯定不是最小的，矛盾。建立最優值的遞歸關系式子問題：M1開始處理集合S中的工件時，M2需要t時間停下來。整體最優值T(S,t)子問題的最優值T(S-{i},max{t-t1i,0}+t2i)遞歸關系式：自底向上求解最優值方案1：先加工S中的i號工件，再加工j號工件，其它工件的加工順序為最優調度順序。方案2：先加工S中的j號工件，再加工i號工件，其它工件的加工順序為最優調度順序。自底向上求解若tij≤tji，則T(S,t)≤T'(S,t)，方案1優于方案2若方案1優于方案2，則T(S,t)≤T'(S,t)，tij≤tji方案1優于方案2tij≤tji不等式兩邊同乘以-1方案2優于方案1tji≤tij不等式兩邊同乘以-1Johnson-Bellman'sRule最優加工順序的第i個和第j個要加工的工件，如果i<j，則必有如果加工工件i和j滿足min{t1j，t2i}大于等于min{t1i，t2j}不等式，稱加工工件i和j滿足JohnsonBellman‘sRule。滿足JohnsonBellman'sRule的加工順序方案為最優方案。構造最優解算法步驟1：令N1={i|t1i<t2i},N2={i|t1it2i}；步驟2：將N1中工件按t1i非減序排序；將N2中工件按t2i非增序排序；步驟3：N1中工件接N2中工件，即N1N2就是所求的滿足JohnsonBellman'sRule的最優加工順序

算法分析顯然，FlowShop算法的時間復雜性取決于Sort函數的執行時間由于Sort函數的執行時間為O(nlogn)，因此FlowShop算法的時間復雜性為O(nlogn)。小結最優加工順序問題最優子結構性質分析建立最優值的遞歸關系分析貝爾曼法則根據貝爾曼法則設計2個算法分析算法時間復雜度0-1背包問題問題：n個物品和1個背包。對物品i，其價值為vi，重量為wi，背包的容量為W。如何選取物品裝入背包，使背包中所裝入的物品的總價值最大？物品不可分割。問題建模目標函數：約束條件：最優子結構性質分析假設(x1,x2,…,xn)是0-1背包問題的一個最優解，則(x1,x2,…,xn-1)是下面相應子問題的一個最優解：目標函數：

約束條件：反證法證明：設(x1,…,xn-1)不是上述子問題的一個最優解，而(y1,…,yn-1)是上述子問題的一個最優解，則又最優解向量(y1,…,yn-1)滿足：所以這說明(y1,y2,…,yn-1,xn)是原問題的一個解反證法證明：又這說明(x1,x2,…,xn)不是所給0-1背包問題的最優解，與前提矛盾。故（x1,…,xn-1）是上述相應子問題的一個最優解建立最優值的遞歸關系式子問題：物品集為{1,2,...,i}，背包剩余容量為j子問題的最優值：

則遞歸關系式：自底向上求解，記錄相關信息defknapsack(weight,value,capacity):#returnmaxvalueweight.insert(0,0)#前0件要用value.insert(0,0)#前0件要用num=len(weight)bag_value=np.zeros((num,capacity+1),dtype=32)#下標從零開始foriinrange(1,num):forjinrange(1,capacity+1):ifweight[i]<=j:bag_value[i][j]=max(bag_value[i-1][j-weight[i]]+value[i],bag_value[i-1][j])else:bag_value[i][j]=bag_value[i-1][j]returnbag_value構造最優解defshow(n,capacity,weight,bag_value):print('最大價值為:',bag_value[n][capacity])x=[0foriinrange(n)]j=capacityforiinrange(n,0,-1):ifbag_value[i][j]>bag_value[i-1][j]:x[i-1]=1j-=weight[i-1]實例有5個物品，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6。背包容量為10，物品不可分割，求裝入背包的物品和獲得的最大價值。012345678910000000000000100666666666200669999999300669999111114400669991011131450066991212151515算法時間復雜度分析填寫二維表格：耗時O(nW)循環二維表中的每個元素，要么由c[i-1][j]得到，要么由c[i-1][j-wi]+vi計算得到，耗時O(1)。所以：算法的時間復雜度為O(nW)。缺點：（1）算法要求所給物品的重量wi是整數；（2）當背包容量W很大時，算法需要的計算時間較多，例如，當W>2n時，算法需要O(n2n)的計算時間。小結：0-1背包問題最優子結構性質分析建立最優值的遞歸關系自底向上求解構造最優解分析算法時間復雜度及缺點改進算法——跳躍點算法函數c[i][j]是關于變量j的階梯狀單調不減函數遞歸關系式p[0]={(0,0)}q[i-1]=p[i-1]+(wi,vi)i=1,2,...,np[i]=q[i-1]∪p[i-1]改進步驟（a）對每一個確定的i，用一個表p[i]來存儲函數C[i][j]的全部跳躍點并按照j升序排列。（b）p[i]可通過計算p[i-1]得到。（c）清除受控點：j大，但價值小的點。（d）由此可得，在遞歸地由p[i-1]計算p[i]時，可先由p[i-1]計算出q[i-1]，然后合并p[i-1]和q[i-1]，并清除其中的受控跳躍點得到p[i]。改進后算法的計算時間復雜性為O(min{nW，2n})

實例：5個物品，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6。背包容量為10p[0]={(0，0)}。q[0]={(2，6)}p[1]={(0，0)，(2，6)}q[1]={(2，3)，(4，9)}p[2]={(0，0)，(2，6)，(2，3)，(4，9)}q[2]={(6，5)，(8，11)，(10，14)}p[3]={(0，0)，(2，6)，(4，9)，(6，5)，(8，11)，(10，14)}實例：5個物品，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6。背包容量為10q[3]={(5，4)，(7，10)，(9，13)，(13，15)，(15，18)}p[4]={(0，0)，(2，6)，(4，9)，(5，4)，(7，10)，(8，11)，(9，13)，(10，14)}q[4]={(4，6)，(6，12)，(8，15)，(11，16)，(12，17)，(13，19)，(14，20)}p[5]={(0，0)，(2，6)，(4，9)，(4，6)，(6，12)，(7，10)，(8，11)，(8，15)，(9，13)，(10，14)}代碼：計算P[]defknapsack_improve(weight,value,capacity):iflen(weight)!=len(value):print("parametererr!")returnobj_num=len(weight)jump_points_p=[[]forxinrange(obj_num+1)]jump_points_q=[[]forxinrange(obj_num+1)]jump_points_p[0].append((0,0))foriinrange(1,obj_num+1):jump_points_q[i-1]=[(point[0]+weight[i-1],point[1]+value[i-1])forpointinjump_points_p[i-1]ifpoint[0]+weight[i-1]<=capacity]jump_points_p[i]=merge_points(jump_points_p[i-1],jump_points_q[i-1])returnjump_points_p構造最優解defshow(obj_num,weight,value,jump_points_p):vector=[0forxinrange(obj_num)]point=jump_points_p[5][len(jump_points_p[5])-1]foriinrange(obj_num,0,-1):temp_point=(point[0]-weight[i-1],point[1]-value[i-1])iftemp_pointinjump_points_p[i-1]:vector[i-1]=1point=temp_pointreturnvector小結0-1背包問題的跳躍點算法p[0]={(0,0)}q[i-1]=p[i-1]+(wi,vi)i=1,2,...,np[i]=q[i-1]∪p[i-1]算法的復雜度為min(nW,2n)最優二叉搜索樹基本概念：二叉搜索樹給定n個關鍵字組成的有序序列S={s1,s2,…,sn},構造一棵左子樹比根節點小，右子樹比根節點大的二叉樹，該二叉樹成為二叉搜索樹。如{s1,s2,s3}的二叉搜索樹：最優二叉查找樹在二叉搜索樹中查找指定關鍵字k時，有可能查找成功，有可能查找不成功。查找不成功時均是到達樹節點的空指針，將空指針看作樹的虛節點ei，e0表示小于s1的所有值，en表示大于sn所有值，其他ei表示(si,si+1)思考：n個關鍵字的有序序列，二叉搜索樹共有幾個虛節點？n+1最優二叉查找樹給定S={s1,s2,...,sn}的查找概率(p1,p2,...,pn)和虛節點{e0,e1,...,en}的概率(q1,q2,...,qn)，且滿足：平均查找次數：思考：n個關鍵字的有序序列，二叉搜索樹共有幾棵？最優二叉搜索樹最優二叉搜索樹是在所有表示有序序列S的二叉搜索樹中，具有最小平均比較次數的二叉搜索樹。在查找概率相等時：深度最小的二叉查找樹為最優二叉搜索樹。查找概率不等時：最優二叉樹并不一定是深度最小的二叉搜索樹。最優子結構性質分析T(1,n)：實結點{s1,s2,…,sn}和虛結點{e0,e1,…,en}構成的二叉搜索樹。設定元素sk作為該樹的根結點，1≤k≤n。左子樹T(1,k-1)：實結點{s1,…,sk-1}和虛結點e0,…,ek-1組成。右子樹T(k+1,n)：實結點{sk+1,…,sn}和虛結點ek,…,en組成。整體最優：如果T(1,n)是最優二叉查找樹，則子問題最優：左子樹T(1,k-1)和右子樹T(k+1,n)也是最優二叉查找樹。證明：（反證法）假設左子樹T(1,k-1)不是最優二叉搜索樹。最優子結構性質分析<建立最優值的遞歸關系式子問題：有序序列{si,si+1,...,sj},虛節點{ei-1,ei,...,ej}假設sk為樹根是最優決策，則左子樹：有序序列{si,si+1,...,sk-1},虛節點{ei-1,ei