第6章 動(dòng)態(tài)規(guī)劃法

1、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社第第6章章 動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法 6.1 概概 述述 6.2 圖問(wèn)題中的動(dòng)態(tài)規(guī)劃法圖問(wèn)題中的動(dòng)態(tài)規(guī)劃法6.3 組合問(wèn)題中的動(dòng)態(tài)規(guī)劃法組合問(wèn)題中的動(dòng)態(tài)規(guī)劃法6.4 查找問(wèn)題中的動(dòng)態(tài)規(guī)劃法查找問(wèn)題中的動(dòng)態(tài)規(guī)劃法6.5 實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目最大子段和問(wèn)題最大子段和問(wèn)題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社6.1 概概 述述 6.1.1 最優(yōu)化問(wèn)題最優(yōu)化問(wèn)題 6.1.2 最優(yōu)性原理最優(yōu)性原理6.1.3 動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 最優(yōu)化問(wèn)題：有最優(yōu)化問(wèn)題：有n個(gè)輸

2、入，它的解由這個(gè)輸入，它的解由這n個(gè)輸入個(gè)輸入的一個(gè)子集組成，這個(gè)子集必須滿足某些事先給定的一個(gè)子集組成，這個(gè)子集必須滿足某些事先給定的條件，這些條件稱為的條件，這些條件稱為約束條件約束條件，滿足約束條件的，滿足約束條件的解稱為問(wèn)題的解稱為問(wèn)題的可行解可行解。滿足約束條件的可行解可能。滿足約束條件的可行解可能不只一個(gè)，為了衡量這些可行解的優(yōu)劣，事先給出不只一個(gè)，為了衡量這些可行解的優(yōu)劣，事先給出一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)通常以函數(shù)的形式給出，這一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)通常以函數(shù)的形式給出，這些標(biāo)準(zhǔn)函數(shù)稱為些標(biāo)準(zhǔn)函數(shù)稱為目標(biāo)函數(shù)目標(biāo)函數(shù)，使目標(biāo)函數(shù)取得極值，使目標(biāo)函數(shù)取得極值（極大或極?。┑目尚薪夥Q為（極

3、大或極?。┑目尚薪夥Q為最優(yōu)解最優(yōu)解，這類問(wèn)題就，這類問(wèn)題就稱為稱為最優(yōu)化問(wèn)題最優(yōu)化問(wèn)題。 6.1.1 最優(yōu)化問(wèn)題最優(yōu)化問(wèn)題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社例：付款問(wèn)題：超市的自動(dòng)柜員機(jī)（POS機(jī)）要找給顧客數(shù)量最少的現(xiàn)金。 假定POS機(jī)中有n張面值為pi(1in)的貨幣，用集合P=p1, p2, , pn表示，如果POS機(jī)需支付的現(xiàn)金為A，那么，它必須從P中選取一個(gè)最小子集S，使得 （式6.1）miiiSmApSp1|)|(,如果用向量X=( x1, x2, , xn)表示S中所選取的貨幣，則 （式6.2） SpSpxiii01算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社

4、清華大學(xué)出版社 那么，POS機(jī)支付的現(xiàn)金必須滿足 （式6.3）Apxniii 1 并且 （式6.4） niixd1min 在付款問(wèn)題中，集合在付款問(wèn)題中，集合P是該問(wèn)題的輸入，滿足式是該問(wèn)題的輸入，滿足式6.1的的解稱為可行解，式解稱為可行解，式6.2是解的表現(xiàn)形式，因?yàn)橄蛄渴墙獾谋憩F(xiàn)形式，因?yàn)橄蛄縓中有中有n個(gè)個(gè)元素，每個(gè)元素的取值為元素，每個(gè)元素的取值為0或或1，所以，可以有，所以，可以有2n個(gè)不同的個(gè)不同的向量，所有這些向量的全體構(gòu)成該問(wèn)題的解空間，式向量，所有這些向量的全體構(gòu)成該問(wèn)題的解空間，式6.3是是該問(wèn)題的約束條件，式該問(wèn)題的約束條件，式6.4是該問(wèn)題的目標(biāo)函數(shù)，使式是該問(wèn)題的目

5、標(biāo)函數(shù)，使式6.4取取得極小值的解稱為該問(wèn)題的最優(yōu)解。得極小值的解稱為該問(wèn)題的最優(yōu)解。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社6.1.2 最優(yōu)性原理最優(yōu)性原理 對(duì)于一個(gè)具有對(duì)于一個(gè)具有n n個(gè)輸入的最優(yōu)化問(wèn)題，其求解個(gè)輸入的最優(yōu)化問(wèn)題，其求解過(guò)程往往可以劃分為若干個(gè)階段，每一階段的決策過(guò)程往往可以劃分為若干個(gè)階段，每一階段的決策僅依賴于前一階段的狀態(tài)，由決策所采取的動(dòng)作使僅依賴于前一階段的狀態(tài)，由決策所采取的動(dòng)作使?fàn)顟B(tài)發(fā)生轉(zhuǎn)移，成為下一階段決策的依據(jù)。從而，狀態(tài)發(fā)生轉(zhuǎn)移，成為下一階段決策的依據(jù)。從而，一個(gè)決策序列在不斷變化的狀態(tài)中產(chǎn)生。這個(gè)決策一個(gè)決策序列在不斷變化的狀態(tài)中產(chǎn)

6、生。這個(gè)決策序列產(chǎn)生的過(guò)程稱為多階段決策過(guò)程。序列產(chǎn)生的過(guò)程稱為多階段決策過(guò)程。 S0P1P2Pn 多階段決策過(guò)程多階段決策過(guò)程S1S2Sn-1Sn算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社Sn-1SnS1S0s1,1sn,knp1,1s1,k1p1,k1s1,r1 sn-1,kn-1pn,knpn-1,kn-1動(dòng)態(tài)規(guī)劃的決策過(guò)程動(dòng)態(tài)規(guī)劃的決策過(guò)程sn-1,1sn-1,rn-1sn,1sn,rn 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 在每一階段的決策中有一個(gè)賴以決策的策略或目標(biāo)，在每一階段的決策中有一個(gè)賴以決策的策略或目標(biāo)，這種策略或目標(biāo)是由問(wèn)題的性質(zhì)和特點(diǎn)所

7、確定，通常以函這種策略或目標(biāo)是由問(wèn)題的性質(zhì)和特點(diǎn)所確定，通常以函數(shù)的形式表示并具有遞推關(guān)系，稱為數(shù)的形式表示并具有遞推關(guān)系，稱為動(dòng)態(tài)規(guī)劃函數(shù)動(dòng)態(tài)規(guī)劃函數(shù)。 多階段決策過(guò)程滿足多階段決策過(guò)程滿足最優(yōu)性原理最優(yōu)性原理（Optimal Principle）：）：無(wú)論決策過(guò)程的初始狀態(tài)和初始決策是什么，其余的決策都無(wú)論決策過(guò)程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的當(dāng)前狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策必須相對(duì)于初始決策所產(chǎn)生的當(dāng)前狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策序列。序列。 如果一個(gè)問(wèn)題滿足最優(yōu)性原理通常稱此問(wèn)題具有如果一個(gè)問(wèn)題滿足最優(yōu)性原理通常稱此問(wèn)題具有最優(yōu)子最優(yōu)子結(jié)構(gòu)性質(zhì)結(jié)構(gòu)性質(zhì)。 算法設(shè)

8、計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社6.1.3 動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想 動(dòng)態(tài)規(guī)劃法將待求解問(wèn)題分解成若干個(gè)動(dòng)態(tài)規(guī)劃法將待求解問(wèn)題分解成若干個(gè)相互重相互重疊疊的子問(wèn)題，每個(gè)子問(wèn)題對(duì)應(yīng)決策過(guò)程的一個(gè)的子問(wèn)題，每個(gè)子問(wèn)題對(duì)應(yīng)決策過(guò)程的一個(gè)階段階段，一般來(lái)說(shuō)，子問(wèn)題的重疊關(guān)系表現(xiàn)在對(duì)給定問(wèn)題求一般來(lái)說(shuō)，子問(wèn)題的重疊關(guān)系表現(xiàn)在對(duì)給定問(wèn)題求解的解的遞推關(guān)系遞推關(guān)系（也就是動(dòng)態(tài)規(guī)劃函數(shù)）中，將子問(wèn)（也就是動(dòng)態(tài)規(guī)劃函數(shù)）中，將子問(wèn)題的解求解一次并題的解求解一次并填填入入表表中，當(dāng)需要再次求解此子中，當(dāng)需要再次求解此子問(wèn)題時(shí)，可以通過(guò)查表獲得該子問(wèn)題的解而不用再問(wèn)題時(shí)，可以通過(guò)查

9、表獲得該子問(wèn)題的解而不用再次求解，從而避免了大量重復(fù)計(jì)算。次求解，從而避免了大量重復(fù)計(jì)算。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 原問(wèn)題的解 原問(wèn)題 填 表子問(wèn)題1子問(wèn)題2子問(wèn)題n動(dòng)態(tài)規(guī)劃法的求解過(guò)程算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社n=5時(shí)分治法計(jì)算斐波那契數(shù)的過(guò)程。 F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：計(jì)算斐波那契數(shù)：2)2() 1(1100)(nnFnFnnnF算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社01234567890112358132134

10、動(dòng)態(tài)規(guī)劃法求解斐波那契數(shù)F(9)的填表過(guò)程 ： 注意到，計(jì)算F(n)是以計(jì)算它的兩個(gè)重疊子問(wèn)題 F(n-1)和F(n-2)的形式來(lái)表達(dá)的，所以，可以設(shè)計(jì)一張表填入n+1個(gè)F(n)的值。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題具有特征： 能夠分解為相互重疊的若干子問(wèn)題； 滿足最優(yōu)性原理（也稱最優(yōu)子結(jié)構(gòu)性質(zhì)）：該問(wèn)題的最優(yōu)解中也包含著其子問(wèn)題的最優(yōu)解。（用反證法）分析問(wèn)題是否滿足最優(yōu)性原理：1. 先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的;2. 然后再證明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解，從而導(dǎo)致矛盾。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出

11、版社清華大學(xué)出版社動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法一般分成三個(gè)階段：動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法一般分成三個(gè)階段：（1）分段分段：將原問(wèn)題分解為若干個(gè)相互重疊的子：將原問(wèn)題分解為若干個(gè)相互重疊的子問(wèn)題；問(wèn)題；（2）分析分析：分析問(wèn)題是否滿足最優(yōu)性原理，找出：分析問(wèn)題是否滿足最優(yōu)性原理，找出動(dòng)態(tài)規(guī)劃函數(shù)的遞推式；動(dòng)態(tài)規(guī)劃函數(shù)的遞推式；（3）求解求解：利用遞推式：利用遞推式自底向上自底向上計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過(guò)程。規(guī)劃過(guò)程。 v 動(dòng)態(tài)規(guī)劃法利用問(wèn)題的最優(yōu)性原理，以動(dòng)態(tài)規(guī)劃法利用問(wèn)題的最優(yōu)性原理，以自底向自底向上上的方式從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的方式從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。的最優(yōu)解

12、。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社6.2 圖問(wèn)題中的動(dòng)態(tài)規(guī)劃法圖問(wèn)題中的動(dòng)態(tài)規(guī)劃法 6.2.1 TSP問(wèn)題問(wèn)題 6.2.2 多段圖的最短路徑問(wèn)題多段圖的最短路徑問(wèn)題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社6.2.1 TSP問(wèn)題問(wèn)題 TSP問(wèn)題是指旅行家要旅行問(wèn)題是指旅行家要旅行n個(gè)城市，要求各個(gè)個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。所走的路程最短。 各個(gè)城市間的距離可以用代價(jià)矩陣來(lái)表示。各個(gè)城市間的距離可以用代價(jià)矩陣來(lái)表示。C= 3 6 7 5 2 3 6 4 2 3 7

13、5 帶權(quán)圖的代價(jià)矩陣帶權(quán)圖的代價(jià)矩陣算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 設(shè)s, s1, s2, , sp, s是從s出發(fā)的一條路徑長(zhǎng)度最短的簡(jiǎn)單回路，假設(shè)從s到下一個(gè)城市s1已經(jīng)求出，則問(wèn)題轉(zhuǎn)化為求從s1到s的最短路徑，顯然s1, s2, , sp, s一定構(gòu)成一條從s1到s的最短路徑。 如若不然，設(shè)s1, r1, r2, , rq, s是一條從s1到s的最短路徑且經(jīng)過(guò)n-1個(gè)不同城市，則s, s1, r1, r2, , rq, s將是一條從s出發(fā)的路徑長(zhǎng)度最短的簡(jiǎn)單回路且比s, s1, s2, , sp, s要短，從而導(dǎo)致矛盾。所以，TSP問(wèn)題滿足最優(yōu)性原理。證明證明T

14、SP問(wèn)題滿足最優(yōu)性原理問(wèn)題滿足最優(yōu)性原理算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社假設(shè)從頂點(diǎn)i出發(fā)，令d(i, V)表示從頂點(diǎn)i出發(fā)經(jīng)過(guò)V中各個(gè)頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)i的最短路徑長(zhǎng)度，開(kāi)始時(shí)，VVi，于是，TSP問(wèn)題的動(dòng)態(tài)規(guī)劃函數(shù)為：d(i,V)=mincik+d(k,Vk)(kV) （式6.5）d(k,)=cki(ki) （式6.6）算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社這是最后一個(gè)階段的決策，而：這是最后一個(gè)階段的決策，而： d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)d(2, 1, 3)=minc21+d(1,

15、3), c23+ d(3, 1)d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)這一階段的決策又依賴于下面的計(jì)算結(jié)果：這一階段的決策又依賴于下面的計(jì)算結(jié)果：d(1, 2)= c12+d(2, ) d(2, 3)=c23+d(3, ) d(3, 2)= c32+d(2, ) d(1, 3)= c13+d(3, ) d(2, 1)=c21+d(1, ) d(3, 1)=c31+d(1, ) 從城市從城市0出發(fā)經(jīng)城市出發(fā)經(jīng)城市1、2、3然后回到城市然后回到城市0的最短路徑長(zhǎng)度是：的最短路徑長(zhǎng)度是：d(0,1, 2, 3)=minc01+d(1, 2, 3), c02+d

16、(2, 1, 3), c03+d(3, 1, 2)而下式可以直接獲得（括號(hào)中是該決策引起的狀態(tài)轉(zhuǎn)移）：而下式可以直接獲得（括號(hào)中是該決策引起的狀態(tài)轉(zhuǎn)移）：d(1, )=c10=5(10) d(2, )=c20=6(20) d(3, )=c30=3(30)算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社再向前倒推，有：再向前倒推，有：d(1, 2)= c12+d(2, )=2+6=8(12) d(1, 3)= c13+d(3, )=3+3=6(13) d(2, 3)= c23+d(3, )=2+3=5(23) d(2, 1)= c21+d(1, )=4+5=9(21)d(3, 1)= c

17、31+d(1, )=7+5=12(31) d(3, 2)= c32+d(2, )=5+6=11(32)再向前倒退，有：再向前倒退，有：d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)=min2+5, 3+11=7(12)d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1)=min4+6, 2+12=10(21)d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)=min7+8, 5+9=14(32)最后有：最后有：d(0, 1, 2, 3)=minc01+ d(1, 2, 3), c02+ d(2, 1, 3),

18、 c03+ d(3, 1, 2) =min3+7, 6+10, 7+14=10(01) 所以，從頂點(diǎn)所以，從頂點(diǎn)0出發(fā)的出發(fā)的TSP問(wèn)題的最短路徑長(zhǎng)度為問(wèn)題的最短路徑長(zhǎng)度為10，路徑是，路徑是01230。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社假設(shè)n個(gè)頂點(diǎn)用0n-1的數(shù)字編號(hào)，首先生成1n-1個(gè)元素的子集存放在數(shù)組V2n-1中，設(shè)數(shù)組dn2n-1存放迭代結(jié)果，其中dij表示從頂點(diǎn)i經(jīng)過(guò)子集Vj中的頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)0的最短路徑長(zhǎng)度。 ji 1231, 21, 32, 31, 2, 30 1015 86 7 269 5 10 331211 14 動(dòng)態(tài)規(guī)劃法求解動(dòng)態(tài)

19、規(guī)劃法求解TSP問(wèn)題的填表過(guò)程問(wèn)題的填表過(guò)程算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法6.1TSP問(wèn)題 1for (i=1; in; i+) /初始化第0列 di0=ci0; 2for (j=1; j2n-1-1; j+) for (i=1; i=0; i-) 2.1 對(duì)頂點(diǎn)i的每一個(gè)鄰接點(diǎn)j，根據(jù)式6.7計(jì)算costi; 2.2 根據(jù)式6.8計(jì)算pathi; 3輸出最短路徑長(zhǎng)度cost0; 4. 輸出最短路徑經(jīng)過(guò)的頂點(diǎn)： 4.1 i=0 4.2 循環(huán)直到pathi=n-1 4.2.1 輸出pathi; 4.2.2 i=pathi; 算法6.2主要由三部分組成：第一部分是初始

20、化部分，其時(shí)間性能為O(n)；第二部分是依次計(jì)算各個(gè)頂點(diǎn)到終點(diǎn)的最短路徑，由兩層嵌套的循環(huán)組成，外層循環(huán)執(zhí)行n-1次，內(nèi)層循環(huán)對(duì)所有出邊進(jìn)行計(jì)算，并且在所有循環(huán)中，每條出邊只計(jì)算一次。假定圖的邊數(shù)為m，則這部分的時(shí)間性能是O(m)；第三部分是輸出最短路徑經(jīng)過(guò)的頂點(diǎn)，其時(shí)間性能是O(n)。所以，算法6.2的時(shí)間復(fù)雜性為O(n+m)。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社6.3 6.3 組合問(wèn)題中的動(dòng)態(tài)規(guī)劃法組合問(wèn)題中的動(dòng)態(tài)規(guī)劃法 6.3.1 0/1背包問(wèn)題背包問(wèn)題 6.3.2 最長(zhǎng)公共子序列問(wèn)題最長(zhǎng)公共子序列問(wèn)題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社6.3.

21、1 0/1背包問(wèn)題背包問(wèn)題 在在0/1背包問(wèn)題中，物品背包問(wèn)題中，物品i或者被裝入背包，或者不被或者被裝入背包，或者不被裝入背包，設(shè)裝入背包，設(shè)xi表示物品表示物品i裝入背包的情況，則當(dāng)裝入背包的情況，則當(dāng)xi=0時(shí)，時(shí)，表示物品表示物品i沒(méi)有被裝入背包，沒(méi)有被裝入背包，xi=1時(shí)，表示物品時(shí)，表示物品i被裝入背被裝入背包。根據(jù)問(wèn)題的要求，有如下約束條件和目標(biāo)函數(shù)：包。根據(jù)問(wèn)題的要求，有如下約束條件和目標(biāo)函數(shù)： )1 (1 , 01nixCxwiniii（式6.9）niiixv1max（式6.10）于是，問(wèn)題歸結(jié)為尋找一個(gè)滿足約束條件式于是，問(wèn)題歸結(jié)為尋找一個(gè)滿足約束條件式6.9，并使目標(biāo)，并

22、使目標(biāo)函數(shù)式函數(shù)式6.10達(dá)到最大的解向量達(dá)到最大的解向量X=(x1, x2, , xn)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社證明證明0/1背包問(wèn)題滿足最優(yōu)性原理。背包問(wèn)題滿足最優(yōu)性原理。 設(shè)設(shè)(x1, x2, , xn)是所給是所給0/1背包問(wèn)題的一個(gè)最優(yōu)解，則背包問(wèn)題的一個(gè)最優(yōu)解，則( x2, , xn)是下面一個(gè)子問(wèn)題的最優(yōu)解：是下面一個(gè)子問(wèn)題的最優(yōu)解：)2(1 ,0112nixxwCxwiniiiniiixv2max如若不然，設(shè)如若不然，設(shè)(y2, , yn)是上述子問(wèn)題的一個(gè)最優(yōu)解，則是上述子問(wèn)題的一個(gè)最優(yōu)解，則 因此，因此， 這說(shuō)明這說(shuō)明(x1, y2, ,

23、yn)是所給是所給0/1背包問(wèn)題比背包問(wèn)題比(x1, x2, , xn)更優(yōu)的更優(yōu)的解，從而導(dǎo)致矛盾。解，從而導(dǎo)致矛盾。 niiiniiixvyv22Cywxwniii211niiiniiiniiixvxvxvyvxv1211211算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 0/1背包問(wèn)題可以看作是決策一個(gè)序列背包問(wèn)題可以看作是決策一個(gè)序列(x1, x2, , xn)，對(duì)任，對(duì)任一變量一變量xi的決策是決定的決策是決定xi=1還是還是xi=0。在對(duì)。在對(duì)xi-1決策后，已確定了決策后，已確定了(x1, , xi-1)，在決策，在決策xi時(shí)，問(wèn)題處于下列兩種狀態(tài)之一：時(shí)，問(wèn)題處于下

24、列兩種狀態(tài)之一：（1）背包容量不足以裝入物品）背包容量不足以裝入物品i，則，則xi=0，背包不增加價(jià)值；，背包不增加價(jià)值；（2）背包容量可以裝入物品）背包容量可以裝入物品i，則，則xi=1，背包的價(jià)值增加了，背包的價(jià)值增加了vi。 這兩種情況下背包價(jià)值的最大者應(yīng)該是對(duì)這兩種情況下背包價(jià)值的最大者應(yīng)該是對(duì)xi決策后的背包決策后的背包價(jià)值。令價(jià)值。令V(i, j)表示在前表示在前i(1in)個(gè)物品中能夠裝入容量為個(gè)物品中能夠裝入容量為j（1jC）的背包中的物品的最大值，則可以得到如下動(dòng)態(tài)規(guī)）的背包中的物品的最大值，則可以得到如下動(dòng)態(tài)規(guī)劃函數(shù)：劃函數(shù)： V(i, 0)= V(0, j)=0 （式式6

25、.11）iiiiwjvwjiVjiVwjjiVjiV), 1(), 1(max), 1(),(（式6.12）算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 式6.11表明：把前面i個(gè)物品裝入容量為0的背包和把0個(gè)物品裝入容量為j的背包，得到的價(jià)值均為0。式6.12的第一個(gè)式子表明：如果第i個(gè)物品的重量大于背包的容量，則裝入前i個(gè)物品得到的最大價(jià)值和裝入前i-1個(gè)物品得到的最大價(jià)值是相同的，即物品i不能裝入背包；第二個(gè)式子表明：如果第i個(gè)物品的重量小于背包的容量，則會(huì)有以下兩種情況：（1）如果把第i個(gè)物品裝入背包，則背包中物品的價(jià)值等于把前i-1個(gè)物品裝入容量為j-wi的背包中的價(jià)值加

26、上第i個(gè)物品的價(jià)值vi；（2）如果第i個(gè)物品沒(méi)有裝入背包，則背包中物品的價(jià)值就等于把前i-1個(gè)物品裝入容量為j的背包中所取得的價(jià)值。顯然，取二者中價(jià)值較大者作為把前i個(gè)物品裝入容量為j的背包中的最優(yōu)解。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè)(n+1)(C+1)的二維表V，Vij表示把前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值。 0 例如，有5個(gè)物品，其重量分別是2, 2, 6, 5, 4，價(jià)值分別為6, 3, 5, 4, 6，背包的容量為10。x5=1x4=0 x3=0 x2=1x1=1 012345678910 00000000000w1=2

27、v1=6100666666666w2=2 v2=3200669999999w3=6 v3=5300669999111114w4=5 v4=44006699910111314w5=5 v5=6500669912121515150算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 按下述方法來(lái)劃分階段：第一階段，只裝入前1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；依此類推，直到第n個(gè)階段。最后，V(n,C)便是在容量為C的背包中裝入n個(gè)物品時(shí)取得的最大價(jià)值。為了確定裝入背包的具體物品，從V(n,C)的值向前推，如果

28、V(n,C)V(n-1,C)，表明第n個(gè)物品被裝入背包，前n-1個(gè)物品被裝入容量為C-wn的背包中；否則，第n個(gè)物品沒(méi)有被裝入背包，前n-1個(gè)物品被裝入容量為C的背包中。依此類推，直到確定第1個(gè)物品是否被裝入背包中為止。由此，得到如下函數(shù)： ), 1(), (, 1), 1(), (0jiVjiVwjjjiVjiVxii（式6.13） 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 設(shè)n個(gè)物品的重量存儲(chǔ)在數(shù)組wn中，價(jià)值存儲(chǔ)在數(shù)組vn中，背包容量為C，數(shù)組Vn+1C+1存放迭代結(jié)果，其中Vij表示前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值，數(shù)組xn存儲(chǔ)裝入背包的物品，動(dòng)態(tài)規(guī)劃法求解

29、0/1背包問(wèn)題的算法如下： 算法6.30/1背包問(wèn)題 int KnapSack(int n, int w , int v ) for (i=0; i=n; i+) /初始化第0列 Vi0=0; for (j=0; j=C; j+) /初始化第0行 V0j=0; for (i=1; i=n; i+) /計(jì)算第i行，進(jìn)行第i次迭代 for (j=1; j=C; j+) if (j0; i-) if (VijVi-1j) xi=1; j=j-wi;else xi=0;return VnC; /返回背包取得的最大價(jià)值 在算法6.3中，第一個(gè)for循環(huán)的時(shí)間性能是O(n)，第二個(gè)for循環(huán)的時(shí)間性能是O

30、(C)，第三個(gè)循環(huán)是兩層嵌套的for循環(huán)，其時(shí)間性能是O(nC)，第四個(gè)for循環(huán)的時(shí)間性能是O(n)，所以，算法6.3的時(shí)間復(fù)雜性為O(nC)。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社6.3.2 最長(zhǎng)公共子序列問(wèn)題最長(zhǎng)公共子序列問(wèn)題 對(duì)給定序列對(duì)給定序列X=(x1, x2, xm)和序列和序列Z=(z1, z2, zk)，Z是是X的子序列當(dāng)且僅當(dāng)存在一個(gè)嚴(yán)格遞增下標(biāo)序列的子序列當(dāng)且僅當(dāng)存在一個(gè)嚴(yán)格遞增下標(biāo)序列(i1, i2, ik)，使得對(duì)于所有，使得對(duì)于所有j=1, 2, , k，有，有zj=xi j（1ijm）。）。 給定兩個(gè)序列給定兩個(gè)序列X和和Y，當(dāng)另一個(gè)序列，當(dāng)另

31、一個(gè)序列Z既是既是X的子序的子序列又是列又是Y的子序列時(shí)，稱的子序列時(shí)，稱Z是序列是序列X和和Y的公共子序列。的公共子序列。最長(zhǎng)公共子序列問(wèn)題就是在序列最長(zhǎng)公共子序列問(wèn)題就是在序列X和和Y的公共子序列中的公共子序列中查找長(zhǎng)度最長(zhǎng)的公共子序列。查找長(zhǎng)度最長(zhǎng)的公共子序列。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社證明最長(zhǎng)公共子序列問(wèn)題滿足最優(yōu)性原理。證明最長(zhǎng)公共子序列問(wèn)題滿足最優(yōu)性原理。設(shè)序列設(shè)序列X=x1, x2, xm和和Y=y1, y2, yn的最長(zhǎng)公共子序列的最長(zhǎng)公共子序列為為Z=z1, z2, zk，記，記Xk為序列為序列X中前中前k個(gè)連續(xù)字符組成的子個(gè)連續(xù)字符組成的子序

32、列，序列，Yk為序列為序列Y中前中前k個(gè)連續(xù)字符組成的子序列，個(gè)連續(xù)字符組成的子序列，Zk為序列為序列Z中前中前k個(gè)連續(xù)字符組成的子序列，顯然有下式成立：個(gè)連續(xù)字符組成的子序列，顯然有下式成立：（1）若）若xm=yn，則，則zk=xm=yn，且，且Zk-1是是Xm-1和和Yn-1的最長(zhǎng)公共子的最長(zhǎng)公共子序列；序列；（2）若）若xmyn且且zkxm，則，則Z是是Xm-1和和Y的最長(zhǎng)公共子序列；的最長(zhǎng)公共子序列；（3）若）若xmyn且且zkyn，則，則Z是是X和和Yn-1的最長(zhǎng)公共子序列。的最長(zhǎng)公共子序列。 可見(jiàn)，兩個(gè)序列的最長(zhǎng)公共子序列包含了這兩個(gè)序列的可見(jiàn)，兩個(gè)序列的最長(zhǎng)公共子序列包含了這兩個(gè)

33、序列的前綴序列的最長(zhǎng)公共子序列。前綴序列的最長(zhǎng)公共子序列。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社要找出序列要找出序列X=x1, x2, xm和和Y=y1, y2, yn的最長(zhǎng)公共子的最長(zhǎng)公共子序列，可按下述遞推方式計(jì)算：當(dāng)序列，可按下述遞推方式計(jì)算：當(dāng)xm=yn時(shí)，找出時(shí)，找出Xm-1和和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上的最長(zhǎng)公共子序列，然后在其尾部加上x(chóng)m即可得到即可得到X和和Y的最的最長(zhǎng)公共子序列；當(dāng)長(zhǎng)公共子序列；當(dāng)xmyn時(shí)，必須求解兩個(gè)子問(wèn)題：找出時(shí)，必須求解兩個(gè)子問(wèn)題：找出Xm-1和和Y的最長(zhǎng)公共子序列以及的最長(zhǎng)公共子序列以及Xm和和Yn-1的最長(zhǎng)公共子序

34、列，這兩的最長(zhǎng)公共子序列，這兩個(gè)公共子序列中的較長(zhǎng)者即為個(gè)公共子序列中的較長(zhǎng)者即為X和和Y的最長(zhǎng)公共子序列。用的最長(zhǎng)公共子序列。用Lij表示子序列表示子序列Xi和和Yj的最長(zhǎng)公共子序列的長(zhǎng)度，可得如下的最長(zhǎng)公共子序列的長(zhǎng)度，可得如下動(dòng)態(tài)規(guī)劃函數(shù)：動(dòng)態(tài)規(guī)劃函數(shù)：L00=Li0=L0j=0(1im,1jn) （式（式6.14） （式（式6.15）1, 1,1jLi1,Lijmax1, 1,111jLiLijjiyxjiyxjiji算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 由此，把序列由此，把序列X=x1, x2, xm和和Y=y1, y2, yn的最長(zhǎng)的最長(zhǎng)公共子序列的搜索分為公共

35、子序列的搜索分為m個(gè)階段，第個(gè)階段，第1階段，按照式階段，按照式6.15計(jì)計(jì)算算X1和和Yj的最長(zhǎng)公共子序列長(zhǎng)度的最長(zhǎng)公共子序列長(zhǎng)度L1j（1jn），第），第2階階段，按照式段，按照式6.15計(jì)算計(jì)算X2和和Yj的最長(zhǎng)公共子序列長(zhǎng)度的最長(zhǎng)公共子序列長(zhǎng)度L2j（1jn），依此類推，最后在第），依此類推，最后在第m階段，計(jì)算階段，計(jì)算Xm和和Yj的的最長(zhǎng)公共子序列長(zhǎng)度最長(zhǎng)公共子序列長(zhǎng)度Lmj（1jn），則），則Lmn就是就是序列序列Xm和和Yn的最長(zhǎng)公共子序列的長(zhǎng)度。的最長(zhǎng)公共子序列的長(zhǎng)度。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 為了得到序列Xm和Yn具體的最長(zhǎng)公共子序列，設(shè)二

36、維表Sm+1n+1，其中Sij表示在計(jì)算Lij的過(guò)程中的搜索狀態(tài)，并且有： 1jLi1Lij31jLi1Lij21Sij且且jijijiyxyxyx（式6.16） 若Sij=1，表明ai=bj，則下一個(gè)搜索方向是Si-1j-1；若Sij=2，表明aibj且Lij-1Li-1j，則下一個(gè)搜索方向是Sij-1；若Sij=3，表明aibj且Lij-1Li-1j，則下一個(gè)搜索方向是Si-1j。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社(a) 長(zhǎng)度矩陣長(zhǎng)度矩陣L (b) 狀態(tài)矩陣狀態(tài)矩陣S01234567890123456789000000000000000000000101111111

37、111012221222220112222222203211212113012222222230312222222401233333334033113131150123333444503332221226012344445560331131211例：序列例：序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，建，建立兩個(gè)立兩個(gè)(m+1)(n+1)的二維表的二維表L和表和表S，分別存放搜索過(guò)程，分別存放搜索過(guò)程中得到的子序列的長(zhǎng)度和狀態(tài)。中得到的子序列的長(zhǎng)度和狀態(tài)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法算法6.4最長(zhǎng)公共

38、子序列問(wèn)題最長(zhǎng)公共子序列問(wèn)題 int CommonOrder(int m, int n, int x , int y , int z ) for (j=0; j=n; j+) /初始化第初始化第0行行 L0j=0; for (i=0; j=m; i+) /初始化第初始化第0列列 Li0=0; for (i=1; i=m; i+) for (j=1; j=Li- -1j) Lij=Lij- -1; Sij=2; else Lij=Li- -1j; Sij=3; i=m; j=n; k=Lmn; for (i0 & j0) if (Sij= =1) zk=xi; k-; i-; j-; else

39、if (Sij= =2) j-; else i-; return Lmn; 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 在算法在算法6.4中，中，第一個(gè)第一個(gè)for循環(huán)的時(shí)間性能是循環(huán)的時(shí)間性能是O(n)；第二個(gè)第二個(gè)for循環(huán)的時(shí)間性能是循環(huán)的時(shí)間性能是O(m)；第三個(gè)循環(huán)是兩層嵌套的第三個(gè)循環(huán)是兩層嵌套的for循環(huán)，其時(shí)間性能是循環(huán)，其時(shí)間性能是O(mn)；第四個(gè)第四個(gè)for循環(huán)的時(shí)間性能是循環(huán)的時(shí)間性能是O(k)，而，而kminm, n，所以，算法所以，算法6.4的時(shí)間復(fù)雜性是的時(shí)間復(fù)雜性是O(mn)。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社6.4 查找問(wèn)

40、題中的動(dòng)態(tài)規(guī)劃法查找問(wèn)題中的動(dòng)態(tài)規(guī)劃法 6.4.1 最優(yōu)二叉查找樹(shù)最優(yōu)二叉查找樹(shù) 6.4.2 近似串匹配問(wèn)題近似串匹配問(wèn)題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 設(shè)設(shè)r1, r2, , rn是是n個(gè)記錄的集合，其查找概率分別是個(gè)記錄的集合，其查找概率分別是p1, p2, , pn，最優(yōu)二叉查找樹(shù)（，最優(yōu)二叉查找樹(shù)（Optimal Binary Search Trees）是以這）是以這n個(gè)記錄構(gòu)成的二叉查找樹(shù)中具有最少平均個(gè)記錄構(gòu)成的二叉查找樹(shù)中具有最少平均比較次數(shù)的二叉查找樹(shù)，即比較次數(shù)的二叉查找樹(shù)，即 最小，其中最小，其中pi是記錄是記錄ri的查找概率，的查找概率，ci是在

41、二叉查找樹(shù)是在二叉查找樹(shù)中查找中查找ri的比較次數(shù)。的比較次數(shù)。 6.4.1 最優(yōu)二叉查找樹(shù)最優(yōu)二叉查找樹(shù) niiicp1算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社ABCD (a) (b) (c)二叉查找樹(shù)示例二叉查找樹(shù)示例BCDAABCD例如，集合例如，集合A, B, C, D的查找概率是的查找概率是0.1, 0.2, 0.4, 0.3， (a)的平均比較次數(shù)是的平均比較次數(shù)是0.110.22+0.43+0.34=2.9，(b)的平均比較次數(shù)是的平均比較次數(shù)是0.120.21+0.42+0.33=2.1，(c)的平均比較次數(shù)是的平均比較次數(shù)是0.130.22+0.41+0.32

42、=1.7。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社將由將由r1, r2, , rn構(gòu)成的二叉查找樹(shù)記為構(gòu)成的二叉查找樹(shù)記為T(mén)(1, n)，其中，其中rk（1kn）是是T(1, n)的根結(jié)點(diǎn)，則其左子樹(shù)的根結(jié)點(diǎn)，則其左子樹(shù)T(1, k- -1)由由r1, , rk-1構(gòu)成，其右子構(gòu)成，其右子樹(shù)樹(shù)T(k+1, n)由由rk+1, , rn構(gòu)成。構(gòu)成。證明最優(yōu)二叉查找樹(shù)滿足最優(yōu)性原理rkT(1, n) 以以rk為根的二叉查找樹(shù)為根的二叉查找樹(shù)T(k+1,n)T(1,k- -1)若若T(1, n)是最優(yōu)二叉查找樹(shù)，則其左是最優(yōu)二叉查找樹(shù)，則其左子樹(shù)子樹(shù)T(1, k-1)和右子樹(shù)和右子樹(shù)

43、T(k+1, n)也是也是最優(yōu)二叉查找樹(shù)，如若不然，假設(shè)最優(yōu)二叉查找樹(shù)，如若不然，假設(shè)T(1, k-1)是比是比T(1, k-1)更優(yōu)的二叉查更優(yōu)的二叉查找樹(shù)，則找樹(shù)，則T(1, k-1)的平均比較次數(shù)小的平均比較次數(shù)小于于T(1, k-1)的平均比較次數(shù)，從而由的平均比較次數(shù)，從而由T(1, k-1)、rk和和T(k+1, n)構(gòu)成的二叉構(gòu)成的二叉查找樹(shù)查找樹(shù)T(1, n)的平均比較次數(shù)小于的平均比較次數(shù)小于T(1, n)的平均比較次數(shù)，這與的平均比較次數(shù)，這與T(1, n)是最優(yōu)二叉查找樹(shù)的假設(shè)相矛盾。是最優(yōu)二叉查找樹(shù)的假設(shè)相矛盾。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社

44、設(shè)設(shè)T(i, j)是由記錄是由記錄ri, , rj(1ijn)構(gòu)成的二叉查找構(gòu)成的二叉查找樹(shù)，樹(shù)，C(i, j)是這棵二叉查找樹(shù)的平均比較次數(shù)。雖然最后的是這棵二叉查找樹(shù)的平均比較次數(shù)。雖然最后的結(jié)果是結(jié)果是C(1, n)，但遵循動(dòng)態(tài)規(guī)劃法的求解方法，但遵循動(dòng)態(tài)規(guī)劃法的求解方法,需要求出所需要求出所有較小子問(wèn)題有較小子問(wèn)題C(i, j)的值，考慮從的值，考慮從ri, , rj中選擇一個(gè)記錄中選擇一個(gè)記錄rk作為二叉查找樹(shù)的根結(jié)點(diǎn)，可以得到如下關(guān)系：作為二叉查找樹(shù)的根結(jié)點(diǎn)，可以得到如下關(guān)系： ), 1() 1,(min), 1() 1,(min), 1() 1,(min ) 1), 1() 1)

45、 1,(1min),(11111111jissjkijisskisjksssssjkijksskisjkssskisssskjkikisjkssssskjkipjkCkiCpnkTrpkiTrppnkTrppkiTrppnkTrpkiTrppjiC中的層數(shù)在中的層數(shù)在中的層數(shù)在中的層數(shù)在中的層數(shù)在中的層數(shù)在算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社因此，得到如下動(dòng)態(tài)規(guī)劃函數(shù)：因此，得到如下動(dòng)態(tài)規(guī)劃函數(shù)： C(i, i-1)=0 (1in+1) （式（式6.17）C(i, i)=pi (1in) （式（式6.18）C(i, j)=minC(i, k-1)+C(k+1, j)+ (1

46、ijn, ikj) （式（式6.19）設(shè)一個(gè)二維表設(shè)一個(gè)二維表Cn+1n+1，其中，其中Cij表示二叉查找樹(shù)表示二叉查找樹(shù)T(i, j)的平均比較次數(shù)。注意到在式的平均比較次數(shù)。注意到在式6.19中，當(dāng)中，當(dāng)k=1時(shí)，求時(shí)，求Cij需需要用到要用到Ci0，當(dāng)，當(dāng)k=n時(shí)，求時(shí)，求Cij需要用到需要用到Cn+1j，所以，所以，二維表二維表Cn+1n+1行下標(biāo)的范圍為行下標(biāo)的范圍為1n+1，列下標(biāo)的范圍，列下標(biāo)的范圍為為0n。 為了在求出由為了在求出由r1, r2, , rn構(gòu)成的二叉查找樹(shù)的平均比構(gòu)成的二叉查找樹(shù)的平均比較 次 數(shù) 的 同 時(shí) 得 到 最 優(yōu) 二 叉 查 找 樹(shù) ， 設(shè) 一 個(gè)

47、二 維 表較 次 數(shù) 的 同 時(shí) 得 到 最 優(yōu) 二 叉 查 找 樹(shù) ， 設(shè) 一 個(gè) 二 維 表Rn+1n+1，其下標(biāo)范圍與二維表，其下標(biāo)范圍與二維表C相同，相同，Rij表示二叉表示二叉查找樹(shù)查找樹(shù)T(i, j)的根結(jié)點(diǎn)的序號(hào)。的根結(jié)點(diǎn)的序號(hào)。jissp算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 例如，集合A, B, C, D的查找概率是0.1, 0.2, 0.4, 0.3，二維表C和R的初始情況如圖6.13所示。 01234100.1 2 00.2 3 00.4 4 00.35 0 012341 1 2 2 3 3 4 45 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出

48、版社 在二維表在二維表C和和R中只需計(jì)算主對(duì)角線以上的元素。中只需計(jì)算主對(duì)角線以上的元素。首先計(jì)算首先計(jì)算C(1, 2)： 4 . 04 . 03 . 001 . 0)2 , 3() 1 , 1 (:25 . 03 . 02 . 00)2 , 2()0 , 1 (:1min)2 , 1 (2121sssspCCkpCCkC在前兩個(gè)記錄構(gòu)成的最優(yōu)二叉查找樹(shù)的根結(jié)點(diǎn)的序號(hào)是在前兩個(gè)記錄構(gòu)成的最優(yōu)二叉查找樹(shù)的根結(jié)點(diǎn)的序號(hào)是2。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社按對(duì)角線逐條計(jì)算每一個(gè)按對(duì)角線逐條計(jì)算每一個(gè)C(i, j)和和R(i, j)，得到最終表。，得到最終表。 0123410

49、0.10.41.11.72 00.20.81.43 00.41.04 00.35 0 012341 12 2332 2333 334 45 (a) 二維表C (b) 二維表R 最終表的狀態(tài)d=1d=2d=3d=1d=2d=3算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社設(shè)n個(gè)字符的查找概率存儲(chǔ)在數(shù)組pn中，動(dòng)態(tài)規(guī)劃法求解最優(yōu)二叉查找樹(shù)的算法如下：算法算法6.5最優(yōu)二叉查找樹(shù)最優(yōu)二叉查找樹(shù) double OptimalBST(int n, double p , double C , int R ) for (i=1; i=n; i+) /按式按式6.17和式和式6.18初始化初始化 C

50、ii-1=0; Cii=pi; Rii=i; Cn+1n=0; 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社for (d=1; dn; d+) /按對(duì)角線逐條計(jì)算按對(duì)角線逐條計(jì)算 for (i=1; i=n-d; i+) j=i+d; min=; mink=i; sum=0; for (k=i; k=j; k+) sum=sum+pk; if (Cik-1+Ck+1jmin) min=Cik-1+Ck+1j; mink=k; Cij=min+sum; Rij=mink; return C1n;算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社6.4.2 近似串匹配問(wèn)題近似串匹

51、配問(wèn)題 設(shè)樣本設(shè)樣本P=p1p2pm，文本，文本T=t1t2tn，對(duì)于一個(gè)非負(fù)，對(duì)于一個(gè)非負(fù)整數(shù)整數(shù)K，樣本，樣本P在文本在文本T中的中的K-近似匹配（近似匹配（K-approximate Match）是指）是指P在在T中包含至多中包含至多K個(gè)差別個(gè)差別的匹配（一般情況下，假設(shè)樣本是正確的）。這里的匹配（一般情況下，假設(shè)樣本是正確的）。這里的差別是指下列三種情況之一：的差別是指下列三種情況之一：（1）修改：）修改：P與與T中對(duì)應(yīng)字符不同；中對(duì)應(yīng)字符不同；（2）刪去：）刪去：T中含有一個(gè)未出現(xiàn)在中含有一個(gè)未出現(xiàn)在P中的字符；中的字符；（3）插入：）插入：T中不含有出現(xiàn)在中不含有出現(xiàn)在P中的一個(gè)字

52、符。中的一個(gè)字符。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 T: a p r o x i o m a l l y P: a p p r o x i m a t l y 3-近似匹配（近似匹配（為刪去為刪去為插入為插入為修改）為修改）樣本樣本P和文本和文本T為為K-近似匹配包含兩層含義：近似匹配包含兩層含義：（1）二者的差別數(shù)至多為）二者的差別數(shù)至多為K；（2）差別數(shù)是指二者在所有匹配對(duì)應(yīng)方式下的最小編輯錯(cuò)）差別數(shù)是指二者在所有匹配對(duì)應(yīng)方式下的最小編輯錯(cuò)誤總數(shù)。誤總數(shù)。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社證明近似串匹配問(wèn)題滿足最優(yōu)性原理。證明近似串匹配問(wèn)題滿足最優(yōu)性原理。如果樣本如果樣本p1p2pm在文本在文本T的某一位置上有最優(yōu)（差別數(shù)最的某一位置上有最優(yōu)（差別數(shù)最?。┑膶?duì)應(yīng)關(guān)系，則樣本小）的對(duì)應(yīng)關(guān)系，則樣本P的任意一個(gè)子串的任意一個(gè)子串pipj（1ijm）與文本）與文本T的對(duì)應(yīng)關(guān)系也必然是最優(yōu)的。的對(duì)應(yīng)關(guān)系也必然是最優(yōu)的。動(dòng)態(tài)規(guī)劃函數(shù)：動(dòng)態(tài)規(guī)劃函數(shù)：定義一個(gè)代價(jià)函數(shù)定義一個(gè)代價(jià)函數(shù)D(i, j)(0im,0jn)表示樣本前綴子串表示樣本前綴子串p1pi與文本前綴子串與文本前綴子串t1tj之間的最小差別數(shù)，則之間的最小差別數(shù)，則D(m, n)表表示樣本示