第五章-動(dòng)態(tài)規(guī)劃詳解課件

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

動(dòng)態(tài)規(guī)劃概述數(shù)塔最小代價(jià)子母樹(shù)非優(yōu)化問(wèn)題實(shí)例單起點(diǎn)最短路徑問(wèn)題最優(yōu)二叉查找樹(shù)

01背包問(wèn)題第5章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃概述動(dòng)態(tài)規(guī)劃概述

動(dòng)態(tài)規(guī)劃概述動(dòng)態(tài)規(guī)劃（DynamicProgramming），在20世紀(jì)50年代由美國(guó)數(shù)學(xué)家RichardBellman（理查德.貝爾曼）發(fā)明，作為多階段決策過(guò)程最優(yōu)化的一種通用方法，對(duì)最優(yōu)化問(wèn)題提出最優(yōu)性原則，從而創(chuàng)建最優(yōu)化問(wèn)題的一種新算法設(shè)計(jì)技術(shù)——?jiǎng)討B(tài)規(guī)劃，它是一種重要的應(yīng)用數(shù)學(xué)工具。至少在計(jì)算機(jī)科學(xué)圈子里，人們不僅用它解決特定類型的最優(yōu)化問(wèn)題，而最終把它作為一種通用的算法設(shè)計(jì)技術(shù)，即包括某些非最優(yōu)化問(wèn)題。多階段決策過(guò)程最優(yōu)化：現(xiàn)實(shí)世界里有許多問(wèn)題屬于這種情況：它有很多解，應(yīng)用要求最優(yōu)解。窮舉法通過(guò)找出全部解，再?gòu)闹羞x出最優(yōu)解。這種方法對(duì)于那些計(jì)算復(fù)雜度很高、計(jì)算量很大的問(wèn)題（如求最佳子集的組合問(wèn)題），要找出一切可能解，所耗費(fèi)的計(jì)算時(shí)間可能是不可以接受的。因此，人們?yōu)榱私档颓蠼鈫?wèn)題的難度，把求解過(guò)程分為一系列階段，各個(gè)階段依次按照最優(yōu)性原則計(jì)算，最后階段計(jì)算得到最優(yōu)解。包括分段、求解兩大步。注：不能段化的問(wèn)題不能用動(dòng)態(tài)規(guī)劃法求解。動(dòng)態(tài)規(guī)劃概述動(dòng)態(tài)規(guī)劃概述最優(yōu)性原則階段1階段2......階段n求解算法求解算法求解算法多階段決策過(guò)程圖示動(dòng)態(tài)的含義：求解算法施加的狀態(tài)是變化的。當(dāng)前狀態(tài)只與其直接前趨狀態(tài)有關(guān)，對(duì)其直接前趨狀態(tài)施加求解算法，成為當(dāng)前狀態(tài)。最優(yōu)性原則(PrincipleofOptimality)：一個(gè)最優(yōu)問(wèn)題任何實(shí)例的最優(yōu)解，是由該實(shí)例的子實(shí)例的最優(yōu)解組成的。對(duì)特定問(wèn)題該原則不一定滿足（罕見(jiàn)），有必要檢查其適用性。子實(shí)例組成父實(shí)例，父實(shí)例分解為子實(shí)例。對(duì)于某些多階段決策問(wèn)題，問(wèn)題本身沒(méi)有最優(yōu)化要求，比如后面要講到的求中國(guó)象棋馬從棋盤上一點(diǎn)移動(dòng)到另一點(diǎn)的全部路徑問(wèn)題，又如計(jì)算裴波那契序列的動(dòng)態(tài)規(guī)劃算法，它們屬于非最優(yōu)化問(wèn)題的動(dòng)態(tài)規(guī)劃法。動(dòng)態(tài)規(guī)劃法的特點(diǎn)：1.分階段（級(jí)）決策。對(duì)最優(yōu)化問(wèn)題，用最優(yōu)性原則設(shè)計(jì)。2.一般采用自頂向下分析（規(guī)模減?。?，自底向上計(jì)算（規(guī)模增加）。計(jì)算過(guò)程是一級(jí)一級(jí)（一階段一階段）地向前推進(jìn)，直到最終狀態(tài)。最優(yōu)性原則階段1階段2......階段n求解算法求解算數(shù)塔

數(shù)塔問(wèn)題：設(shè)有一三角形數(shù)塔如圖。求一條自塔頂?shù)剿椎穆窂?，該路徑?/p>

節(jié)點(diǎn)值之和最大。分段：每一級(jí)臺(tái)階自然劃分為一個(gè)階段，成為多階段決策的優(yōu)化問(wèn)題。無(wú)法分段的問(wèn)題，不能用動(dòng)態(tài)規(guī)劃法求解。求解：動(dòng)態(tài)規(guī)劃法求解。自底向上計(jì)算，各實(shí)例計(jì)算滿足最優(yōu)性原則，如實(shí)例18的子實(shí)例為12和7，max(12+6,7+6)=18。5級(jí)4級(jí)3級(jí)2級(jí)1級(jí)182739326746657873911311874014261582467131211數(shù)塔數(shù)塔分段：每一級(jí)臺(tái)階自然劃分為一個(gè)階段，成為多階段決策數(shù)塔問(wèn)題：動(dòng)態(tài)規(guī)劃法與窮舉法效率比較

數(shù)塔：動(dòng)態(tài)規(guī)劃法與窮舉法的時(shí)間效率比較輸入規(guī)模：為便于分析，選擇數(shù)塔層數(shù)k(k>0)；基本操作：節(jié)點(diǎn)值求和運(yùn)算；增長(zhǎng)函數(shù)：加法次數(shù)與k的關(guān)系；效率類別：沒(méi)有最佳、最差情況；（都要從塔頂計(jì)算到塔底）增長(zhǎng)率（次數(shù)）：各層節(jié)點(diǎn)數(shù)升序：1,2,3,4,5,6,7,8,9,10,...

節(jié)點(diǎn)總數(shù)

n

升序：1,3,6,10,15,21,28,36,45,55,...

層數(shù)k（頂為1）：1,2,3,4,5,6,7,8,9,10,...

路徑總數(shù)t升序：

2,

4,8,16,32,...,t=2k-1,k>11.窮舉法：T(k)=(k-1)2k-1，k>1（指數(shù)級(jí)）本例k=5，每條路徑上5個(gè)節(jié)點(diǎn)做4次加法，共64次加法。2.動(dòng)態(tài)規(guī)劃法：（層節(jié)點(diǎn)數(shù)=層數(shù)）自底向上計(jì)算，k層加法總數(shù)為k-1層節(jié)點(diǎn)數(shù)×2，有效率計(jì)算式：

T(k)=2×(k-1+...+3+2+1)=k(k-1),k>1（平方級(jí)）本例加法總數(shù)2×(4+3+2+1)=20次，比64次少很多。數(shù)塔問(wèn)題：動(dòng)態(tài)規(guī)劃法與窮舉法效率比較數(shù)塔：動(dòng)態(tài)規(guī)劃法與窮舉非最優(yōu)化問(wèn)題實(shí)例

非最優(yōu)化問(wèn)題實(shí)例求中國(guó)象棋馬的路徑

問(wèn)題：在m×n棋盤上，求馬從P點(diǎn)跳到Q點(diǎn)的所有路徑。654321654321654321可用回溯法和遞歸法求解，但遞歸法效率很低，?？臻g占用很大。非最優(yōu)化問(wèn)題實(shí)例非最優(yōu)化問(wèn)題實(shí)例654最小代價(jià)子母樹(shù)

最小代價(jià)子母樹(shù)

問(wèn)題：n(n>1)堆沙子，重量向量W=(w1,...wn)。要將它們歸并為1堆，歸并規(guī)則：每次只能將相鄰2堆歸并為1堆，經(jīng)過(guò)n-1次歸并后，最終歸并為一堆?？偞鷥r(jià)為歸并過(guò)程中新產(chǎn)生的沙堆質(zhì)量之和，這個(gè)代價(jià)最小的歸并樹(shù)稱為最小代價(jià)子母樹(shù)。分析：屬于最優(yōu)化問(wèn)題，目標(biāo)為總代價(jià)最小。分段：顯然需要n-1次歸并才能將n堆歸并為1堆。自然地可以將每次歸并劃分為一個(gè)階段，成為多階段決策問(wèn)題，嘗試動(dòng)態(tài)規(guī)劃法。求解：（此處采用自底向上的分析，找規(guī)律較簡(jiǎn)潔）當(dāng)n=2時(shí)：僅一種歸并法即2合1。當(dāng)n=3時(shí)：有2種歸并方法，第一種歸并方法如圖，前1堆后2堆。13781528f(i,j)——從第i堆到第j堆的代價(jià)和。g(i,j)——從第i堆到第j堆的重量和。f(1,3)=15+28=43

（最優(yōu)結(jié)果）

=f(2,3)+g(1,3)序號(hào)1

233級(jí)2級(jí)1小代價(jià)子母樹(shù)最小代價(jià)子母樹(shù)13781528f(i,j)最小代價(jià)子母樹(shù)(續(xù)1)n=4n=3時(shí)：第二種歸并方法，前2堆后1堆。n=4時(shí)：有3大類歸并法。前1堆后3堆、前2堆后2堆、前3堆后1堆。因3堆有2種歸并法，所以一共5小類歸并法。前1堆第1種情況：78163115序號(hào)1

2341344f(1,4)=15+31+44=90=f(2,4)+g(1,4)w不變

=f(2,3)+g(2,4)+g(1,4)若f(2,4)越小，則f(1,4)就越小。13782028f(i,j)——從第i堆到第j堆的代價(jià)和。g(i,j)——從第i堆到第j堆的重量和。f(1,3)=20+28=48

=f(1,2)+g(1,3)序號(hào)1

233級(jí)2級(jí)1級(jí)4級(jí)3級(jí)2級(jí)1級(jí)最小代價(jià)子母樹(shù)(續(xù)1)n=4n=3時(shí)：第二種歸并方法，前2最小代價(jià)子母樹(shù)(續(xù)2)n=4n=4時(shí)：前1堆的第2種情況。781624311344序號(hào)1

234f(1,4)=24+31+44=99=f(2,4)+g(1,4)w不變

=f(3,4)+g(2,4)+g(1,4)若f(2,4)越小，則f(1,4)就越小。n=4時(shí)：前2堆情況。781624201344序號(hào)1

234f(1,4)=20+24+44=88=f(1,2)+f(3,4)+g(1,4)若f(1,2)+f(3,4)越小，f(1,4)就越小4級(jí)3級(jí)2級(jí)1級(jí)3級(jí)2級(jí)1級(jí)最小代價(jià)子母樹(shù)(續(xù)2)n=4n=4時(shí)：前1堆的第2種情況最小代價(jià)子母樹(shù)(續(xù)3)n=4n=4時(shí)：前3堆的第1種情況。781620281344n=4時(shí)：前3堆的第2種情況。序號(hào)1

234f(1,4)=20+28+44=92=f(1,3)+g(1,4)w不變

=f(1,2)+g(1,3)+g(1,4)若f(1,3)越小，則f(1,4)就越小。781615281344序號(hào)1

234f(1,4)=15+28+44=87最優(yōu)

=f(1,3)+g(1,4)w不變

=f(2,3)+g(1,3)+g(1,4)若f(1,3)越小，則f(1,4)就越小。4級(jí)3級(jí)2級(jí)1級(jí)4級(jí)3級(jí)2級(jí)1級(jí)最小代價(jià)子母樹(shù)(續(xù)3)n=4n=4時(shí)：前3堆的第1種情況最小代價(jià)子母樹(shù)(續(xù)4)n=4將n=4歸納為3大類情況：f(1,4)=min

{f(2,4),f(1,2)+f(3,4),f(1,3)}

+g(1,4)

前1堆前2堆前3堆將n=4計(jì)算式推廣，對(duì)于任意的n(n>1)，歸納出如下公式：f(1,n)=min{f(2,n),f(1,2)+f(3,n),f(1,3)+f(4,n),...,f(1,n-1)}

+

g(1,n)

前1堆前2堆前3堆......前n-1堆上式稱為動(dòng)態(tài)方程，即用方程給出的動(dòng)態(tài)規(guī)劃算法。很多動(dòng)態(tài)規(guī)劃算法不能用方程形式給出，只能是描述性的。最小代價(jià)子母樹(shù)(續(xù)4)n=4F(1,n)在(13,7,8,16,21,4,18)上的結(jié)果F(1,n)在(13,7,8,16,21,4,18)上的結(jié)果//w[1...n]:n堆沙子的質(zhì)量序列//g[1...n;1...n]:g[i,j]=//f[1…n:1…n]:f[I,j]表示第i層從第j個(gè)位置開(kāi)始i堆沙子的最小歸并代價(jià),并約定f[1,i]=0proceduremincpt(w)begin

計(jì)算g[i,j]=g[j,i]=f[i,j]←0(1≤i≤n,1≤j≤n);fori←2tondo//i表示層次,也是歸并沙子的堆數(shù),在上圖中,表示行號(hào)

forj←1ton-i+1do//表示列號(hào)

beginmin←f[i-1,j];

fork←i-1step-1untill1doifmin>f[k,j]+f[i-k,j+k]then//min{f(1,n-1),f(1,2)+f(3,n),f(1,3)+f(4,n)…min←f[k,j]+f[i-k,j+k];f[i,j]←g[j,i+j-1]+min;end;return(f[n,1]);endp;//w[1...n]:n堆沙子的質(zhì)量序列遞推求解中的交疊子問(wèn)題

遞推求解中的交疊子問(wèn)題（非最優(yōu)化問(wèn)題）實(shí)例：計(jì)算裴波那契數(shù)的遞歸版本。遞推式：n>1，F(xiàn)(n)=F(n-1)+F(n-2)F(0)=0,F(1)=1例如，F(xiàn)(5)

計(jì)算過(guò)程用遞歸樹(shù)表示：F(5)F(4)F(3)F(2)F(3)F(1)F(2)F(1)F(0)F(0)F(1)F(2)F(1)F(0)F(1)樹(shù)中可以看出，計(jì)算F(5)時(shí)要重復(fù)計(jì)算F(2)、F(3)顯然降低時(shí)間效率。此即交疊子問(wèn)題，F(xiàn)(5)分為兩個(gè)子問(wèn)題F(4)和F(3)，F(xiàn)(4)包含了F(3)。動(dòng)態(tài)規(guī)劃法：自底向上計(jì)算依次計(jì)算F(0),F(1),F(2),...,F(n)一次，各次計(jì)算結(jié)果存入數(shù)組，最后一個(gè)元素就是F(n)。用一個(gè)單循環(huán)即可簡(jiǎn)單實(shí)現(xiàn)。遞推求解中的交疊子問(wèn)題遞推求解中的交疊子問(wèn)題（非最優(yōu)化問(wèn)單起點(diǎn)最短路徑問(wèn)題

單起點(diǎn)最短路徑問(wèn)題（區(qū)別于完全最短路徑問(wèn)題）概念：給定一個(gè)連通圖（有向或者無(wú)向），求給定起始頂點(diǎn)到結(jié)束頂點(diǎn)的最短路徑，此即單起點(diǎn)（單源）最短路徑問(wèn)題。完全最短路徑問(wèn)題要求找到從每個(gè)頂點(diǎn)到其他所有頂點(diǎn)之間的最短路徑。分段：頂點(diǎn)集分為k個(gè)不相交子集Vd,1≤d≤k,k≥2,級(jí)內(nèi)頂點(diǎn)不相鄰。任一條邊(u,v)，u∈Vd，v∈Vd+m，m≥1。令|V1|=|Vk|=1。從源點(diǎn)到收點(diǎn)依次編號(hào)V1V2V3V4V512345678910分級(jí)k=1k=2k=3k=4k=5圖示求解過(guò)程：紅色數(shù)字為實(shí)例求解結(jié)果（最優(yōu)性原則）本例：帶權(quán)有向圖源點(diǎn)收點(diǎn)計(jì)算方向841210819171316單起點(diǎn)最短路徑問(wèn)題單起點(diǎn)最短路徑問(wèn)題（區(qū)別于完全最短路徑對(duì)于一個(gè)有k級(jí)的動(dòng)態(tài)規(guī)劃,需要列出從s到t的每一條路上的k-2次判定結(jié)果.其中第i級(jí)判定是利用最優(yōu)化原理確定Vi+1中的哪一個(gè)頂點(diǎn)在可能得到的最佳線路上.設(shè)D(i,j)是從頂點(diǎn)集Vi中的點(diǎn)j到t的一條最小耗費(fèi)路線,cost(i,j)是這條路線的耗費(fèi).由后向前推算,得:cost(i,j)=min{C(j,l)+cost(i+1,l)}C(j,l):表示頂點(diǎn)集Vi中的頂點(diǎn)j到頂點(diǎn)集Vi+1中的點(diǎn)l的耗費(fèi)cost(i+1,l):表示頂點(diǎn)集Vi+1中的點(diǎn)l到目標(biāo)點(diǎn)t的耗費(fèi)對(duì)于一個(gè)有k級(jí)的動(dòng)態(tài)規(guī)劃,需要列出從s到t的每一條路上的k-cost(3,5)=min(4+cost(4,8),8+cost(4,9))=min(4+8,8+4)=12//第三層中,頂點(diǎn)5到終點(diǎn)的耗費(fèi)cost(3,6)=min(9+cost(4,8),6+cost(4,9))=min(9+8,6+4)=10//取頂點(diǎn)9cost(3,7)=min(5+cost(4,8),4+cost(4,9))=min(5+8,4+4)=8cost(2,2)=min(10+cost(3,5),9+cost(3,6))=min(10+12,9+10)=19cost(2,3)=min(6+12,7+10,10+8)=17cost(2,4)=min(3+10,8+8)=13//取頂點(diǎn)6cost(1,1)=min(4+19,2+17,3+13)=16//取頂點(diǎn)4cost(3,5)=min(4+cost(4,8),8+co由cost(1,1)=3+cost(2,4)記下結(jié)點(diǎn)4由cost(2,4)=3+cost(3,6)記下結(jié)點(diǎn)6由cost(3,6)=6+cost(4,9)記下結(jié)點(diǎn)9即D(1,1)=4,D(2,4)=6,D(3,6)=9,D(4,9)=10所以得到線路:1,4,6,9,10由cost(1,1)=3+cost(2,4)記下結(jié)點(diǎn)4//最短路徑算法輸入:圖的頂點(diǎn)編號(hào)表,各頂點(diǎn)的鄰接表,邊的耗費(fèi)函數(shù)C(i,j)表.輸出:從s到t的一條最小耗費(fèi)路線及其耗費(fèi)cost(1,s),即cost(1)procdureFGRAPHbeginfori←1tondocost[i]←0;forj←n-1step-1to1do begin 設(shè)頂點(diǎn)r使(j,r)∈E,且C(j,r)+cost[r]最小;

//耗費(fèi)時(shí)間(n+E)

cost[j]←C(j,r)+cost[r]; D[j]←r;//記下最短路徑經(jīng)歷的頂點(diǎn)

End;p[1]←1;

//找最小耗費(fèi)路線p[k]←n;forj←2tok-1do p[j]←D[p[j-1]];endp;//最短路徑算法最優(yōu)二叉查找樹(shù)

最優(yōu)二叉查找樹(shù)（最優(yōu)BST）前面我們已經(jīng)講過(guò)BST的相關(guān)算法及特性，本節(jié)介紹什么是最優(yōu)BST，以及用動(dòng)態(tài)規(guī)劃算法來(lái)構(gòu)造BST。最優(yōu)BST概念問(wèn)題的提出：基于統(tǒng)計(jì)先驗(yàn)知識(shí)，我們可統(tǒng)計(jì)出一個(gè)數(shù)表（集合）中各元素的查找概率，理解為集合各元素的出現(xiàn)頻率。比如中文輸入法字庫(kù)中各詞條（單字、詞組等）的先驗(yàn)概率，針對(duì)用戶習(xí)慣可以自動(dòng)調(diào)整詞頻——所謂動(dòng)態(tài)調(diào)頻、高頻先現(xiàn)原則，以減少用戶翻查次數(shù)。這就是最優(yōu)二叉查找樹(shù)問(wèn)題：查找過(guò)程中鍵值比較次數(shù)最少，或者說(shuō)希望用最少的鍵值比較次數(shù)找到每個(gè)關(guān)鍵碼（鍵值）。為解決這樣的問(wèn)題，顯然需要對(duì)集合的每個(gè)元素賦予一個(gè)特殊屬性——查找概率。最優(yōu)BST：最優(yōu)BST整棵樹(shù)的平均鍵值比較次數(shù)最小。BST好處是查找效率高，平均查找效率屬于logn型，最壞為線性（完全不平衡）。最優(yōu)二叉查找樹(shù)最優(yōu)二叉查找樹(shù)（最優(yōu)BST）舉例說(shuō)明：解最優(yōu)BST問(wèn)題的蠻力策略（窮舉法）

舉例說(shuō)明：解最優(yōu)BST問(wèn)題的蠻力策略（窮舉法）已知：4個(gè)鍵{a1,a2,a3,a4}，出現(xiàn)概率依次為{0.1,0.2,0.4,0.3}要求：構(gòu)造包含這4個(gè)鍵的最優(yōu)BST。策略：窮舉生成包含4個(gè)鍵的全部BST，共14種。然后計(jì)算每個(gè)BST的

平均鍵值比較次數(shù)，從中選擇比較次數(shù)最小的作為最優(yōu)BST。包含n個(gè)鍵的BST總數(shù)等于第n個(gè)卡塔蘭數(shù)：BST的平均鍵值比較次數(shù)的計(jì)算：（統(tǒng)計(jì)平均）它以4n/n1.5速度→(+∞)包含4個(gè)鍵的兩種BST（非最優(yōu)）a1a2a3a40.10.20.40.3比較1次比較2次比較3次比較4次a1a2a3a40.10.20.40.3比較1次比較2次比較3次左樹(shù)：0.1×1+0.2×2+0.4×3+0.3×4=2.9右樹(shù)：0.2×1+0.1×2+0.4×2+0.3×3=2.1結(jié)論：一定存在鍵值平均比較次數(shù)最少的最優(yōu)BST。舉例說(shuō)明：解最優(yōu)BST問(wèn)題的蠻力策略（窮舉法）舉例說(shuō)明：解

動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法原理

動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法原理問(wèn)題：n個(gè)鍵，查找概率，構(gòu)成最優(yōu)BST，表示為，求這棵樹(shù)的平均查找次數(shù)C[1,n]

（耗費(fèi)最低）。換言之，如何構(gòu)造這棵最優(yōu)BST，使得C[1,n]最小。分段求解：（自頂向下分析：規(guī)模減?。?/p>

動(dòng)態(tài)規(guī)劃法策略是將問(wèn)題分成多個(gè)階段，逐段推進(jìn)計(jì)算，后繼實(shí)例解由其直接前趨實(shí)例解計(jì)算得到。對(duì)于最優(yōu)BST問(wèn)題，利用減一技術(shù)和最優(yōu)性原則，如果前n-1

個(gè)節(jié)點(diǎn)構(gòu)成最優(yōu)BST，加入一個(gè)節(jié)點(diǎn)an

后要求構(gòu)成規(guī)模n

的最優(yōu)BST。按n-1,n-2,...,2,1遞歸，問(wèn)題可解。自底向上計(jì)算：C[1,2]→C[1,3]→...→C[1,n]。為不失一般性用C[i,j]表示由構(gòu)成的BST的耗費(fèi)。其中

1≤i≤j≤n。這棵樹(shù)表示為。從中選擇一個(gè)鍵作根節(jié)點(diǎn)，它的左子樹(shù)為，右子樹(shù)為。要求選擇的k使得整棵樹(shù)的平均查找次數(shù)C[i,j]最小。左右子樹(shù)遞歸執(zhí)行此過(guò)程。（根的生成過(guò)程）動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法原理動(dòng)態(tài)規(guī)劃法生成最優(yōu)B動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法原理（續(xù)）akpk最優(yōu)BST最優(yōu)BST根層：L(ak)=1k-1=i：左子樹(shù)縮為單節(jié)點(diǎn)。k+1=j：右子樹(shù)縮為單節(jié)點(diǎn)。k<i：左子樹(shù)為空樹(shù)。k>j：右子樹(shù)為空樹(shù)。1≤i≤j≤n自頂向下分析遞推計(jì)算式動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法原理（續(xù)）akpk最優(yōu)最優(yōu)根層：舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程

舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程例：4個(gè)鍵{a1,a2,a3,a4}，出現(xiàn)概率依次為{0.1,0.2,0.4,0.3}，求：構(gòu)造包含這4個(gè)鍵的最優(yōu)BST。（n=4）解：計(jì)算公式如下：自底向上計(jì)算：C[1,2]→C[1,3]→...→C[1,n]（本例n=4）k是選擇的根節(jié)點(diǎn)下標(biāo)。上面C[2,3]=0.8

是下頁(yè)的計(jì)算結(jié)果。12兩個(gè)鍵123三個(gè)鍵舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)1）

舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)1）計(jì)算公式：23兩個(gè)鍵最終結(jié)果：1234四個(gè)鍵34兩個(gè)鍵舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)1）舉例說(shuō)明：動(dòng)舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)2）

舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)2）計(jì)算公式：最終結(jié)果：1234四個(gè)鍵234三個(gè)鍵將各階段計(jì)算結(jié)果用

主表C

和

根表R

描述如下：舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)2）舉例說(shuō)明：動(dòng)動(dòng)態(tài)規(guī)劃算法：主表C和根表K各階段計(jì)算結(jié)果用

主表C

和

根表R

描述：計(jì)算過(guò)程中有j=0情況，所以j從0開(kāi)始編號(hào)。已知4個(gè)鍵{a1,a2,a3,a4}，出現(xiàn)概率依次為{0.1,0.2,0.4,0.3}。j=01234i=100.10.41.11.7200.20.81.4300.41.0400.350主表C[i,j]各階段計(jì)算結(jié)果，例如C[2,4]=1.4

：圖中箭頭表示求和的一對(duì)元素，將最小和與當(dāng)前節(jié)點(diǎn)概率和(p2+p3+p4)相加C[2,4]=0.5+(0.2+0.4+0.3)=1.4。如此計(jì)算C[i,j],1≤i＜j≤n=4。實(shí)際計(jì)算過(guò)程的i、j范圍i:1～n-1，j:2～n，圖中紅色數(shù)字。j=01234i=112332233333445根表R[i,j]動(dòng)態(tài)規(guī)劃算法：主表C和根表K各階段計(jì)算結(jié)果用主表C和根動(dòng)態(tài)規(guī)劃法算例的計(jì)算結(jié)果圖本例計(jì)算結(jié)果：akpk最優(yōu)BST最優(yōu)BSTa10.1a30.4a40.30.2a2j=01234i=112332233333445根表R[i,j]根表可知，4個(gè)鍵的最優(yōu)根下標(biāo)為3即a3鍵。它的左子樹(shù)為a1a2鍵，右子樹(shù)為a4鍵。左子樹(shù)是什么結(jié)構(gòu)呢？再看根表，a1a2構(gòu)成的最優(yōu)子樹(shù)根是a2。因?yàn)閍1<a2，所以1鍵是2鍵的左節(jié)點(diǎn)。最終結(jié)果圖動(dòng)態(tài)規(guī)劃法算例的計(jì)算結(jié)果圖本例計(jì)算結(jié)果：akpk最優(yōu)最優(yōu)a1動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法

動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法procedureSUBTREE-ROOT//w權(quán)值矩陣,C代價(jià)矩陣,r最優(yōu)樹(shù)根列表beginfori←1tondo begin w[i,i]←q[i];C[i,i]←0; end;forl←1tondofori←0ton-1do begin j←i+1;w[i,j]←w[i,j-1]+p[j]+q[j];

令m是使得C[i,k-1]+C[k,j]最小的k值(i<k<=j);C[i,j]←w[i,j]+C[i,m-1]+C[m,j]; r[i,j]←a[m]; end;endp;動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法pprocedureBUILDTREE(i,j)begincreattherootofT[i,j],thatis,nodev[i,j]Markv[i,j]byr[i][j];Letmbethesubscriptofr[i,j]ifi<m-1thenBUILDTREE(i,m-1);//Buildtheleftsubtreeofv[i,j];ifm<jthenBUILDTREE(m,j);//Buildtherightsubtreeofv[i,j]endp;procedureBUILDTREE(i,j)動(dòng)態(tài)規(guī)劃法解01背包

動(dòng)態(tài)規(guī)劃法解01背包問(wèn)題描述已知：n個(gè)重量w1,...,wn、價(jià)值v1,...,vn的物品和一個(gè)承重量W的背包。要求：找出最有價(jià)值子集，且能裝入背包中（不超重）。假定：物品重量、背包承重量、物品數(shù)量（01背包）都是整數(shù)。01背包的最優(yōu)化描述：（xi=0：i

物品不裝入，xi=1：i

物品裝入）求滿足約束方程的是目標(biāo)函數(shù)達(dá)到最大的解向量X=(x1,...,xn)。窮舉n個(gè)物品全部組合（冪集，子集數(shù)=2n），從中找出最有價(jià)值子集。貪婪法不一定能找到最優(yōu)解。物品數(shù)承重量動(dòng)態(tài)規(guī)劃法解01背包動(dòng)態(tài)規(guī)劃法解01背包物品數(shù)承重量動(dòng)態(tài)規(guī)劃法求解01背包

動(dòng)態(tài)規(guī)劃法求解01背包分段：動(dòng)態(tài)規(guī)劃法策略是將問(wèn)題分成多個(gè)階段，逐段推進(jìn)計(jì)算，后繼實(shí)例解由直接前趨子實(shí)例解計(jì)算得到。對(duì)于01背包問(wèn)題，可利用減一技術(shù)和最優(yōu)性原則，按物品數(shù)量和背包承重量分段。

V(i,j)——前i個(gè)物品中能夠裝入承重量j的背包中的最大總價(jià)值。前i個(gè)物品中最優(yōu)子集的總價(jià)值（動(dòng)態(tài)規(guī)劃函數(shù)）：

V(0,j)=0（0個(gè)物品），V(i,0)=0（承重量0）

V(i,j)=V(i-1,j)

第i個(gè)物品不能裝入，j<wi（超重）

V(i,j)=max

{

vi+V(i-1,j-wi),V(i-1,j)

}

j>wi（不超重）

i在最優(yōu)子集中

i不在最優(yōu)子集中自底向上計(jì)算：V(i,j)→V(n,W)（i：0→n,j：0→W）目標(biāo)

V(n,W)

第1階段：裝入1個(gè)物品，計(jì)算各種承重量下的最優(yōu)價(jià)值子集；第2階段：裝入2個(gè)物品，計(jì)算各種承重量下的最優(yōu)價(jià)值子集；第n階段：裝入n個(gè)物品，計(jì)算各種承重量下的最優(yōu)價(jià)值子集。動(dòng)態(tài)規(guī)劃法求解01背包動(dòng)態(tài)規(guī)劃法求解01背包動(dòng)態(tài)規(guī)劃法解01背包問(wèn)題的算法表

動(dòng)態(tài)規(guī)劃法解01背包問(wèn)題的算法表：前i個(gè)物品中最優(yōu)子集的總價(jià)值（動(dòng)態(tài)規(guī)劃函數(shù)）：

V(0,j)=0（0個(gè)物品），V(i,0)=0（承重量0）

V(i,j)=V(i-1,j)

第i個(gè)物品不能裝入，j<wi（超重）

V(i,j)=max

{

vi+V(i-1,j-wi),V(i-1,j)

}

j>wi（不超重）

i在最優(yōu)子集中

i不在最優(yōu)子集中Vj=0......j-wi......j......j=Wi=00...0...0...0......i-10V(i-1,j-wi)V(i-1,j)i0V(i,j)......i=n0V(n,W)說(shuō)明：可按行（或列）填寫此表。目標(biāo)動(dòng)態(tài)規(guī)劃法解01背包問(wèn)題的算法表動(dòng)態(tài)規(guī)劃法解01背包問(wèn)題的動(dòng)態(tài)規(guī)劃法解01背包問(wèn)題算例

動(dòng)態(tài)規(guī)劃法解01背包問(wèn)題算例例：01背包數(shù)據(jù)如下表，求：能夠放入背包的最有價(jià)值的物品集合。物品i重量wi價(jià)值vi承重量W1w1=2v1=12W=52w2=1v2=103w3=3v3=204w4=2v4=15Vj=012345i=000000010012121212201012222222301012223032401015253037自底向上：按行或列填表。遞推公式：例如：接下來(lái)，找出最優(yōu)解的物品集合。動(dòng)態(tài)規(guī)劃法解01背包問(wèn)題算例動(dòng)態(tài)規(guī)劃法解01背包問(wèn)題算例物動(dòng)態(tài)規(guī)劃法解01背包問(wèn)題算例（續(xù)）通過(guò)最優(yōu)解的回溯，找出最優(yōu)子集為{w1,w2,w4}最優(yōu)解有w4最優(yōu)解無(wú)w3最優(yōu)解有w2最優(yōu)解有w1最優(yōu)解回溯2動(dòng)態(tài)規(guī)劃法解01背包問(wèn)題算例（續(xù)）通過(guò)最優(yōu)解的回溯，找出最優(yōu)第5章動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃概述數(shù)塔最小代價(jià)子母樹(shù)非優(yōu)化問(wèn)題實(shí)例單起點(diǎn)最短路徑問(wèn)題最優(yōu)二叉查找樹(shù)

01背包問(wèn)題第5章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃概述動(dòng)態(tài)規(guī)劃概述

動(dòng)態(tài)規(guī)劃概述動(dòng)態(tài)規(guī)劃（DynamicProgramming），在20世紀(jì)50年代由美國(guó)數(shù)學(xué)家RichardBellman（理查德.貝爾曼）發(fā)明，作為多階段決策過(guò)程最優(yōu)化的一種通用方法，對(duì)最優(yōu)化問(wèn)題提出最優(yōu)性原則，從而創(chuàng)建最優(yōu)化問(wèn)題的一種新算法設(shè)計(jì)技術(shù)——?jiǎng)討B(tài)規(guī)劃，它是一種重要的應(yīng)用數(shù)學(xué)工具。至少在計(jì)算機(jī)科學(xué)圈子里，人們不僅用它解決特定類型的最優(yōu)化問(wèn)題，而最終把它作為一種通用的算法設(shè)計(jì)技術(shù)，即包括某些非最優(yōu)化問(wèn)題。多階段決策過(guò)程最優(yōu)化：現(xiàn)實(shí)世界里有許多問(wèn)題屬于這種情況：它有很多解，應(yīng)用要求最優(yōu)解。窮舉法通過(guò)找出全部解，再?gòu)闹羞x出最優(yōu)解。這種方法對(duì)于那些計(jì)算復(fù)雜度很高、計(jì)算量很大的問(wèn)題（如求最佳子集的組合問(wèn)題），要找出一切可能解，所耗費(fèi)的計(jì)算時(shí)間可能是不可以接受的。因此，人們?yōu)榱私档颓蠼鈫?wèn)題的難度，把求解過(guò)程分為一系列階段，各個(gè)階段依次按照最優(yōu)性原則計(jì)算，最后階段計(jì)算得到最優(yōu)解。包括分段、求解兩大步。注：不能段化的問(wèn)題不能用動(dòng)態(tài)規(guī)劃法求解。動(dòng)態(tài)規(guī)劃概述動(dòng)態(tài)規(guī)劃概述最優(yōu)性原則階段1階段2......階段n求解算法求解算法求解算法多階段決策過(guò)程圖示動(dòng)態(tài)的含義：求解算法施加的狀態(tài)是變化的。當(dāng)前狀態(tài)只與其直接前趨狀態(tài)有關(guān)，對(duì)其直接前趨狀態(tài)施加求解算法，成為當(dāng)前狀態(tài)。最優(yōu)性原則(PrincipleofOptimality)：一個(gè)最優(yōu)問(wèn)題任何實(shí)例的最優(yōu)解，是由該實(shí)例的子實(shí)例的最優(yōu)解組成的。對(duì)特定問(wèn)題該原則不一定滿足（罕見(jiàn)），有必要檢查其適用性。子實(shí)例組成父實(shí)例，父實(shí)例分解為子實(shí)例。對(duì)于某些多階段決策問(wèn)題，問(wèn)題本身沒(méi)有最優(yōu)化要求，比如后面要講到的求中國(guó)象棋馬從棋盤上一點(diǎn)移動(dòng)到另一點(diǎn)的全部路徑問(wèn)題，又如計(jì)算裴波那契序列的動(dòng)態(tài)規(guī)劃算法，它們屬于非最優(yōu)化問(wèn)題的動(dòng)態(tài)規(guī)劃法。動(dòng)態(tài)規(guī)劃法的特點(diǎn)：1.分階段（級(jí)）決策。對(duì)最優(yōu)化問(wèn)題，用最優(yōu)性原則設(shè)計(jì)。2.一般采用自頂向下分析（規(guī)模減小），自底向上計(jì)算（規(guī)模增加）。計(jì)算過(guò)程是一級(jí)一級(jí)（一階段一階段）地向前推進(jìn)，直到最終狀態(tài)。最優(yōu)性原則階段1階段2......階段n求解算法求解算數(shù)塔

數(shù)塔問(wèn)題：設(shè)有一三角形數(shù)塔如圖。求一條自塔頂?shù)剿椎穆窂?，該路徑?/p>

節(jié)點(diǎn)值之和最大。分段：每一級(jí)臺(tái)階自然劃分為一個(gè)階段，成為多階段決策的優(yōu)化問(wèn)題。無(wú)法分段的問(wèn)題，不能用動(dòng)態(tài)規(guī)劃法求解。求解：動(dòng)態(tài)規(guī)劃法求解。自底向上計(jì)算，各實(shí)例計(jì)算滿足最優(yōu)性原則，如實(shí)例18的子實(shí)例為12和7，max(12+6,7+6)=18。5級(jí)4級(jí)3級(jí)2級(jí)1級(jí)182739326746657873911311874014261582467131211數(shù)塔數(shù)塔分段：每一級(jí)臺(tái)階自然劃分為一個(gè)階段，成為多階段決策數(shù)塔問(wèn)題：動(dòng)態(tài)規(guī)劃法與窮舉法效率比較

數(shù)塔：動(dòng)態(tài)規(guī)劃法與窮舉法的時(shí)間效率比較輸入規(guī)模：為便于分析，選擇數(shù)塔層數(shù)k(k>0)；基本操作：節(jié)點(diǎn)值求和運(yùn)算；增長(zhǎng)函數(shù)：加法次數(shù)與k的關(guān)系；效率類別：沒(méi)有最佳、最差情況；（都要從塔頂計(jì)算到塔底）增長(zhǎng)率（次數(shù)）：各層節(jié)點(diǎn)數(shù)升序：1,2,3,4,5,6,7,8,9,10,...

節(jié)點(diǎn)總數(shù)

n

升序：1,3,6,10,15,21,28,36,45,55,...

層數(shù)k（頂為1）：1,2,3,4,5,6,7,8,9,10,...

路徑總數(shù)t升序：

2,

4,8,16,32,...,t=2k-1,k>11.窮舉法：T(k)=(k-1)2k-1，k>1（指數(shù)級(jí)）本例k=5，每條路徑上5個(gè)節(jié)點(diǎn)做4次加法，共64次加法。2.動(dòng)態(tài)規(guī)劃法：（層節(jié)點(diǎn)數(shù)=層數(shù)）自底向上計(jì)算，k層加法總數(shù)為k-1層節(jié)點(diǎn)數(shù)×2，有效率計(jì)算式：

T(k)=2×(k-1+...+3+2+1)=k(k-1),k>1（平方級(jí)）本例加法總數(shù)2×(4+3+2+1)=20次，比64次少很多。數(shù)塔問(wèn)題：動(dòng)態(tài)規(guī)劃法與窮舉法效率比較數(shù)塔：動(dòng)態(tài)規(guī)劃法與窮舉非最優(yōu)化問(wèn)題實(shí)例

非最優(yōu)化問(wèn)題實(shí)例求中國(guó)象棋馬的路徑

問(wèn)題：在m×n棋盤上，求馬從P點(diǎn)跳到Q點(diǎn)的所有路徑。654321654321654321可用回溯法和遞歸法求解，但遞歸法效率很低，?？臻g占用很大。非最優(yōu)化問(wèn)題實(shí)例非最優(yōu)化問(wèn)題實(shí)例654最小代價(jià)子母樹(shù)

最小代價(jià)子母樹(shù)

問(wèn)題：n(n>1)堆沙子，重量向量W=(w1,...wn)。要將它們歸并為1堆，歸并規(guī)則：每次只能將相鄰2堆歸并為1堆，經(jīng)過(guò)n-1次歸并后，最終歸并為一堆?？偞鷥r(jià)為歸并過(guò)程中新產(chǎn)生的沙堆質(zhì)量之和，這個(gè)代價(jià)最小的歸并樹(shù)稱為最小代價(jià)子母樹(shù)。分析：屬于最優(yōu)化問(wèn)題，目標(biāo)為總代價(jià)最小。分段：顯然需要n-1次歸并才能將n堆歸并為1堆。自然地可以將每次歸并劃分為一個(gè)階段，成為多階段決策問(wèn)題，嘗試動(dòng)態(tài)規(guī)劃法。求解：（此處采用自底向上的分析，找規(guī)律較簡(jiǎn)潔）當(dāng)n=2時(shí)：僅一種歸并法即2合1。當(dāng)n=3時(shí)：有2種歸并方法，第一種歸并方法如圖，前1堆后2堆。13781528f(i,j)——從第i堆到第j堆的代價(jià)和。g(i,j)——從第i堆到第j堆的重量和。f(1,3)=15+28=43

（最優(yōu)結(jié)果）

=f(2,3)+g(1,3)序號(hào)1

233級(jí)2級(jí)1小代價(jià)子母樹(shù)最小代價(jià)子母樹(shù)13781528f(i,j)最小代價(jià)子母樹(shù)(續(xù)1)n=4n=3時(shí)：第二種歸并方法，前2堆后1堆。n=4時(shí)：有3大類歸并法。前1堆后3堆、前2堆后2堆、前3堆后1堆。因3堆有2種歸并法，所以一共5小類歸并法。前1堆第1種情況：78163115序號(hào)1

2341344f(1,4)=15+31+44=90=f(2,4)+g(1,4)w不變

=f(2,3)+g(2,4)+g(1,4)若f(2,4)越小，則f(1,4)就越小。13782028f(i,j)——從第i堆到第j堆的代價(jià)和。g(i,j)——從第i堆到第j堆的重量和。f(1,3)=20+28=48

=f(1,2)+g(1,3)序號(hào)1

233級(jí)2級(jí)1級(jí)4級(jí)3級(jí)2級(jí)1級(jí)最小代價(jià)子母樹(shù)(續(xù)1)n=4n=3時(shí)：第二種歸并方法，前2最小代價(jià)子母樹(shù)(續(xù)2)n=4n=4時(shí)：前1堆的第2種情況。781624311344序號(hào)1

234f(1,4)=24+31+44=99=f(2,4)+g(1,4)w不變

=f(3,4)+g(2,4)+g(1,4)若f(2,4)越小，則f(1,4)就越小。n=4時(shí)：前2堆情況。781624201344序號(hào)1

234f(1,4)=20+24+44=88=f(1,2)+f(3,4)+g(1,4)若f(1,2)+f(3,4)越小，f(1,4)就越小4級(jí)3級(jí)2級(jí)1級(jí)3級(jí)2級(jí)1級(jí)最小代價(jià)子母樹(shù)(續(xù)2)n=4n=4時(shí)：前1堆的第2種情況最小代價(jià)子母樹(shù)(續(xù)3)n=4n=4時(shí)：前3堆的第1種情況。781620281344n=4時(shí)：前3堆的第2種情況。序號(hào)1

234f(1,4)=20+28+44=92=f(1,3)+g(1,4)w不變

=f(1,2)+g(1,3)+g(1,4)若f(1,3)越小，則f(1,4)就越小。781615281344序號(hào)1

234f(1,4)=15+28+44=87最優(yōu)

=f(1,3)+g(1,4)w不變

=f(2,3)+g(1,3)+g(1,4)若f(1,3)越小，則f(1,4)就越小。4級(jí)3級(jí)2級(jí)1級(jí)4級(jí)3級(jí)2級(jí)1級(jí)最小代價(jià)子母樹(shù)(續(xù)3)n=4n=4時(shí)：前3堆的第1種情況最小代價(jià)子母樹(shù)(續(xù)4)n=4將n=4歸納為3大類情況：f(1,4)=min

{f(2,4),f(1,2)+f(3,4),f(1,3)}

+g(1,4)

前1堆前2堆前3堆將n=4計(jì)算式推廣，對(duì)于任意的n(n>1)，歸納出如下公式：f(1,n)=min{f(2,n),f(1,2)+f(3,n),f(1,3)+f(4,n),...,f(1,n-1)}

+

g(1,n)

前1堆前2堆前3堆......前n-1堆上式稱為動(dòng)態(tài)方程，即用方程給出的動(dòng)態(tài)規(guī)劃算法。很多動(dòng)態(tài)規(guī)劃算法不能用方程形式給出，只能是描述性的。最小代價(jià)子母樹(shù)(續(xù)4)n=4F(1,n)在(13,7,8,16,21,4,18)上的結(jié)果F(1,n)在(13,7,8,16,21,4,18)上的結(jié)果//w[1...n]:n堆沙子的質(zhì)量序列//g[1...n;1...n]:g[i,j]=//f[1…n:1…n]:f[I,j]表示第i層從第j個(gè)位置開(kāi)始i堆沙子的最小歸并代價(jià),并約定f[1,i]=0proceduremincpt(w)begin

計(jì)算g[i,j]=g[j,i]=f[i,j]←0(1≤i≤n,1≤j≤n);fori←2tondo//i表示層次,也是歸并沙子的堆數(shù),在上圖中,表示行號(hào)

forj←1ton-i+1do//表示列號(hào)

beginmin←f[i-1,j];

fork←i-1step-1untill1doifmin>f[k,j]+f[i-k,j+k]then//min{f(1,n-1),f(1,2)+f(3,n),f(1,3)+f(4,n)…min←f[k,j]+f[i-k,j+k];f[i,j]←g[j,i+j-1]+min;end;return(f[n,1]);endp;//w[1...n]:n堆沙子的質(zhì)量序列遞推求解中的交疊子問(wèn)題

遞推求解中的交疊子問(wèn)題（非最優(yōu)化問(wèn)題）實(shí)例：計(jì)算裴波那契數(shù)的遞歸版本。遞推式：n>1，F(xiàn)(n)=F(n-1)+F(n-2)F(0)=0,F(1)=1例如，F(xiàn)(5)

計(jì)算過(guò)程用遞歸樹(shù)表示：F(5)F(4)F(3)F(2)F(3)F(1)F(2)F(1)F(0)F(0)F(1)F(2)F(1)F(0)F(1)樹(shù)中可以看出，計(jì)算F(5)時(shí)要重復(fù)計(jì)算F(2)、F(3)顯然降低時(shí)間效率。此即交疊子問(wèn)題，F(xiàn)(5)分為兩個(gè)子問(wèn)題F(4)和F(3)，F(xiàn)(4)包含了F(3)。動(dòng)態(tài)規(guī)劃法：自底向上計(jì)算依次計(jì)算F(0),F(1),F(2),...,F(n)一次，各次計(jì)算結(jié)果存入數(shù)組，最后一個(gè)元素就是F(n)。用一個(gè)單循環(huán)即可簡(jiǎn)單實(shí)現(xiàn)。遞推求解中的交疊子問(wèn)題遞推求解中的交疊子問(wèn)題（非最優(yōu)化問(wèn)單起點(diǎn)最短路徑問(wèn)題

單起點(diǎn)最短路徑問(wèn)題（區(qū)別于完全最短路徑問(wèn)題）概念：給定一個(gè)連通圖（有向或者無(wú)向），求給定起始頂點(diǎn)到結(jié)束頂點(diǎn)的最短路徑，此即單起點(diǎn)（單源）最短路徑問(wèn)題。完全最短路徑問(wèn)題要求找到從每個(gè)頂點(diǎn)到其他所有頂點(diǎn)之間的最短路徑。分段：頂點(diǎn)集分為k個(gè)不相交子集Vd,1≤d≤k,k≥2,級(jí)內(nèi)頂點(diǎn)不相鄰。任一條邊(u,v)，u∈Vd，v∈Vd+m，m≥1。令|V1|=|Vk|=1。從源點(diǎn)到收點(diǎn)依次編號(hào)V1V2V3V4V512345678910分級(jí)k=1k=2k=3k=4k=5圖示求解過(guò)程：紅色數(shù)字為實(shí)例求解結(jié)果（最優(yōu)性原則）本例：帶權(quán)有向圖源點(diǎn)收點(diǎn)計(jì)算方向841210819171316單起點(diǎn)最短路徑問(wèn)題單起點(diǎn)最短路徑問(wèn)題（區(qū)別于完全最短路徑對(duì)于一個(gè)有k級(jí)的動(dòng)態(tài)規(guī)劃,需要列出從s到t的每一條路上的k-2次判定結(jié)果.其中第i級(jí)判定是利用最優(yōu)化原理確定Vi+1中的哪一個(gè)頂點(diǎn)在可能得到的最佳線路上.設(shè)D(i,j)是從頂點(diǎn)集Vi中的點(diǎn)j到t的一條最小耗費(fèi)路線,cost(i,j)是這條路線的耗費(fèi).由后向前推算,得:cost(i,j)=min{C(j,l)+cost(i+1,l)}C(j,l):表示頂點(diǎn)集Vi中的頂點(diǎn)j到頂點(diǎn)集Vi+1中的點(diǎn)l的耗費(fèi)cost(i+1,l):表示頂點(diǎn)集Vi+1中的點(diǎn)l到目標(biāo)點(diǎn)t的耗費(fèi)對(duì)于一個(gè)有k級(jí)的動(dòng)態(tài)規(guī)劃,需要列出從s到t的每一條路上的k-cost(3,5)=min(4+cost(4,8),8+cost(4,9))=min(4+8,8+4)=12//第三層中,頂點(diǎn)5到終點(diǎn)的耗費(fèi)cost(3,6)=min(9+cost(4,8),6+cost(4,9))=min(9+8,6+4)=10//取頂點(diǎn)9cost(3,7)=min(5+cost(4,8),4+cost(4,9))=min(5+8,4+4)=8cost(2,2)=min(10+cost(3,5),9+cost(3,6))=min(10+12,9+10)=19cost(2,3)=min(6+12,7+10,10+8)=17cost(2,4)=min(3+10,8+8)=13//取頂點(diǎn)6cost(1,1)=min(4+19,2+17,3+13)=16//取頂點(diǎn)4cost(3,5)=min(4+cost(4,8),8+co由cost(1,1)=3+cost(2,4)記下結(jié)點(diǎn)4由cost(2,4)=3+cost(3,6)記下結(jié)點(diǎn)6由cost(3,6)=6+cost(4,9)記下結(jié)點(diǎn)9即D(1,1)=4,D(2,4)=6,D(3,6)=9,D(4,9)=10所以得到線路:1,4,6,9,10由cost(1,1)=3+cost(2,4)記下結(jié)點(diǎn)4//最短路徑算法輸入:圖的頂點(diǎn)編號(hào)表,各頂點(diǎn)的鄰接表,邊的耗費(fèi)函數(shù)C(i,j)表.輸出:從s到t的一條最小耗費(fèi)路線及其耗費(fèi)cost(1,s),即cost(1)procdureFGRAPHbeginfori←1tondocost[i]←0;forj←n-1step-1to1do begin 設(shè)頂點(diǎn)r使(j,r)∈E,且C(j,r)+cost[r]最小;

//耗費(fèi)時(shí)間(n+E)

cost[j]←C(j,r)+cost[r]; D[j]←r;//記下最短路徑經(jīng)歷的頂點(diǎn)

End;p[1]←1;

//找最小耗費(fèi)路線p[k]←n;forj←2tok-1do p[j]←D[p[j-1]];endp;//最短路徑算法最優(yōu)二叉查找樹(shù)

最優(yōu)二叉查找樹(shù)（最優(yōu)BST）前面我們已經(jīng)講過(guò)BST的相關(guān)算法及特性，本節(jié)介紹什么是最優(yōu)BST，以及用動(dòng)態(tài)規(guī)劃算法來(lái)構(gòu)造BST。最優(yōu)BST概念問(wèn)題的提出：基于統(tǒng)計(jì)先驗(yàn)知識(shí)，我們可統(tǒng)計(jì)出一個(gè)數(shù)表（集合）中各元素的查找概率，理解為集合各元素的出現(xiàn)頻率。比如中文輸入法字庫(kù)中各詞條（單字、詞組等）的先驗(yàn)概率，針對(duì)用戶習(xí)慣可以自動(dòng)調(diào)整詞頻——所謂動(dòng)態(tài)調(diào)頻、高頻先現(xiàn)原則，以減少用戶翻查次數(shù)。這就是最優(yōu)二叉查找樹(shù)問(wèn)題：查找過(guò)程中鍵值比較次數(shù)最少，或者說(shuō)希望用最少的鍵值比較次數(shù)找到每個(gè)關(guān)鍵碼（鍵值）。為解決這樣的問(wèn)題，顯然需要對(duì)集合的每個(gè)元素賦予一個(gè)特殊屬性——查找概率。最優(yōu)BST：最優(yōu)BST整棵樹(shù)的平均鍵值比較次數(shù)最小。BST好處是查找效率高，平均查找效率屬于logn型，最壞為線性（完全不平衡）。最優(yōu)二叉查找樹(shù)最優(yōu)二叉查找樹(shù)（最優(yōu)BST）舉例說(shuō)明：解最優(yōu)BST問(wèn)題的蠻力策略（窮舉法）

舉例說(shuō)明：解最優(yōu)BST問(wèn)題的蠻力策略（窮舉法）已知：4個(gè)鍵{a1,a2,a3,a4}，出現(xiàn)概率依次為{0.1,0.2,0.4,0.3}要求：構(gòu)造包含這4個(gè)鍵的最優(yōu)BST。策略：窮舉生成包含4個(gè)鍵的全部BST，共14種。然后計(jì)算每個(gè)BST的

平均鍵值比較次數(shù)，從中選擇比較次數(shù)最小的作為最優(yōu)BST。包含n個(gè)鍵的BST總數(shù)等于第n個(gè)卡塔蘭數(shù)：BST的平均鍵值比較次數(shù)的計(jì)算：（統(tǒng)計(jì)平均）它以4n/n1.5速度→(+∞)包含4個(gè)鍵的兩種BST（非最優(yōu)）a1a2a3a40.10.20.40.3比較1次比較2次比較3次比較4次a1a2a3a40.10.20.40.3比較1次比較2次比較3次左樹(shù)：0.1×1+0.2×2+0.4×3+0.3×4=2.9右樹(shù)：0.2×1+0.1×2+0.4×2+0.3×3=2.1結(jié)論：一定存在鍵值平均比較次數(shù)最少的最優(yōu)BST。舉例說(shuō)明：解最優(yōu)BST問(wèn)題的蠻力策略（窮舉法）舉例說(shuō)明：解

動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法原理

動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法原理問(wèn)題：n個(gè)鍵，查找概率，構(gòu)成最優(yōu)BST，表示為，求這棵樹(shù)的平均查找次數(shù)C[1,n]

（耗費(fèi)最低）。換言之，如何構(gòu)造這棵最優(yōu)BST，使得C[1,n]最小。分段求解：（自頂向下分析：規(guī)模減?。?/p>

動(dòng)態(tài)規(guī)劃法策略是將問(wèn)題分成多個(gè)階段，逐段推進(jìn)計(jì)算，后繼實(shí)例解由其直接前趨實(shí)例解計(jì)算得到。對(duì)于最優(yōu)BST問(wèn)題，利用減一技術(shù)和最優(yōu)性原則，如果前n-1

個(gè)節(jié)點(diǎn)構(gòu)成最優(yōu)BST，加入一個(gè)節(jié)點(diǎn)an

后要求構(gòu)成規(guī)模n

的最優(yōu)BST。按n-1,n-2,...,2,1遞歸，問(wèn)題可解。自底向上計(jì)算：C[1,2]→C[1,3]→...→C[1,n]。為不失一般性用C[i,j]表示由構(gòu)成的BST的耗費(fèi)。其中

1≤i≤j≤n。這棵樹(shù)表示為。從中選擇一個(gè)鍵作根節(jié)點(diǎn)，它的左子樹(shù)為，右子樹(shù)為。要求選擇的k使得整棵樹(shù)的平均查找次數(shù)C[i,j]最小。左右子樹(shù)遞歸執(zhí)行此過(guò)程。（根的生成過(guò)程）動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法原理動(dòng)態(tài)規(guī)劃法生成最優(yōu)B動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法原理（續(xù)）akpk最優(yōu)BST最優(yōu)BST根層：L(ak)=1k-1=i：左子樹(shù)縮為單節(jié)點(diǎn)。k+1=j：右子樹(shù)縮為單節(jié)點(diǎn)。k<i：左子樹(shù)為空樹(shù)。k>j：右子樹(shù)為空樹(shù)。1≤i≤j≤n自頂向下分析遞推計(jì)算式動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST算法原理（續(xù)）akpk最優(yōu)最優(yōu)根層：舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程

舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程例：4個(gè)鍵{a1,a2,a3,a4}，出現(xiàn)概率依次為{0.1,0.2,0.4,0.3}，求：構(gòu)造包含這4個(gè)鍵的最優(yōu)BST。（n=4）解：計(jì)算公式如下：自底向上計(jì)算：C[1,2]→C[1,3]→...→C[1,n]（本例n=4）k是選擇的根節(jié)點(diǎn)下標(biāo)。上面C[2,3]=0.8

是下頁(yè)的計(jì)算結(jié)果。12兩個(gè)鍵123三個(gè)鍵舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)1）

舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)1）計(jì)算公式：23兩個(gè)鍵最終結(jié)果：1234四個(gè)鍵34兩個(gè)鍵舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)1）舉例說(shuō)明：動(dòng)舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)2）

舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)2）計(jì)算公式：最終結(jié)果：1234四個(gè)鍵234三個(gè)鍵將各階段計(jì)算結(jié)果用

主表C

和

根表R

描述如下：舉例說(shuō)明：動(dòng)態(tài)規(guī)劃法生成最優(yōu)BST過(guò)程（續(xù)2）舉例說(shuō)明：動(dòng)動(dòng)態(tài)規(guī)劃算法：主表C和根表K各階段計(jì)算結(jié)果用

主表C

和

根表R

描述：計(jì)算過(guò)程中有j=0情況，所以j從0開(kāi)始編號(hào)。已知4個(gè)鍵{a1,a2,a3,a4}，出現(xiàn)概率依次為{0.1,0.2,0.4,0.3}。j=01234i=100.10.41.11.7200.20.81.4300.41.0400.350主表C[i,j]各階段計(jì)算結(jié)果，例如C[2,4]=1.4

：圖中箭頭表示求和的一對(duì)元素，將最小和與當(dāng)前節(jié)點(diǎn)概率和(p2+p3+p4)相加C[2,4]=0.5+(0.2+0.4+0.3)=1.4。如此計(jì)算C[i,j],1≤i＜j≤n=4。實(shí)際計(jì)算過(guò)程的i、j范圍i:1～n-1，j:2～n，圖中紅色數(shù)字。j=01234i=112332233333445根表R[i,j]動(dòng)態(tài)規(guī)劃算法：主表C和根表K各階段計(jì)算結(jié)果用主表C和根動(dòng)態(tài)規(guī)劃法算例的計(jì)算結(jié)果圖本例計(jì)算結(jié)果：akpk最優(yōu)BST最優(yōu)BSTa10.1a30.4a40.30.2a2j=01234i=112332233333445根表R[i,j]根表可知，4個(gè)鍵的最優(yōu)根下標(biāo)為3即a3鍵。它的左子樹(shù)為a1a2鍵，右子樹(shù)為a4鍵。左子樹(shù)是什么結(jié)構(gòu)呢？再看根表，a1a2構(gòu)成的最優(yōu)子樹(shù)根是a2。因?yàn)閍1<a2，所以1鍵是2鍵的左節(jié)點(diǎn)。最終結(jié)果圖動(dòng)態(tài)規(guī)劃法算例的計(jì)