算法設(shè)計(jì)與分析_3動(dòng)態(tài)規(guī)劃1

1、韓啟龍2022-4-192最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)重疊子問(wèn)題重疊子問(wèn)題無(wú)后效性無(wú)后效性2022-4-193最優(yōu)子結(jié)構(gòu)性質(zhì)（最優(yōu)性原理）最優(yōu)子結(jié)構(gòu)性質(zhì)（最優(yōu)性原理）。在分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的，然后再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解，從而導(dǎo)致矛盾。 利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。注意：同一個(gè)問(wèn)題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問(wèn)題的維度低

2、）2022-4-194遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱(chēng)為子問(wèn)題的重疊性質(zhì)子問(wèn)題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。 通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。 2022-4-195 控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看，避免了相同子問(wèn)題的重復(fù)求解。2022-4-196 我們可以按如下4個(gè)步驟來(lái)設(shè)計(jì)動(dòng)態(tài)

3、規(guī)劃算法: Characterize the structure of an optimal solution Recursively define the value of an optimal solution Compute the value of an optimal solution in a bottom-up fashion Construct an optimal solution from computed information 找出找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 遞歸地定義最優(yōu)值。 以自底向上的方式計(jì)算出最優(yōu)值。 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。2022-

4、4-197n給定n個(gè)矩陣 ， 其中 與 是可乘的， ?？疾爝@n個(gè)矩陣的連乘積 n由于矩陣乘法滿(mǎn)足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。n若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。,.,21nAAAiA1iA1,.,2 , 1ninAAA.213.3 矩陣連乘問(wèn)題矩陣連乘問(wèn)題u完全加括號(hào)的矩陣連乘積可遞歸遞歸地定義為：（1）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積 是完全加括號(hào)的，則 可 表示為2個(gè)完全加括號(hào)的矩陣連乘積 和 的乘積并加括號(hào)，即 AABC)(B

5、CA2022-4-198 給定n個(gè)矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1,2 ,n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少連乘積需要的數(shù)乘次數(shù)最少。3.3 矩陣連乘問(wèn)題矩陣連乘問(wèn)題_2022-4-199u動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃將矩陣連乘積 簡(jiǎn)記為Ai:j ，這里ij jiiAAA.1考察計(jì)算Ai:j的最優(yōu)計(jì)算次序最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開(kāi)，ikj，則其相應(yīng)完全加括號(hào)方式為).)(.(211jkkkiiAAAAAA計(jì)算量：Ai:k的計(jì)算量加上Ak+1:j的計(jì)算量，再加上Ai:k和Ak+1:j相乘的計(jì)算量

6、3.3 矩陣連乘問(wèn)題矩陣連乘問(wèn)題矩陣可乘條件：矩陣可乘條件：A A的列數(shù)等于的列數(shù)等于B B的行數(shù)的行數(shù)若若A是一個(gè)是一個(gè)pq矩陣，矩陣，B是一個(gè)是一個(gè)qr矩陣，則矩陣，則AB總共需要總共需要pqr次數(shù)乘。次數(shù)乘。2022-4-1910特征：如果Ai:j的最優(yōu)次序包含矩陣子鏈 Ai:k和Ak+1:j。則子鏈的次序也是最優(yōu)的。矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱(chēng)為最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。證明3.3 矩陣連乘問(wèn)題矩陣連乘問(wèn)題_ 找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 遞歸地定義最優(yōu)值。 以自底向上的方式計(jì)算出最優(yōu)值。 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。若有一個(gè)計(jì)

7、算A1：k的次序計(jì)算量更少，則用此次序替換原來(lái)計(jì)算A1：k的次序，得到的計(jì)算A1：n的計(jì)算量將比最優(yōu)次序所需計(jì)算量更少，矛盾。2022-4-1911n設(shè)計(jì)算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)最少數(shù)乘次數(shù)mi,j，則原問(wèn)題的最優(yōu)值為m1,n n當(dāng)i=j時(shí)，Ai:j=Ai，因此，mi,i=0，i=1,2,nn當(dāng)ij時(shí)，n可以遞歸地定義mi,j為：jkipppjkmkimjim1, 1,這里 的維數(shù)為 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 斷開(kāi)位置 的位置只有 種可能，記為sijkij 3.3 矩陣連乘問(wèn)題矩陣連乘問(wèn)題_2022-4-1912對(duì)于1ij

8、n不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問(wèn)題。因此，不同子問(wèn)題的個(gè)數(shù)最多只有由此可見(jiàn)，在遞歸計(jì)算時(shí)，許多子問(wèn)題被重復(fù)計(jì)算多次許多子問(wèn)題被重復(fù)計(jì)算多次。也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一特征。用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過(guò)程中，保存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法。)(22nnn3.3 矩陣連乘問(wèn)題矩陣連乘問(wèn)題_簡(jiǎn)單的遞歸計(jì)算指數(shù)計(jì)算時(shí)間matrixChain(int p, int m, int s) int n=p.length-1; for (int i = 1;

9、 i = n; i+) mii = 0; for (int r = 2; r = n; r+) /矩陣鏈長(zhǎng)度為矩陣鏈長(zhǎng)度為2、3 n for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; 算法復(fù)雜度分析：算法復(fù)雜度分析：算法matrixChain的主要計(jì)算量取決于算法中對(duì)r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O

10、(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。2022-4-1914A1A2A3A4A5A6303535151555101020202512513514522350250035 15 201300025min23452625 100035 5 2024554375035 171250 2011375mmp p pmmmp p pmmp p p 3.3 矩陣連乘問(wèn)題矩陣連乘問(wèn)題_計(jì)算m35=?k=?2022-4-1915A1A2A3A4A5A630353515155510102020253.3 矩陣連乘問(wèn)題矩陣連乘問(wèn)題_最優(yōu)解如何構(gòu)

11、造？根據(jù)k值，即sij來(lái)構(gòu)造。Ai:j的最佳方式應(yīng)該在Ak和Ak+1之間斷開(kāi)。2022-4-1916 定義：定義：若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對(duì)于所有j=1,2,k有：zj=xij。 例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。 定義定義：給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱(chēng)Z是序列X和Y的公共子序列公共子序列。 最長(zhǎng)公共子序列問(wèn)題描述：最長(zhǎng)公共子序列問(wèn)題描述：給定2個(gè)序列X=x1,x2,xm和Y=

12、y1,y2,yn，找出X和Y的最長(zhǎng)公共子序列。 3.4 最長(zhǎng)公共子序列最長(zhǎng)公共子序列2022-4-1917證證 明明定理：定理：設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長(zhǎng)公共子序列為Z=z1,z2,zk ，則(1)若xm=yn，zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列。(2)若xmyn且zkxm，Z是Xm-1和Y的最長(zhǎng)公共子序列。(3)若xmyn且zkyn，Z是X和Yn-1的最長(zhǎng)公共子序列。由此可見(jiàn)，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)最優(yōu)子結(jié)構(gòu)性質(zhì)構(gòu)性質(zhì)。 窮舉法可以解決問(wèn)題窮舉法可以解決問(wèn)題

13、（對(duì)對(duì)X所有子序列檢查是否為所有子序列檢查是否為Y子序列并記錄最長(zhǎng)情況子序列并記錄最長(zhǎng)情況） LCS問(wèn)題的最優(yōu)子結(jié)構(gòu)特性：3.4 最長(zhǎng)公共子序列最長(zhǎng)公共子序列_2022-4-1918由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。Xm=Yn； XmYn（Xm-1，Y）;(X，Yn-1)用cij記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)Cij=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01

14、,1max1 1103.4 最長(zhǎng)公共子序列最長(zhǎng)公共子序列_2022-4-1919 由于在所考慮的子問(wèn)題空間中，總共有(mn)個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。 Algorithm lcsLength(x,y,b)1: mx.length-1;2: ny.length-1;3: ci0=0; c0i=0;4: for (int i = 1; i = m; i+)5: for (int j = 1; j =cij-1) 10: cij=ci-1j;11: bij=;12: else 13: cij=cij-1;14: bij=;3.4 最長(zhǎng)公共子序列最長(zhǎng)公共

15、子序列_2022-4-1920構(gòu)造最長(zhǎng)公共子序列構(gòu)造最長(zhǎng)公共子序列Algorithm lcs(int i,int j,char x,int b) if (i =0 | j=0) return; if (bij= ) lcs(i-1,j-1,x,b); System.out.print(xi); else if (bij= ) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); 3.4 最長(zhǎng)公共子序列最長(zhǎng)公共子序列_2022-4-1921設(shè)所給的2個(gè)序列為X=A,B,C,B,D,A,B和Y=B,D,C,A,B,A。由算法LCSLength和LCS計(jì)算的過(guò)程如下：B D C

16、A B AABCBDAB00000000000000001111111221122221122331222331223341223443.4 最長(zhǎng)公共子序列最長(zhǎng)公共子序列_說(shuō)明：LCS問(wèn)題解不是唯一的。2022-4-19223.5 凸多邊形最優(yōu)三角剖分凸多邊形最優(yōu)三角剖分多邊形凸多邊形簡(jiǎn)單多邊形平面上一條分段線性閉曲線；首尾相接的直線段所組成的；邊、頂點(diǎn)。邊除連接頂點(diǎn)外無(wú)別的交點(diǎn)；平面分為三部分。邊界或內(nèi)部任意兩點(diǎn)所連接的直線段上所有點(diǎn)均在三角形的內(nèi)部或邊界上；2022-4-19233.5 凸多邊形最優(yōu)三角剖分凸多邊形最優(yōu)三角剖分凸多邊形的表示用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P=v0,

17、v1,vn-1表示具有n條邊的凸多邊形。.n條邊為：v0v1,v1v2,vn-1vn約定：v0=vn2022-4-19243.5 凸多邊形最優(yōu)三角剖分凸多邊形最優(yōu)三角剖分多邊形的三角剖分若vi與vj是多邊形上不相鄰的2個(gè)頂點(diǎn)，則線段vivj稱(chēng)為多邊形的一條弦。弦將多邊形分割成2個(gè)多邊形vi,vi+1,vj和vj,vj+1,vi多邊形的三角剖分多邊形的三角剖分是將多邊形分割成互不互不相交的三角形相交的三角形的弦的集合T。2022-4-1925給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。 3.5 凸多邊

18、形最優(yōu)三角剖分凸多邊形最優(yōu)三角剖分凸多邊形最優(yōu)三角剖分2022-4-19263.5 凸多邊形最優(yōu)三角剖分凸多邊形最優(yōu)三角剖分l 表達(dá)式的語(yǔ)法樹(shù) 一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹(shù)，稱(chēng)為表達(dá)式的語(yǔ)法樹(shù)。l 例子完全加括號(hào)的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語(yǔ)法樹(shù)2022-4-19273.5 凸多邊形最優(yōu)三角剖分凸多邊形最優(yōu)三角剖分凸多邊形凸多邊形v0,v1,vn-1的三角剖分的三角剖分是否可以用語(yǔ)法樹(shù)來(lái)表示？是否可以用語(yǔ)法樹(shù)來(lái)表示？2022-4-1928矩陣連乘積中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，ij，對(duì)應(yīng)于

19、矩陣連乘積Ai+1:j。3.5 凸多邊形最優(yōu)三角剖分凸多邊形最優(yōu)三角剖分凸多邊形的三角剖分與矩陣連乘積凸多邊形的三角剖分與矩陣連乘積是否有關(guān)系？有什么關(guān)系？是否有關(guān)系？有什么關(guān)系？2022-4-1929最優(yōu)三角剖分問(wèn)題具有最優(yōu)子結(jié)性質(zhì)3.5 凸多邊形最優(yōu)三角剖分凸多邊形最優(yōu)三角剖分證明：若凸(n+1)邊形P=v0,v1,vn-1的最優(yōu)三角剖分T包含三角形v0vkvn，1kn-1，則T的權(quán)為3個(gè)部分權(quán)的和：三角形三角形v0vkvn的權(quán)的權(quán)，子多邊形子多邊形v0,v1,vk和vk,vk+1,vn的權(quán)之和?？梢詳嘌裕蒚所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衯0,v1,vk或vk,vk

20、+1,vn的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。 2022-4-1930u 定義tij，1iT(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)2n時(shí)，算法需要(n2n)計(jì)算時(shí)間。 2022-4-19423.8 0-1背包問(wèn)題背包問(wèn)題為什么要進(jìn)行算法改進(jìn)?O(nc)c2n時(shí)，算法需要(n2n)計(jì)算時(shí)間由m(i,j)的遞歸式可以看出，在一般情況下，對(duì)每一個(gè)確定的每一個(gè)確定的i(1in)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類(lèi)函數(shù)的描述特征。

21、在一般情況下，函數(shù)m(i,j)由其全部跳躍點(diǎn)唯一確定。iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(2022-4-1943是背包容量為j，可選擇物品為i，i+1，n時(shí)0-1背包問(wèn)題的最優(yōu)值。iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(nnnwjwjvjnm00),(例子：n=5，c=10，w=2，2，6，5，4，v =6，3，5，4，6?？疾臁氨嘲萘俊迸c“最優(yōu)解m(i ,j )”之間的關(guān)系：由計(jì)算m(i ,j)的遞歸式遞歸式可知，當(dāng)i = 5時(shí)，55546(5, )040jwvmjjwjm(5 , j)04

22、6c當(dāng)cj=4時(shí)，m(5, j ) = 6當(dāng)4j=0時(shí)，m(5, j ) = 0 在j=2時(shí)，因0-1背包問(wèn)題，無(wú)法裝進(jìn)物品。 在一般情況下，對(duì)每一個(gè)確定的確定的i(1in)，函數(shù)m(i,j)是關(guān)于變量j的階階梯狀單調(diào)不減梯狀單調(diào)不減函數(shù)。 符合常理，符合常理，若背包容量越大，若背包容量越大，則裝的價(jià)值越多。則裝的價(jià)值越多。2022-4-19463.8 0-1背包問(wèn)題背包問(wèn)題橫坐標(biāo)：背包容量；橫坐標(biāo)：背包容量；縱坐標(biāo)：可選物品為縱坐標(biāo)：可選物品為i in n時(shí)問(wèn)題的最優(yōu)值；時(shí)問(wèn)題的最優(yōu)值；注意：此時(shí)的注意：此時(shí)的i i是確定的。是確定的。在一般情況下，函數(shù)m(i,j)由其全部跳躍點(diǎn)唯一確定。如

23、圖所示。2022-4-19473.8 0-1背包問(wèn)題背包問(wèn)題注意：i(1in)是確定的。背包容量j是自變量 pi可依m(xù)(i，j)的遞歸式遞歸地由表pi+1計(jì)算 pn+1=(0，0)。 要搞清的幾個(gè)問(wèn)題：iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(u m(i,j)：背包容量為背包容量為j，可選物品為，可選物品為in時(shí)問(wèn)題的最優(yōu)值時(shí)問(wèn)題的最優(yōu)值u pi：存儲(chǔ)的存儲(chǔ)的m(i，j)的全部跳躍點(diǎn)，的全部跳躍點(diǎn)，P1中的最后的跳躍點(diǎn)即問(wèn)題的最優(yōu)值中的最后的跳躍點(diǎn)即問(wèn)題的最優(yōu)值2022-4-1948p i 如何計(jì)算？如何計(jì)算？p i ：存儲(chǔ)函數(shù)m(i，j)的全部跳

24、躍點(diǎn)。對(duì)每一個(gè)確定的i(1in)，根據(jù)m(i，j)的遞歸式遞歸地由pi+1計(jì)算，初始時(shí)pn+1=(0，0)。 如何理解？p i 存儲(chǔ)的是函數(shù)m( i , j )的全部跳躍點(diǎn)，即（j, m( i , j )）；如何確定這個(gè)值？分析： （j, m( i , j )）中，背包的容量），只需根據(jù)j的變化由m( i , j )的遞歸式就可以計(jì)算出m( i , j ) 的值，即可得到跳躍點(diǎn)的值，（j, m( i , j )）。初始值為pn+1 = (0 , 0)，即（j, m(n+1, j)）= (0, 0) 也就是說(shuō)，我們從初始值開(kāi)始，從后向前進(jìn)行遞歸調(diào)用，就可以得到所有的pi的值。2022-4-194

25、93.8 0-1背包問(wèn)題背包問(wèn)題要搞清的幾個(gè)問(wèn)題：u qi+1：函數(shù)函數(shù)m(i+1，j-wi)+vi的跳躍點(diǎn)集的跳躍點(diǎn)集qi+1qi+1由函數(shù)由函數(shù)pi+1計(jì)算可得計(jì)算可得函數(shù)m(i, j)是由函數(shù)m(i+1, j)與函數(shù)m(i+1, j-wi)+vi作max運(yùn)算得到的。因此，函數(shù)m(i, j)的全部跳躍點(diǎn)包含于函數(shù)m(i+1，j)的跳躍點(diǎn)集pi+1與函數(shù)m(i+1，j-wi)+vi的跳躍點(diǎn)集qi+1的并集中。易知，(s,t)qi+1當(dāng)且僅當(dāng)wi s c且(s-wi, t-vi ) pi+1。因此，由pi+1確定跳躍點(diǎn)集qi+1如下:qi+1=pi+1 (wi,vi)=(j+wi, m(i,j

26、)+vi)|(j,m(i,j) pi+1 2022-4-1950因?yàn)?，函?shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運(yùn)算得到的。因此，函數(shù)m(i,j)的全部跳躍點(diǎn)包含于函數(shù)m(i+1，j)的跳躍點(diǎn)集pi+1與函數(shù)m(i+1，j-wi)+vi的跳躍點(diǎn)集qi+1的并集中。即有p i = p i+1 q i +1 qi+1如何計(jì)算的？易知，跳躍點(diǎn)(s,t)qi+1當(dāng)且僅當(dāng)wisc且(s-wi,t-vi)pi+1。定義定義1： pi+1存儲(chǔ)函數(shù)m(i+1，j)的跳躍點(diǎn)集；定義定義2： qi+1存儲(chǔ)函數(shù)m(i+1，j-wi)+vi的跳躍點(diǎn)集。易知分析：第i個(gè)物品裝入背

27、包中，才會(huì)發(fā)生這種情況。其中：s是背包的容量；tm( i+1 , s)；此時(shí)，第i個(gè)物品已經(jīng)裝入背包中，必有s=wi,且整個(gè)問(wèn)題可以轉(zhuǎn)換為容量為(s wi) 的背包裝物品從i+1到n的問(wèn)題。此問(wèn)題可由p i +1 來(lái)確定。此時(shí)，背包容量為(s wi)自變量；根據(jù)m( i ,j)的定義可以求出m(i+1, s-wi)的值，即可確定（(s-wi)，m(i+1, s-wi) ）的值跳躍點(diǎn)；此時(shí)，m(i+1, s-wi) m( i+1 , s) vit vi。即（(s-wi)， (t vi)）p i+1因此，可由pi+1確定跳躍點(diǎn)集qi+1，即qi+1=pi+1(wi,vi)=(j+wi,m(i,j)

28、+vi)|(j,m(i,j)pi+1由由p i +1中的每個(gè)點(diǎn)中的每個(gè)點(diǎn)在自變量與函數(shù)上分在自變量與函數(shù)上分別加上別加上wi與與vi獲得獲得2022-4-19513.8 0-1背包問(wèn)題背包問(wèn)題要搞清的幾個(gè)問(wèn)題：u 受控跳躍點(diǎn)：受控跳躍點(diǎn)：設(shè)(a，b)和(c，d)是pi+1qi+1中的2個(gè)跳躍點(diǎn)，則當(dāng)ca且db時(shí)，(c，d)受控于(a，b)，從而(c，d)不是pi中的跳躍點(diǎn)。即，背包容量大，裝的物品價(jià)值小。背包容量大，裝的物品價(jià)值小。(c，d)肯定不是最優(yōu)值?？隙ú皇亲顑?yōu)值。除受控跳躍點(diǎn)外，pi+1qi+1中的其它跳躍點(diǎn)均為pi中的跳躍點(diǎn)。2022-4-19523.8 0-1背包問(wèn)題背包問(wèn)題要搞

29、清的幾個(gè)問(wèn)題：pi的計(jì)算：分三步的計(jì)算：分三步1.先由pi+1計(jì)算出qi+12.合并表pi+1和表qi+13.清除其中的受控跳躍點(diǎn)得到表pipi = pi+1 qi+12022-4-19533.8 0-1背包問(wèn)題背包問(wèn)題1. m（i，j）2.跳躍點(diǎn)（s，t）（x，m（i，x）3. pi4. qi5.受控跳躍點(diǎn)pi = pi+1 qi+1要搞清的幾個(gè)問(wèn)題：例1、 n=3，c=6，w=4，3，2，v=5，2，1。 x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)

30、xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0, 0)(2, 1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)p4=(0, 0)q4=p4 (w3, v3)p3=p4 q4p2=p3 q3p3=(0, 0)，(2,1)q3=p3 (w2, v2)=(3,2)(5,3)p2=p3 q3=(0,0),(2,1),(3,2),(5,3)p1=p2 q2p2=(0,0),(2,1),(3,2),(5,3)q2=p2 (w1, v1)=(4,5),(6,6),(7,7

31、),(9,8)p1=p2 q2 =(0,0),(2,1),(3,2),(4,5),(6,6)2022-4-1955n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。初始時(shí)p6=(0,0)，(w5,v5)=(4,6)。因此，q6=p6(w5,v5)=(4,6)。p5=(0,0),(4,6)。q5=p5(w4,v4)=(5,4),(9,10)。從跳躍點(diǎn)集p5與q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中看到跳躍點(diǎn)(5,4)受控于跳躍點(diǎn)(4,6)。將受控跳躍點(diǎn)(5,4)清除后，得到p4=(0,0),(4,6),(9,10)3.8 0-1背包問(wèn)題背包問(wèn)題202

32、2-4-1956n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。q4=p4(6，5)=(6，5)，(10，11)p3=(0，0)，(4，6)，(9，10)，(10，11)q3=p3(2，3)=(2，3)，(6，9)p2=(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)q2=p2(2，6)=(2，6)，(4，9)，(6，12)，(8，15)p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15)p1的最后的那個(gè)跳躍點(diǎn)(8,15)給出所求的最優(yōu)值為m(1,c)=15。3.8 0-1背包問(wèn)題背包問(wèn)題上述算法的主要計(jì)算量在于計(jì)算跳躍點(diǎn)集pi(1

33、in)。由于qi+1=pi+1(wi，vi)，故計(jì)算qi+1需要O(|pi+1|)計(jì)算時(shí)間。合并pi+1和qi+1并清除受控跳躍點(diǎn)也需要O(|pi+1|)計(jì)算時(shí)間。從跳躍點(diǎn)集pi的定義可以看出，pi中的跳躍點(diǎn)相應(yīng)于xi,xn的0/1賦值。因此，pi中跳躍點(diǎn)個(gè)數(shù)不超過(guò)2n-i+1。由此可見(jiàn)，算法計(jì)算跳躍點(diǎn)集pi所花費(fèi)的計(jì)算時(shí)間為從而，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O(2n)。當(dāng)所給物品的重量wi(1in)是整數(shù)時(shí)，|pi|c+1，(1in)。在這種情況下，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O(minnc,2n)。 nniinniOOipO22| 1|222022-4-1958n=4，c=9，w=2，3，

34、4，5，v=3，4，5，7。3.8 0-1背包問(wèn)題背包問(wèn)題2022-4-1959 二叉搜索樹(shù)二叉搜索樹(shù)（1）若它的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；（2）若它的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；（3 它的左、右子樹(shù)也分別為二叉排序樹(shù)45125333724100619078在隨機(jī)的情況下，二叉查找樹(shù)的平均查找長(zhǎng)度和 是等數(shù)量級(jí)的nlog3.9 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)查找成功與不成功的概率二叉查找樹(shù)的期望耗費(fèi)有n 個(gè)節(jié)點(diǎn)的二叉樹(shù)的個(gè)數(shù)為：窮舉搜索法的時(shí)間復(fù)雜度為指數(shù)級(jí)110niniiiqpniiiTniiiTniiiTniiiTqdpkqdpkTE

35、0101)(depth)(depth1) 1)(depth() 1)(depth() incost search()/4(2/3nn0d1d2d3d4d5d1k2k3k4k5k3.9 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)2.80 Total0.40 0.10 3 0.20 0.05 3 0.20 0.05 3 0.20 0.05 3 0.30 0.10 2 0.15 0.05 2 0.60 0.20 2 0.20 0.10 1 0.15 0.05 2 0.10 0.10 0 0.30 0.15 1 oncontributiy probabilit depth node54321 054321ddddd

36、dkkkkk0d1d2d3d4d5d1k2k3k4k5k3.9 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)2022-4-1962給定一個(gè)由n個(gè)互異的關(guān)鍵字組成的序列K，且關(guān)鍵字有序關(guān)鍵字有序，（k1k2.kn），我們想從這些關(guān)鍵字中構(gòu)造構(gòu)造一棵二叉查找樹(shù)。對(duì)每個(gè)關(guān)鍵字ki，一次搜索為ki的概率是pi。某些搜索的值可能不在K內(nèi)，因此，還有n+1個(gè)“虛擬鍵虛擬鍵”d0,d1,dn代表不在K內(nèi)的值。具體地，d0代表所有小于k1的值，dn代表所有大于kn的值，而對(duì)于i=1,2,n-1，虛擬鍵di代表所有位于ki和ki+1之間的值。對(duì)于每個(gè)虛擬鍵di，一次搜索對(duì)應(yīng)于di的概率是qi。每個(gè)關(guān)鍵字ki是一個(gè)內(nèi)部節(jié)點(diǎn)，每個(gè)虛擬鍵di是一個(gè)葉子節(jié)點(diǎn)。每次搜索要么成功找到搜索要么成功找到ki，要么失敗，要么失?。ㄕ业侥硞€(gè)虛擬鍵）。3.9 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)問(wèn)題的定義輸入：k=k1, k2, , kn, k1 k2 kn, P=p1, p2, , pn, pi 為搜索ki 的概率 Q=q0, q1, , qn, qi 為搜索值di 的概率輸出：K 的二叉搜索樹(shù)T, E(T)最小2022-4-1963一棵二叉查找樹(shù)的任意一棵子樹(shù)必定包含在連續(xù)范圍內(nèi)的關(guān)鍵字ki,kj，對(duì)某個(gè)1ijn。另外，一棵含有關(guān)鍵字ki,kj的子樹(shù)必定也含有虛擬鍵di-1,dj作為葉子。首先，考察子樹(shù)如果一棵最優(yōu)二叉