1、算法設(shè)計(jì)與分析,2,第三章 動(dòng)態(tài)規(guī)劃,本章主要知識(shí)點(diǎn)：(11) 3.1 矩陣連乘問(wèn)題 3.2 動(dòng)態(tài)規(guī)劃算法的基本要素 3.3 最長(zhǎng)公共子序列問(wèn)題 3.4 最大子段和 3.5 凸多邊形的最優(yōu)三角剖分 3.6 多邊形游戲 3.7 圖像壓縮 3.8 電路布線 3.9 流水作業(yè)調(diào)度 3.10 0-1背包問(wèn)題 3.11 最有二叉搜索樹(shù) 3.12 動(dòng)態(tài)規(guī)劃加速原理 ,3,4,5,6,7,8,9,10,11,引言,動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題。 但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多

2、次。 如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。,Those who cannot remember the past are doomed to repeat it. George Santayana, The life of Reason, Book I: Introduction and Reason in Common Sense (1905),12,最優(yōu)化原理與無(wú)后效性,一般來(lái)說(shuō)，能夠采用動(dòng)態(tài)規(guī)劃方法求解的問(wèn)題必須滿足.最優(yōu)化原理和.無(wú)后效性原則。 1)動(dòng)態(tài)規(guī)劃的最優(yōu)化原理。作為整個(gè)過(guò)程的最優(yōu)策略具有如下性質(zhì)：無(wú)論

3、過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的當(dāng)前狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略?？梢酝ㄋ椎乩斫鉃樽訂?wèn)題的局部最優(yōu)將導(dǎo)致整個(gè)問(wèn)題的全局最優(yōu)，即問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，也就是說(shuō)一個(gè)問(wèn)題的最優(yōu)解只取決于其子問(wèn)題的最優(yōu)解，非最優(yōu)解對(duì)問(wèn)題的求解沒(méi)有影響。在例題1最短路徑問(wèn)題中，A到E的最優(yōu)路徑上的任一點(diǎn)到終點(diǎn)E的路徑也必然是該點(diǎn)到終點(diǎn)E的一條最優(yōu)路徑，滿足最優(yōu)化原理。下面來(lái)討論另外一個(gè)問(wèn)題。,13,(2)動(dòng)態(tài)規(guī)劃的無(wú)后效性原則。所謂無(wú)后效性原則，指的是這樣一種性質(zhì)：某階段的狀態(tài)一旦確定，則此后過(guò)程的演變不再受此前各狀態(tài)及決策的影響。也就是說(shuō)，“未來(lái)與過(guò)去無(wú)關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個(gè)完整總結(jié)

4、，此前的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響過(guò)程未來(lái)的演變。具體地說(shuō)，如果一個(gè)問(wèn)題被劃分各個(gè)階段之后，階段 I 中的狀態(tài)只能由階段 I+1 中的狀態(tài)通過(guò)狀態(tài)轉(zhuǎn)移方程得來(lái)，與其他狀態(tài)沒(méi)有關(guān)系，特別是與未發(fā)生的狀態(tài)沒(méi)有關(guān)系，這就是無(wú)后效性。從圖論的角度去考慮，如果把這個(gè)問(wèn)題中的狀態(tài)定義成圖中的頂點(diǎn)，兩個(gè)狀態(tài)之間的轉(zhuǎn)移定義為邊，轉(zhuǎn)移過(guò)程中的權(quán)值增量定義為邊的權(quán)值，則構(gòu)成一個(gè)有向無(wú)環(huán)加權(quán)圖，因此，這個(gè)圖可以進(jìn)行“拓?fù)渑判颉?，至少可以按他們拓?fù)渑判虻捻樞蛉澐蛛A段。,14,動(dòng)態(tài)規(guī)劃基本步驟,找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 遞歸地定義最優(yōu)值。 以自底向上的方式計(jì)算出最優(yōu)值。 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造

5、最優(yōu)解。,15,3.1 矩陣連乘問(wèn)題,給定n個(gè)矩陣A1,A2,.,An，其中Ai與Ai+1是可乘的，i=1,2,.,n-1?？疾爝@n個(gè)矩陣的連乘積A1A2.An。 由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。 完全加括號(hào)的矩陣連乘積可遞歸地定義為： 單個(gè)矩陣是完全加括號(hào)的； 矩陣連乘積A是完全加括號(hào)的，則A可表示為2個(gè)完全加括號(hào)的矩陣連乘積B和C的乘積并加括號(hào)，即A=(BC)。 設(shè)有四個(gè)矩陣A,B,C,D，

6、它們的維數(shù)分別是：A=5010，B=1040，C=4030，D=305 總共有五種完全加括號(hào)的方式：(A(BC)D) (A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D) 其數(shù)乘次數(shù)分別為：16000, 10500, 36000, 87500, 34500,16,窮舉搜索法,問(wèn)題描述：給定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ì)于

7、n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。 由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下： 也就是說(shuō)，P(n)是隨n的增長(zhǎng)成指數(shù)增長(zhǎng)的。,17,動(dòng)態(tài)規(guī)劃法1.分析最優(yōu)解的結(jié)構(gòu),下面我們考慮用求解。 預(yù)處理： 將矩陣連乘積AiAi+1.Aj簡(jiǎn)記為Ai:j，這里ij。 考察計(jì)算Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開(kāi)，ikj，則其相應(yīng)完全加括號(hào)方式為（AiAi+1. Ak）（Ak+1 Ak+2. Aj ）。 計(jì)算量：Ai:k的計(jì)算量加上Ak+1:j的計(jì)算量，再加上Ai:k和Ak+1:j相

8、乘的計(jì)算量。 分析最優(yōu)解的結(jié)構(gòu) 特征：計(jì)算Ai:j的最優(yōu)次序所包含的計(jì)算矩陣子鏈 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ì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。,18,2.建立遞歸關(guān)系,設(shè)計(jì)算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問(wèn)題的最優(yōu)值為m1,n。 當(dāng)i=j時(shí)，Ai:j=Ai，因此，mi,i=0，i=1,2,n。 當(dāng)ij時(shí)，mi,j=mi,k+mk+1,j+pi-1pkpj，這里Ai的維數(shù)為pi-1pi。 可以遞歸地定義mi,j為： k的位置只有j-i種可能。,19,3

9、.計(jì)算最優(yōu)值,對(duì)于1ijn不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問(wèn)題。因此，不同子問(wèn)題的個(gè)數(shù)最多只有 由此可見(jiàn)，在遞歸計(jì)算時(shí)，許多子問(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í)間的算法。,20,算法MatrixChain首先計(jì)算出mii=0,i=1,2,3,.n，然后，根據(jù)遞歸式，按矩陣鏈的方式依次計(jì)算mii+1(矩陣鏈長(zhǎng)度為2，兩個(gè)相鄰矩陣相乘，A1*A2,A2*A3,.An-

10、1* An）mii+2(矩陣鏈長(zhǎng)度為3）；在計(jì)算mij時(shí)，只用到已計(jì)算出的mik和mk+1j,21,算法描述,算法描述： void MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) 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

11、-1*pk*pj; if (t mij) mij = t; sij = k; ,22,示例,23,4.構(gòu)造最優(yōu)解,算法描述：略。 復(fù)雜性分析： 算法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)。 算法TraceBack的復(fù)雜性？,24,3.2 動(dòng)態(tài)規(guī)劃算法的基本要素,從計(jì)算矩陣連乘積最優(yōu)計(jì)算次序的動(dòng)態(tài)規(guī)劃算法可以看出，該算法的有效性依賴(lài)于問(wèn)題本身所具有的兩個(gè)重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)。從一般意義上講，問(wèn)題的這兩個(gè)重要性質(zhì)是該問(wèn)題

12、可以用動(dòng)態(tài)規(guī)劃算法求解的基本要素。本節(jié)著重介紹： 最優(yōu)子結(jié)構(gòu) 重疊子問(wèn)題 備忘錄方法 此外，本節(jié)最后對(duì)動(dòng)態(tài)規(guī)劃算法與備忘錄方法的適用條件作了簡(jiǎn)單介紹。,25,一、最優(yōu)子結(jié)構(gòu),矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱(chēng)為最優(yōu)子結(jié)構(gòu)性質(zhì)。 在分析問(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)題可以有多種方式

13、刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問(wèn)題的維度低）,26,二、重疊子問(wèn)題,遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱(chēng)為子問(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í)間，從而獲得較高的解題效率。,27,三、備忘錄方法,備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看，避免了相同子問(wèn)題的重復(fù)

14、求解。 int LookupChain(int i，int j) if (mij 0) return mij; if (i = j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; 算法復(fù)雜性：T(n)=O(n3),28,關(guān)于動(dòng)

15、態(tài)規(guī)劃算法和備忘錄方法的適用條件,綜上所述，矩陣連乘積的最優(yōu)計(jì)算次序問(wèn)題可用自頂向下的備忘錄方法或自底向上的動(dòng)態(tài)規(guī)劃算法在O(n3)計(jì)算時(shí)間內(nèi)求解。 這兩個(gè)算法都利用了子問(wèn)題重疊性質(zhì)?？偣灿?n2)個(gè)不同的子問(wèn)題，對(duì)每個(gè)子問(wèn)題兩種算法都只解一次并記錄答案。當(dāng)再次遇到該子問(wèn)題時(shí)，簡(jiǎn)單地取用已得到的答案，節(jié)省了計(jì)算量，提高了算法的效率。 適用條件：一般來(lái)說(shuō)，當(dāng)一個(gè)問(wèn)題的所有子問(wèn)題都至少要解一次時(shí)，用動(dòng)態(tài)規(guī)劃算法比用備忘錄方法好。此時(shí)，動(dòng)態(tài)規(guī)劃算法沒(méi)有任何多余的計(jì)算，還可以利用其規(guī)則的表格存取方式來(lái)減少在動(dòng)態(tài)規(guī)劃算法中的計(jì)算時(shí)間和空間需求。當(dāng)子問(wèn)題空間中部分子問(wèn)題可以不必求解時(shí)，易用備忘錄方法則較為

16、有利，因?yàn)閺钠淇刂平Y(jié)構(gòu)可以看出，該方法只解那些確實(shí)需要求解的子問(wèn)題。,29,3.3 最長(zhǎng)公共子序列,概述： 若給定序列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的公共子序列。 給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長(zhǎng)公共子序列。,30,最長(zhǎng)公共子序列的結(jié)構(gòu),設(shè)序列

17、X=x1,x2,xm和Y=y1,y2,yn的最長(zhǎng)公共子序列為Z=z1,z2,zk ，則 若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列。 若xmyn且zkxm，則Z是Xm-1和Y的最長(zhǎng)公共子序列。 若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é)構(gòu)性質(zhì)。,31,子問(wèn)題的遞歸結(jié)構(gòu),由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用cij記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)

18、i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)Cij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：,32,計(jì)算最優(yōu)值,由于在所考慮的子問(wèn)題空間中，總共有(mn)個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。 void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; ,33,構(gòu)造最長(zhǎng)公共子序列,算法描述： void LCS(int i，int j，

19、char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b); ,34,算法的改進(jìn),在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組元素cij的值僅由ci-1j-1，ci-1j和cij-1這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素cij，可以不借助于數(shù)組b而僅借助于c本身在時(shí)間內(nèi)確定cij的值是由ci-1j-1，ci-1j和cij-1中哪一個(gè)值所確定的。 如果只需要計(jì)算最長(zhǎng)

20、公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上，在計(jì)算cij時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n)。,35,3.4 最大子段和,問(wèn)題描述： 給定由n個(gè)整數(shù)（包含負(fù)整數(shù)）組成的序列a1,a2,.,an，求該序列子段和的最大值。當(dāng)所有整數(shù)均為負(fù)值時(shí)定義其最大子段和為0。 依此定義，所求的最優(yōu)值為： 例如，當(dāng)(a1,a2, a3, a4, a5,a6)=(-2,11,-4,13,-5,-2)時(shí)，最大子段和為：,36,1. 一個(gè)簡(jiǎn)單算法,一個(gè)簡(jiǎn)單算法： int MaxSum(int n, a

21、, 算法有3重循環(huán)，復(fù)雜性為O(n3)。,由于有： 算法可作如下改進(jìn)： int MaxSum(int n, a, 改進(jìn)后的算法復(fù)雜性為O(n2) 。,37,2. 分治方法求解,從問(wèn)題的解的結(jié)構(gòu)可以看出，它適合于用分治策略求解： 如果將所給的序列a1:n分為長(zhǎng)度相等的兩段a1:n/1和an/2+1:n，分別求出這兩段的最大子段和，則a1:n的最大子段和有三種情形： a1:n的最大子段和與a1:n/2的最大子段和相同； a1:n的最大子段和與an/2+1:n的最大子段和相同； a1:n的最大子段和為下面的形式。 A、B這兩種情形可遞歸求得。對(duì)于情形C，容易看出，an/2與an/2+1在最優(yōu)子序列中

22、。因此，我們可以在a1:n/2和an/2+1:n中分別計(jì)算出如下的s1和s2。則s1+s2即為出現(xiàn)情形C使得最優(yōu)值。 從而設(shè)計(jì)出下面所示的分治算法。,int MaxSubSum(int a, int left, int right) int sum=0; if (left=right)sum=aleft0?aleft:0; elseint center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int rightsum=MaxSubSum(a,center+1,right); int s1=0;lefts=0; for (int

23、 i=center;i=left;i-) lefts+=ai; if (leftss1) s1=lefts; int s2=0;rights=0; for (int i=center+1;is2) s2=rights; sum=s1+s2; if (sumleftsum) sum=leftsum; if (sumsightsum) sum=rightsum; return sum; ,38,3. 動(dòng)態(tài)規(guī)劃方法求解,在對(duì)上述分治算法的分析中我們注意到， 由bj的定義易知，當(dāng)bj-10時(shí)bj=bj-1+aj，否則bj=aj。由此可得計(jì)算bj的動(dòng)態(tài)規(guī)劃遞歸式bj=maxbj-1+aj，aj，1jn。

24、 據(jù)此，可設(shè)計(jì)出求最大子段和的動(dòng)態(tài)規(guī)劃算法如下： int MaxSum(int n, int a) int sum=0; b=0; for (i=1;i0) b+=ai; else b=ai; if (bsum) sum=b; return sum; 顯然該算法的計(jì)算時(shí)間為O(n)。,39,4. 算法的推廣,最大矩陣和問(wèn)題，略 最大m子段和問(wèn)題，略,40,3.5 凸多邊形最優(yōu)三角剖分,用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P=v0,v1,vn-1表示具有n條邊的凸多邊形。 若vi與vj是多邊形上不相鄰的2個(gè)頂點(diǎn)，則線段vivj稱(chēng)為多邊形的一條弦。弦將多邊形分割成2個(gè)多邊形vi,vi+1,vj

25、和vj,vj+1,vi。 多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。 給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得該三角剖分中諸三角形上權(quán)之和為最小。,41,三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題,一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹(shù)，稱(chēng)為表達(dá)式的語(yǔ)法樹(shù)。例如，完全加括號(hào)的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語(yǔ)法樹(shù)如圖 (a)所示。 凸多邊形v0,v1,vn-1的三角剖分也可以用語(yǔ)法樹(shù)表示。例如，圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語(yǔ)法樹(shù)表示。 矩陣連乘積中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1

26、)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，ij，對(duì)應(yīng)于矩陣連乘積Ai+1:j。,42,最優(yōu)子結(jié)構(gòu)性質(zhì),凸多邊形的最優(yōu)三角剖分問(wèn)題有最優(yōu)子結(jié)構(gòu)性質(zhì)。 事實(shí)上，若凸(n+1)邊形P=v0,v1,vn-1的最優(yōu)三角剖分T包含三角形v0vkvn，1kn-1，則T的權(quán)為3個(gè)部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形v0,v1,vk和vk,vk+1,vn的權(quán)之和?？梢詳嘌裕蒚所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衯0,v1,vk或vk,vk+1,vn的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。,43,最優(yōu)三角剖分的遞歸結(jié)構(gòu),定義tij，1ijn為凸子多邊形vi-1,

27、vi,vj的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。為方便起見(jiàn)，設(shè)退化的多邊形vi-1,vi具有權(quán)值0。據(jù)此定義，要計(jì)算的凸(n+1)邊形P的最優(yōu)權(quán)值為t1n。 tij的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。當(dāng)j-i1時(shí)，凸子多邊形至少有3個(gè)頂點(diǎn)。由最優(yōu)子結(jié)構(gòu)性質(zhì)，tij的值應(yīng)為tik的值加上tk+1j的值，再加上三角形vi-1vkvj的權(quán)值，其中ikj-1。由于在計(jì)算時(shí)還不知道k的確切位置，而k的所有可能位置只有j-i個(gè)，因此可以在這j-i個(gè)位置中選出使tij值達(dá)到最小的位置。由此，tij可遞歸地定義為：,44,計(jì)算最優(yōu)值,凸n+1邊形P=v0,v1,.,vn的最有三角剖分動(dòng)態(tài)規(guī)劃算法Min

28、WT： void MinWT(int n, type *t, int *s) for (int i=1;i=n;i+) tii=0; for (int r=2; r=n; r+) for (i=1; i=n; i+) int j=i+r-1; tij=tii+ti+1j+w(i-1,i,j); sij=i; for (int k=i+1;kj;k+) int u=tik+tk+1j+w(i-1,k,j); if (utij)tij=u;sij=k; 復(fù)雜性：T(n)=O(n3) S(n)=O(n2),45,構(gòu)造最優(yōu)解,思考：構(gòu)造一個(gè)在O(n)時(shí)間內(nèi)的求最優(yōu)解的算法。,46,3.6 多邊形游戲,

29、多邊形游戲是一個(gè)單人玩的游戲，開(kāi)始時(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ù)值通過(guò)邊E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。 最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。 問(wèn)題:對(duì)于給定的多邊形，計(jì)算最高得分。,47,最優(yōu)子結(jié)構(gòu)性質(zhì),設(shè)所給的多邊形的定點(diǎn)和便的順時(shí)針序列為： op1, v1, op

30、2, v2, ., opn, vn 在所給多邊形中，從頂點(diǎn)i(1in)開(kāi)始，長(zhǎng)度為j(鏈中有j個(gè)頂點(diǎn))的順時(shí)針鏈p(i，j) 可表示為vi，opi+1，vi+j-1。 如果這條鏈的最后一次合并運(yùn)算在opi+s處發(fā)生(1sj-1)，則可在opi+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分別是在所有可能的合并中得到的最小值和最大值。依此定義有am1b，cm2d (1)當(dāng)opi+s=+時(shí)，顯然有a+cmb+d (

31、2)當(dāng)opi+s=*時(shí)，有minac，ad，bc，bdmmaxac，ad，bc，bd 換句話說(shuō)，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。,48,遞歸求解,由前面的分析可知，為了求鏈合并的最大值，必須同時(shí)求子鏈合并的最大值和最小值。 設(shè)mi,j,0是鏈p(i,j)合并的最小值，mi,j,1是最大值。 若最優(yōu)合并在opi+s處將p(i,j)分為2個(gè)長(zhǎng)度小于j的子鏈p(i,s)和p(i+s,j-s)，且從頂點(diǎn)i開(kāi)始的長(zhǎng)度小于j的子鏈的最大值和最小值均已計(jì)算出。為敘述方便，記 a=mi,s,0，b=mi,s,1，c=mi+s,j-s,0，d=mi+s,j-s,0 (1)當(dāng)opi+s=+時(shí)，m

32、i,j,0=a+c，mi,j,1=b+d (2)當(dāng)opi+s=*時(shí)，mi,j,0=minac,ad,bc,bd，mi,j,1=maxac,ad,bc,bd 綜合(1)和(2)，將p(i,j)在opi+s處斷開(kāi)的最大值為maxf(i,j,s)，最小值為minf(i,j,s)，則 由于最優(yōu)斷開(kāi)位置s有1sj-1的j-1種情況，由此可知 初始邊界值顯然為mi,1,0=vi, mi,1,1=vi, 1in。,49,算法描述,算法描述：P63 算法復(fù)雜性：O(n3),50,3.7 圖像壓縮,圖象的變位壓縮存儲(chǔ)格式將所給的象素點(diǎn)序列p1,p2,pn,0pi255分割成m個(gè)連續(xù)段S1,S2,Sm。第i個(gè)象素

33、段Si中(1im)，有l(wèi)i個(gè)象素,且該段中每個(gè)象素都只用bi位表示。設(shè)則第i個(gè)象素段Si為 設(shè) ，則hibi8。因此需要用3位表示bi,如果限制1li255，則需要用8位表示li。因此，第i個(gè)象素段所需的存儲(chǔ)空間為li*bi+11位。按此格式存儲(chǔ)象素序列p1,p2,pn，需要位的存儲(chǔ)空間。 圖象壓縮問(wèn)題要求確定象素序列p1,p2,pn的最優(yōu)分段，使得依此分段所需的存儲(chǔ)空間最少。每個(gè)分段的長(zhǎng)度不超過(guò)256位。,51,最優(yōu)子結(jié)構(gòu)性質(zhì),設(shè)li，bi，是p1,p2,pn的最優(yōu)分段。顯而易見(jiàn)，l1，b1是p1,pl1的最優(yōu)分段，且li，bi，是pl1+1,pn的最優(yōu)分段。即圖象壓縮問(wèn)題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)

34、。 設(shè)si，1in，是象素序列p1,pn的最優(yōu)分段所需的存儲(chǔ)位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)易知： 其中 算法復(fù)雜度分析：由于算法compress中對(duì)k的循環(huán)次數(shù)不超這256，故對(duì)每一個(gè)確定的i，可在時(shí)間O(1)內(nèi)完成的計(jì)算。因此整個(gè)算法所需的計(jì)算時(shí)間為O(n)。,52,遞歸計(jì)算最優(yōu)值與構(gòu)造最優(yōu)解,遞歸計(jì)算最優(yōu)值算法描述：P6465 構(gòu)造最優(yōu)解算法描述：P6566 Compress：S(n)=O(n)，T(n)=O(n),53,3.8 電路布線,在一塊電路板的上、下2端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線(i,(i)將上端接線柱與下端接線柱相連，如圖所示。其中(i)是1,2,n的一個(gè)排列。導(dǎo)線(i

35、,(i)稱(chēng)為該電路板上的第i條連線。對(duì)于任何1i(j)。 電路布線問(wèn)題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說(shuō)，該問(wèn)題要求確定導(dǎo)線集Nets=(i,(i),1in的最大不相交子集。,=8，7，4，2，5，1，9，3，10，6,54,最優(yōu)子結(jié)構(gòu)性質(zhì),記N(i,j)=t|(t,(t)Nets,ti,(t)j，N(i,j)的最大不相交子集為MNS(i,j)，Size(i,j)=|MNS(i,j)|。 (1)當(dāng)i=1時(shí)， (2)當(dāng)i1時(shí)， j(i)。此時(shí)， (i,(i)N(i,j)。故在這種情況下，N(i,j)=N(i-1,j)，從而Size(i,j)=Size(i-1,j

36、)。 j(i)。若(i,(i)MNS(i,j) 。 則對(duì)任意(t,(t) MNS(i,j)有ti且(t)(i)。在這種情況下MNS(i,j)-(i,(i)是N(i-1,(i)-1)的最大不相交子集。若(i,(i)N(i,j)，則對(duì)任意(t,(t) MNS(i,j)有ti。從而MNS(i,j)N(i-1,j)。因此，Size(i,j)Size(i-1,j)。另一方面MNS(i-1,j)N(i,j)，故又有Size(i,j)Size(i-1,j)，從而Size(i,j)=Size(i-1,j)。 綜上可知，電路布線問(wèn)題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。,55,遞歸計(jì)算最優(yōu)值,算法描述：詳見(jiàn)P6768，計(jì)算最優(yōu)值

37、，構(gòu)造最優(yōu)解。 算法復(fù)雜性： MNS算法：T(n)=O(n2)，S(n)=(n2) Traceback算法：T(n)=O(n) 思考：求解目標(biāo)為最少層數(shù)時(shí)的算法問(wèn)題。,void MNS(C, n, *size) for (j=0; jC1; j+) size1j=0; for (j=C1; j=n; j+) size1j=0; for (i=2; in; i+) for (j=0; jCi; j+) sizeij=sizei-1j; for (j=Cj; j=n; j+) sizeij=maxsizei-1j, sizei-1Ci-1+1; sizenn=maxsizen-1n, sizen-

38、1Cn-1+1; ,void Traceback(C, *size, n, Net, m) int j=n; m=0; for (int i=n; i1; i-) if (sizeij!=sizei-1jNetm+=i; j=Ci-1; if (j=C1) Netm+=1; ,56,3.9 流水作業(yè)問(wèn)題,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)度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在機(jī)器M1上開(kāi)始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成

39、所需的時(shí)間最少。 分析： 直觀上，一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器M1沒(méi)有空閑時(shí)間，且機(jī)器M2的空閑時(shí)間最少。在一般情況下，機(jī)器M2上會(huì)有機(jī)器空閑和作業(yè)積壓2種情況。 設(shè)全部作業(yè)的集合為N=1，2，n。S是N的作業(yè)子集。在一般情況下，機(jī)器M1開(kāi)始加工S中作業(yè)時(shí)，機(jī)器M2還在加工其他作業(yè)，要等時(shí)間t后才可利用。將這種情況下完成S中作業(yè)所需的最短時(shí)間記為T(mén)(S,t)。流水作業(yè)調(diào)度問(wèn)題的最優(yōu)值為T(mén)(N,0)。,57,最優(yōu)子結(jié)構(gòu)性質(zhì),設(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

40、(1)。 證明：事實(shí)上，由T的定義知TT(S,b(1)。若TT(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)度矛盾。故TT(S,b(1)。從而T=T(S,b(1)。這就證明了流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。 由流水作業(yè)調(diào)度問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知， 思考：直接利用該遞歸關(guān)系構(gòu)造動(dòng)態(tài)規(guī)劃算法。,58,Johnson不等式,對(duì)遞歸式的深入分析表明，算法可進(jìn)一步得到簡(jiǎn)化。 設(shè)是作業(yè)集S在機(jī)器M2的等待時(shí)間為t時(shí)的任一最優(yōu)調(diào)度。若(1)=i, (2

41、)=j。則由動(dòng)態(tài)規(guī)劃遞歸式可得： T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij) 其中， 如果作業(yè)i和j滿足minbi,ajminbj,ai，則稱(chēng)作業(yè)i和j滿足Johnson不等式。,59,流水作業(yè)調(diào)度的Johnson法則,交換作業(yè)i和作業(yè)j的加工順序，得到作業(yè)集S的另一調(diào)度，它所需的加工時(shí)間為T(mén)(S,t)=ai+aj+T(S-i,j,tji) 其中， 當(dāng)作業(yè)i和j滿足Johnson不等式時(shí)，有 由此可見(jiàn)當(dāng)作業(yè)i和作業(yè)j不滿足Johnson不等式時(shí)，交換它們的加工順序后，不增加加工時(shí)間。對(duì)于流水作業(yè)調(diào)度問(wèn)題，必存在最優(yōu)調(diào)度 ，使得作業(yè)(i)和(

42、i+1)滿足Johnson不等式。進(jìn)一步還可以證明，調(diào)度滿足Johnson法則當(dāng)且僅當(dāng)對(duì)任意ij有 由此可知，所有滿足Johnson法則的調(diào)度均為最優(yōu)調(diào)度。,60,算法及其復(fù)雜性,流水作業(yè)調(diào)度問(wèn)題的Johnson算法： 令N1=i|aibi，N2=i|aibi； 將N1中作業(yè)依ai的非減序排序；將N2中作業(yè)依bi的非增序排序； N1中作業(yè)接N2中作業(yè)構(gòu)成滿足Johnson法則的最優(yōu)調(diào)度。 思考：上述步驟得到的作業(yè)序列滿足Johnson法則。 算法描述：P70。 算法復(fù)雜度分析：算法的主要計(jì)算時(shí)間花在對(duì)作業(yè)集的排序。因此，在最壞情況下算法所需的計(jì)算時(shí)間為O(nlogn)。所需的空間為O(n)。,

43、61,3.10 0-1背包問(wèn)題,給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大? 0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。,62,最優(yōu)子結(jié)構(gòu)性質(zhì),設(shè)所給0-1背包問(wèn)題的子問(wèn)題 的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，n時(shí)0-1背包問(wèn)題的最優(yōu)值。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下。,63,計(jì)算最優(yōu)值算法及其復(fù)雜性,算法描述：P72 算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算

44、時(shí)間較多。例如，當(dāng)c2n時(shí)，算法需要(n2n)計(jì)算時(shí)間。,64,算法改進(jìn),由m(i,j)的遞歸式容易證明，在一般情況下，對(duì)每一個(gè)確定的i(1in)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類(lèi)函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由其全部跳躍點(diǎn)惟一確定。如圖所示。 對(duì)每一個(gè)確定的i(1in)，用一個(gè)表pi存儲(chǔ)函數(shù)m(i，j)的全部跳躍點(diǎn)。表pi可依計(jì)算m(i，j)的遞歸式遞歸地由表pi+1計(jì)算，初始時(shí)pn+1=(0，0)。,示例：n=3，c=6，w=4,3,2，v=5,2,1。,66,關(guān)于m(i,j),函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-w

45、i)+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)wisc且(s-wi,t-vi)pi+1。因此，容易由pi+1確定跳躍點(diǎn)集qi+1如下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另一方面，設(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)。除受控跳躍點(diǎn)外，pi+1qi+1中的其他跳躍點(diǎn)均為pi中的跳躍點(diǎn)。

46、由此可見(jiàn)，在遞歸地由表pi+1計(jì)算表pi時(shí)，可先由pi+1計(jì)算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳躍點(diǎn)得到表pi。,67,另一個(gè)例子,實(shí)例： n=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的并集p5 q5=(0,0),(4,6),(5,4),(9,10)中看到跳躍點(diǎn)(5,4)受控于跳躍點(diǎn)(4,6)。將受控跳躍點(diǎn)(5,4)清除后，得到p4=(0,

47、0),(4,6),(9,10) 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。,68,算法復(fù)雜度分析,算法描述：P7475 上述算法的主要計(jì)算量在于計(jì)算跳躍點(diǎn)集pi(1in)。由于qi+1=

48、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)。,69,3.11 最優(yōu)二叉搜索樹(shù),什么是二叉搜索樹(shù)？ 若它的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的

49、值； 若它的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值； 它的左、右子樹(shù)也分別為二叉排序樹(shù) 在隨機(jī)的情況下，二叉查找樹(shù)的平均查找長(zhǎng)度和logn是等數(shù)量級(jí)的。,70,基本概念,具體地，設(shè)S=x1,x2,.,xn是一個(gè)有序集，且x1x2.xn。表示有序集S的二叉搜索樹(shù)利用二叉樹(shù)的結(jié)點(diǎn)來(lái)存儲(chǔ)有序集中的元素。它具有下述性質(zhì)：存儲(chǔ)于每個(gè)結(jié)點(diǎn)中的元素x大于其左子樹(shù)中任一結(jié)點(diǎn)所存儲(chǔ)的元素，小于其右子樹(shù)中任一結(jié)點(diǎn)所存儲(chǔ)的元素。二叉搜索樹(shù)的葉結(jié)點(diǎn)是形如(xi，xi+1)的開(kāi)區(qū)間。在表示S的二叉搜索樹(shù)中搜索一個(gè)元素x，返回的結(jié)果有兩種情形： 在二叉搜索樹(shù)的內(nèi)結(jié)點(diǎn)中找到x=xi。 在二叉搜索樹(shù)的葉結(jié)點(diǎn)中

50、確定x(xi，xi+1)。 設(shè)第一種情形中找到元素x=xi的概率為bi；在第二種情形中確定x(xi，xi+1)的概率為ai。并約定x0=-，xn+1=+。顯然有 (a0,b1,a1,.,bn,an)稱(chēng)為集合S的存取概率分布。 在表示S的二叉搜索樹(shù)T中，設(shè)存儲(chǔ)元素xi的結(jié)點(diǎn)深度為ci；存儲(chǔ)葉結(jié)點(diǎn)(xj,xj+1)的結(jié)點(diǎn)深度為dj，則 表示在二叉搜索樹(shù)T中作一次搜索所需要的平均比較次數(shù)。P又稱(chēng)為二叉搜索樹(shù)T的平均路長(zhǎng)。在一般情況下，不同的二叉樹(shù)的平均路長(zhǎng)時(shí)不相同的。,71,二叉查找樹(shù)的期望耗費(fèi)示例,72,最優(yōu)二叉搜索樹(shù),最優(yōu)二叉搜索樹(shù)問(wèn)題是對(duì)于有序集S及其存取概率分布(a0,b1,a1,.,bn,

51、an)，在所有表示有序集S的二叉搜索樹(shù)中找出一棵具有最小平均路長(zhǎng)的二叉搜索樹(shù)。 有n個(gè)節(jié)點(diǎn)的二叉樹(shù)的個(gè)數(shù)為：(4n/n3/2)。窮舉搜索法的時(shí)間復(fù)雜度為指數(shù)級(jí)。,73,最優(yōu)子結(jié)構(gòu),二叉搜索樹(shù)T的一棵含有結(jié)點(diǎn)xi,.,xj和葉結(jié)點(diǎn)(xi-1,xi),.,(xj,xj+1)的子樹(shù)可以看作是有序集xi,.,xj關(guān)于全集合x(chóng)i-1,xj+1的一棵二叉搜索樹(shù)，其存取概率為下面的條件概率 其中，wij=ai-1+bi+.+bj+aj。 設(shè)Tij是有序集合x(chóng)i,.,xj關(guān)于存取概率P的一棵最優(yōu)二叉搜索樹(shù)，其平均路長(zhǎng)為pij。Tij的根結(jié)點(diǎn)存儲(chǔ)元素xm，其左右子樹(shù)Tl和Tr的平均路長(zhǎng)分別為pl和pr。由于Tl和Tr中結(jié)點(diǎn)深度是他們?cè)赥ij中的結(jié)點(diǎn)深度減1，故我們有 由于Tl是關(guān)于集合x(chóng)i,.xm-1的一棵二叉搜索樹(shù)，故plpi,