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

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

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

01背包問題第5章動態(tài)規(guī)劃動態(tài)規(guī)劃概述動態(tài)規(guī)劃概述

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

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

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

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

節(jié)點總數(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ù)級）本例k=5，每條路徑上5個節(jié)點做4次加法，共64次加法。2.動態(tài)規(guī)劃法：（層節(jié)點數(shù)=層數(shù)）自底向上計算，k層加法總數(shù)為k-1層節(jié)點數(shù)×2，有效率計算式：

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

非最優(yōu)化問題實例求中國象棋馬的路徑

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

最小代價子母樹

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

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

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

233級2級1小代價子母樹最小代價子母樹13781528f(i,j)最小代價子母樹(續(xù)1)n=4n=3時：第二種歸并方法，前2堆后1堆。n=4時：有3大類歸并法。前1堆后3堆、前2堆后2堆、前3堆后1堆。因3堆有2種歸并法，所以一共5小類歸并法。前1堆第1種情況：78163115序號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堆的代價和。g(i,j)——從第i堆到第j堆的重量和。f(1,3)=20+28=48

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

233級2級1級4級3級2級1級最小代價子母樹(續(xù)1)n=4n=3時：第二種歸并方法，前2最小代價子母樹(續(xù)2)n=4n=4時：前1堆的第2種情況。781624311344序號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時：前2堆情況。781624201344序號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級3級2級1級3級2級1級最小代價子母樹(續(xù)2)n=4n=4時：前1堆的第2種情況最小代價子母樹(續(xù)3)n=4n=4時：前3堆的第1種情況。781620281344n=4時：前3堆的第2種情況。序號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序號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級3級2級1級4級3級2級1級最小代價子母樹(續(xù)3)n=4n=4時：前3堆的第1種情況最小代價子母樹(續(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計算式推廣，對于任意的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堆上式稱為動態(tài)方程，即用方程給出的動態(tài)規(guī)劃算法。很多動態(tài)規(guī)劃算法不能用方程形式給出，只能是描述性的。最小代價子母樹(續(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個位置開始i堆沙子的最小歸并代價,并約定f[1,i]=0proceduremincpt(w)begin

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

forj←1ton-i+1do//表示列號

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ì)量序列遞推求解中的交疊子問題

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

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

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

//耗費時間(n+E)

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

End;p[1]←1;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

主表C

和

根表R

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

主表C

和

根表R

描述：計算過程中有j=0情況，所以j從0開始編號。已知4個鍵{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]各階段計算結(jié)果，例如C[2,4]=1.4

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

動態(tài)規(guī)劃法生成最優(yōu)BST算法procedureSUBTREE-ROOT//w權(quán)值矩陣,C代價矩陣,r最優(yōu)樹根列表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;動態(tài)規(guī)劃法生成最優(yōu)BST算法動態(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)動態(tài)規(guī)劃法解01背包

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

物品不裝入，xi=1：i

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

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

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

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

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

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

V(i,j)=max

{

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

}

j>wi（不超重）

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

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

V(n,W)

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

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

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

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

第i個物品不能裝入，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)說明：可按行（或列）填寫此表。目標(biāo)動態(tài)規(guī)劃法解01背包問題的算法表動態(tài)規(guī)劃法解01背包問題的動態(tài)規(guī)劃法解01背包問題算例

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

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

01背包問題第5章動態(tài)規(guī)劃動態(tài)規(guī)劃概述動態(tài)規(guī)劃概述

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

數(shù)塔問題：設(shè)有一三角形數(shù)塔如圖。求一條自塔頂?shù)剿椎穆窂剑撀窂缴?/p>

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

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

節(jié)點總數(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ù)級）本例k=5，每條路徑上5個節(jié)點做4次加法，共64次加法。2.動態(tài)規(guī)劃法：（層節(jié)點數(shù)=層數(shù)）自底向上計算，k層加法總數(shù)為k-1層節(jié)點數(shù)×2，有效率計算式：

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

非最優(yōu)化問題實例求中國象棋馬的路徑

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

最小代價子母樹

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

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

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

233級2級1小代價子母樹最小代價子母樹13781528f(i,j)最小代價子母樹(續(xù)1)n=4n=3時：第二種歸并方法，前2堆后1堆。n=4時：有3大類歸并法。前1堆后3堆、前2堆后2堆、前3堆后1堆。因3堆有2種歸并法，所以一共5小類歸并法。前1堆第1種情況：78163115序號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堆的代價和。g(i,j)——從第i堆到第j堆的重量和。f(1,3)=20+28=48

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

233級2級1級4級3級2級1級最小代價子母樹(續(xù)1)n=4n=3時：第二種歸并方法，前2最小代價子母樹(續(xù)2)n=4n=4時：前1堆的第2種情況。781624311344序號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時：前2堆情況。781624201344序號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級3級2級1級3級2級1級最小代價子母樹(續(xù)2)n=4n=4時：前1堆的第2種情況最小代價子母樹(續(xù)3)n=4n=4時：前3堆的第1種情況。781620281344n=4時：前3堆的第2種情況。序號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序號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級3級2級1級4級3級2級1級最小代價子母樹(續(xù)3)n=4n=4時：前3堆的第1種情況最小代價子母樹(續(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計算式推廣，對于任意的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堆上式稱為動態(tài)方程，即用方程給出的動態(tài)規(guī)劃算法。很多動態(tài)規(guī)劃算法不能用方程形式給出，只能是描述性的。最小代價子母樹(續(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個位置開始i堆沙子的最小歸并代價,并約定f[1,i]=0proceduremincpt(w)begin

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

forj←1ton-i+1do//表示列號

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ì)量序列遞推求解中的交疊子問題

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

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

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

//耗費時間(n+E)

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

End;p[1]←1;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

主表C

和

根表R

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

主表C

和

根表R

描述：計算過程中有j=0情況，所以j從0開始編號。已知4個鍵{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]各階段計算結(jié)果，例如C[2,4]=1.4

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