算法設計與分析耿國華第三章

第三章動態(tài)規(guī)劃算法設計與分析主編耿國華本章內容Chapter3

3.1

動態(tài)規(guī)劃基礎3.1.1動態(tài)規(guī)劃的基本思想3.1.2動態(tài)規(guī)劃的基本要素3.1.3動態(tài)規(guī)劃的基本步驟3.1.4動態(tài)規(guī)劃示例——組合數(shù)問題3.2線性動態(tài)規(guī)劃——合唱隊形問題3.3區(qū)域動態(tài)規(guī)劃——矩陣連乘問題3.4背包動態(tài)規(guī)劃——0-1背包問題3.5樹形動態(tài)規(guī)劃——最優(yōu)二叉搜索樹問題3.6本章小結

引言

本章給出的動態(tài)規(guī)劃技術可使用較少的時間求解此類問題。與分治法不同，在求解過程中動態(tài)規(guī)劃方法采用自底向上的遞推方式，將原問題分解為互不獨立的小規(guī)模子問題，根據子問題的相關性從已知的各個局部解中選出能產生最佳解的部分，并將計算過程填表，只要某個子問題被解決，它將不會被重復求解，從而減少了算法的時間復雜度，適合動態(tài)規(guī)劃算法求解的問題，可以在多項式時間內被求解出來，常用于最優(yōu)（最大/最?。﹩栴}的求解過程.Chapter3本章將針對線性動態(tài)規(guī)劃、區(qū)域動態(tài)規(guī)劃、背包動態(tài)規(guī)劃、樹形動態(tài)規(guī)劃四類具體實例給出問題求解的技術方法。3.1動態(tài)規(guī)劃基礎

3.1.1動態(tài)規(guī)劃的基本思想3.1.2動態(tài)規(guī)劃的基本要素3.1.3動態(tài)規(guī)劃的基本步驟3.1.4動態(tài)規(guī)劃示例——組合數(shù)問題Chapter93.1.1動態(tài)規(guī)劃的基本思想

多階段最優(yōu)化決策解決問題的過程稱為動態(tài)規(guī)劃。動態(tài)規(guī)劃通常是用遞歸程序實現(xiàn)的，遞推關系是實現(xiàn)由分解后的子問題向最終問題求解轉化的紐帶。3.1.1動態(tài)規(guī)劃的基本思想指導思想：動態(tài)規(guī)劃是建立在最優(yōu)原則的基礎上，在每一決策步上列出各種可能局部解，按某些條件舍棄肯定不能得到最優(yōu)解的局部解，這是一個尋找最優(yōu)判斷序列的過程，即不論初始策略如何，下一次決策必須相對前一次決策產生的新狀態(tài)構成最優(yōu)序列。這樣，在每一步都經過篩選，以每一步的最優(yōu)性來保證全局的最優(yōu)性?；舅枷耄河涗涀訂栴}并不斷填表。即將待求解的問題分成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。適合動態(tài)規(guī)劃算法求解的問題，經分解后不是互相獨立的，即它們可以在多項式時間內被求解出來

Chapter33.1.1動態(tài)規(guī)劃的基本思想

多階段最優(yōu)化決策解決問題的過程稱為動態(tài)規(guī)劃。動態(tài)規(guī)劃通常是用遞歸程序實現(xiàn)的，遞推關系是實現(xiàn)由分解后的子問題向最終問題求解轉化的紐帶，3.1.1動態(tài)規(guī)劃的基本思想指導思想：動態(tài)規(guī)劃是建立在最優(yōu)原則的基礎上，在每一決策步上列出各種可能局部解，按某些條件舍棄肯定不能得到最優(yōu)解的局部解，這是一個尋找最優(yōu)判斷序列的過程，即不論初始策略如何，下一次決策必須相對前一次決策產生的新狀態(tài)構成最優(yōu)序列。這樣，在每一步都經過篩選，以每一步的最優(yōu)性來保證全局的最優(yōu)性。基本思想：記錄子問題并不斷填表。即將待求解的問題分成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。適合動態(tài)規(guī)劃算法求解的問題，經分解后不是互相獨立的，即它們可以在多項式時間內被求解出來

Chapter33.1.2動態(tài)規(guī)劃的基本要素3.1.2動態(tài)規(guī)劃的基本要素一個可用動態(tài)規(guī)劃算法求解的問題必須具備以下三要素：1、最優(yōu)子結構當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，就稱該問題具有最優(yōu)子結構。一般在分析問題的最優(yōu)子結構時，采用反證法。首先假設由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的，然后再設法證明在這個假設下可以構造出比原問題最優(yōu)解更好的解，從而導致矛盾。Chapter32、無后效性(馬爾可夫性)

一旦某階段狀態(tài)已經確定，它以前各階段的狀態(tài)無法直接影響它未來的決策，且當前的狀態(tài)只是對以往決策的總結。若將動態(tài)規(guī)劃問題進行抽象，用結點表示狀態(tài)，邊表示狀態(tài)之間的關系，這樣的圖必將是一個有向無環(huán)圖，即各狀態(tài)之間有著嚴格的遞推關系。3.1.2動態(tài)規(guī)劃的基本要素

3.1.2動態(tài)規(guī)劃的基本要素3、子問題重疊性

可用動態(tài)規(guī)劃算法求解的問題，應具備的最后一個基本性質是子問題的重疊性。在用遞歸算法自頂向下解此問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。動態(tài)規(guī)劃算法正是利用這種子問題的重疊性質，對每個子問題都只解一次，而后將其解保存在一個表格中，當再次需要解此問題時，只是簡單的查看一下結果，從而得到較高的解題效率。題的最優(yōu)解時，就稱該問題具有最優(yōu)子結構。

Chapter33.1.3動態(tài)規(guī)劃的基本步驟

3.1.3動態(tài)規(guī)劃的基本步驟在求解具體問題時，通常按照以下步驟求解動態(tài)規(guī)劃問題：(1)找出最優(yōu)解的性質，并刻畫其結構特征；(2)遞歸的定義最優(yōu)值；(3)自底向上的方式計算出最優(yōu)值；(4)根據計算最優(yōu)值時得到的信息，構造最優(yōu)解。如果該問題只需求出最優(yōu)值，則可省去步驟（4）；若要進一步求出問題的最優(yōu)解，則必須執(zhí)行步驟（4），此時需要記錄更多算法執(zhí)行過程中的中間數(shù)據，以便根據這些數(shù)據構造出最優(yōu)解。Chapter33.1.4動態(tài)規(guī)劃的例子

3.1.4動態(tài)規(guī)劃的例子

下面就以具體的例子來說明可用動態(tài)規(guī)劃算法求解的問題所應具備的基本特征，以及如何運用動態(tài)規(guī)劃算法來求解問題。例3-1：對斐波納契數(shù)列F(n)，用動態(tài)規(guī)劃算法求出它的第n項。問題求解步驟如下：步驟1：最優(yōu)子結構的性質用F(n)表示在斐波納契數(shù)列中第n個數(shù)的值，由于F(n)=F(n-1)+F(n-2),計算F(n-1),又要知道F(n-2)和F(n-3)的值，這樣整個問題的求解會導致很多重復的計算量，為避免重復，應該將計算過的值記錄下來，下次用到的時候直接讀出即可。即將原問題自底向上分解為若干個子問題，從斐波納契數(shù)列的第一項開始，依次遞推計算前n-1項的值并存儲在一個數(shù)組中，第n項的值即可用與其相鄰的前兩項的值相加得到，從而保證當每個子問題用最優(yōu)的方法求解，故原問題具有最優(yōu)子結構的性質。Chapter33.1.4動態(tài)規(guī)劃的例子3.1.4動態(tài)規(guī)劃的例子步驟2：建立遞歸方程步驟3：以自底向上的方法來計算最優(yōu)解表3-1斐波納契數(shù)列計算動態(tài)規(guī)劃表步驟4：在數(shù)組中分析構造出問題的解，具體算法如下所示：constintN=100;int

Fib(intn){intF[N]={1,1};

for(inti=2;i<=n;i++)

F[i]=F[i-1]+F[i-2];}Chapter3n01234567F(n)11235813213.1.4動態(tài)規(guī)劃的例子

3.1.4動態(tài)規(guī)劃的例子例3-2：分別用遞歸和動態(tài)規(guī)劃算法解。遞歸：重復求解子問題，如算法3.1所示?！舅惴?.1用遞歸求解組合問題】/*功能：求解。輸入：正整數(shù)n,m

輸出：輸出的結果*/

int

ComB(int

n,intm){if(m==0||n==m)

return(1);elsereturn(ComB(n-1,m-1))+return(ComB(n-1,m));}

Chapter33.1.4動態(tài)規(guī)劃的例子3.1.4動態(tài)規(guī)劃的例子例3-2：分別用遞歸和動態(tài)規(guī)劃算法解。(2)動態(tài)規(guī)劃：記錄子問題，如算法3.2所示。步驟1：分析最優(yōu)子結構計算組合數(shù)，可將原問題分解為求解兩個子問題，要采用自底向上的方法，先計算出(i=1…n)，然后用公式（i=1…n，初值）……，依次計算出其他各項值并填表，當子問題被求解，原問題得解。由于采用了填表技術，子問題被求解后就不用重復計算，達到子問題最優(yōu)求解方式，具有最優(yōu)子結構的性質。步驟2：建立遞歸關系根據公式可以用

C[i][j](i=1~n,j=1~m)來記錄，即用一張表來記錄重復子問題的結果。

Chapter3步驟2：建立遞歸關系3.1.4動態(tài)規(guī)劃的例子

3.1.4動態(tài)規(guī)劃的例子例3-2：分別用遞歸和動態(tài)規(guī)劃算法解。步驟3：計算最優(yōu)值如求解(n=5，m=3)，通過動態(tài)規(guī)劃算法來記錄（其中），結果如表3-1所示,如計算表中第四行第二列的值，可以用第三行第一列的與第三行第二列的求和得到，即=6表3-2組合數(shù)計算動態(tài)規(guī)劃表Chapter3步驟2：建立遞歸關系i=1i=2i=3j=1100j=2210j=3331j=4464j=5510103.1.4動態(tài)規(guī)劃的例子

3.1.4動態(tài)規(guī)劃的例子例3-2：分別用遞歸和動態(tài)規(guī)劃算法解。步驟4：算法描述及分析【算法3.2用動態(tài)規(guī)劃求解組合問題】/*功能：求解。輸入：正整數(shù)n,m

輸出：輸出的結果*/int

ComB(intn,intm){intC[n+1][m+1],i,j;/*為更加簡潔，本例數(shù)組下標從1開始*/for(j=1;j<=m;j++)C[1][j]=0;for(i=1;i<=n;i++)C[i][1]=i;for(i=2;i<=n;i++)for(j=2;j<=m;j++)

if(i<j)C[i][j]=0;elseC[i][j]=C[i-1][j-1]+C[i-1][j];

return(C[n][m]);}Chapter33.2線性動態(tài)規(guī)劃-----合唱隊形問題

Chapter3本節(jié)內容1.問題描述2.分析最優(yōu)子結構3.建立遞歸關系4.計算最優(yōu)值5.程序描述及算法分析3.2線性動態(tài)規(guī)劃-----合唱隊形問題

建立在線性結構或圖結構的基礎之上的線性動態(tài)規(guī)劃算法，可解決的問題具有線性遞推的特點，通常以某一結點為狀態(tài)，向兩個方向：即由前向后或者由后向前線性遍歷每個狀態(tài)，從中找出具有最優(yōu)值的狀態(tài)從而得到問題的解，下面我們就用合唱隊形問題來解決線性動態(tài)規(guī)劃問題。1.問題描述N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，而不改變其他同學的位置，使得剩下的K位同學排成合唱隊形。Chapter33.2線性動態(tài)規(guī)劃-----合唱隊形問題

問題描述1.問題描述合唱隊形要求：設K位同學從左到右依次編號為1，2，...，K，他們的身高分別為T1,T2，...，TK，則他們的身高滿足T1<...<Ti,且Ti>Ti+1>...>TK(1<=i<=K)。當給定隊員人數(shù)N和每個學生的身高T[i]時，計算需要多少學生出列，可以得到最長的合唱隊形。如下圖所示：

Chapter3編號:12345…………i-1ii+1…..N3.2線性動態(tài)規(guī)劃-----合唱隊形問題

分析最優(yōu)子結構

2.分析最優(yōu)子結構假設第i位同學為最高個，則對其左邊序列求最長遞增序列長度，對其右邊序列求最長遞減序列長度，然后兩者相加再減1（因為第i位同學被重復計算了一次）即可得到整個合唱隊形的長度。設f1(i)（1=<i<=n）為前i個同學的最大上升子序列的長度，計算f1(i)的值時，必須先求得f1(1),f1(2),…,f1(i-1)，再選擇一個最大的f1(j)（j<i），在前j個數(shù)中的最大上升序后再加一，就可以得到前i個數(shù)的最大上升子序列的長度f1(i)。Chapter3由此可見，原問題的解即最長的合唱隊形取決于最大上升子序列和最大下降子序列的長度，具有最優(yōu)子結構的性質。由于在某一時刻，它是單向的從一個狀態(tài)線性遞推到下一個狀態(tài)，屬于線性動態(tài)規(guī)劃問題。3.2線性動態(tài)規(guī)劃-----合唱隊形問題

建立遞歸關系3.建立遞歸關系當組成最大上升子序列時，得到遞歸方程：f1(i)=max{f1(j)+1}(j<i,Tj<Ti)

f1(1)=1;//遞歸出口

設f2(i)為后面N-i+1位排列的最大下降子序列長度，用同樣的方法可以得到遞歸方程：f2(i)=max{f2(j)+1}(i<j,Tj<Ti)f2(N)=1;//邊界值

Chapter33.2線性動態(tài)規(guī)劃-----合唱隊形問題

計算最優(yōu)值

4.計算最優(yōu)值首先用數(shù)組a保存所有人的身高，第一遍正向掃描,從左到右求最大上升子序列的長度，然后反向掃描，從右到左求最大下降子序列的長度，然后依次枚舉由前i個學生組成的最大上升自序列的長度和由后N-i+1個學生組成的最大下降自序列的和，則N次枚舉后得到N個合唱隊形的長度，取其中的最大值，然后用學生總數(shù)n減去該最大值即可得到原問題的解。例3-3：已知8個學生的身高：176、163、150、180、170、130、167、160，計算他們所組成的最長合唱隊形的長度。

Chapter33.2線性動態(tài)規(guī)劃-----合唱隊形問題

計算最優(yōu)值

4.計算最優(yōu)值先從左到右求最大上升子序列的長度，通過比較8個同學的身高，得到f1表如3-3（a）所示,然后從右到左求最大下降子序列的長度,通過比較8個同學的身高，得到f2如表3-3（b）所示，最后將兩個表中對應的元素相加減1（兩表中的值相加，第i位同學被重復計算了一次），得到最終問題的解表如3-3（c）所示：

表3-3合唱隊形問題動態(tài)規(guī)劃表(a)最大上升子序列的長度表f1

(b)最大下降子序列的長度表f2

Chapter3i=1i=2i=3i=4i=5i=6i=7i=8f1[i]11122122i=1i=2i=3i=4i=5i=6i=7i=8f2[i]432431213.2線性動態(tài)規(guī)劃-----合唱隊形問題

程序描述及算法分析Chapter35.程序描述及算法分析(c)最終結果表ans由此可見，當i取4，即以身高為180的同學為中心位置，所形成的合唱隊形的長度最長為5，需要8-5=3個人出列，最終形成的合唱隊形為：176,180,170,167,160?！舅惴?.3用動態(tài)規(guī)劃求解合唱隊形問題】{/*功能：從n個同學中取出k個，求他們所組成的合唱隊形輸入：隊員人數(shù)n和每個學生身高a[i]輸出：最長的合唱隊形的長度ans*/

i=1i=2i=3i=4i=5i=6i=7i=8ans432541323.2線性動態(tài)規(guī)劃-----合唱隊形問題

程序描述及算法分析int*ans

ChorusRank(intn,inta[100]){for(inti=1;i<=n;i++){intf1[maxn];intf2[maxn];f1[i]=1;for(intj=1;j<i;j++)if(a[j]<a[i]&&f1[i]<f1[j]+1)f1[i]=f1[j]+1;//從左到右求最大上升子序列

}for(inti=n;i>=1;i--){f2[i]=1;for(intj=i+1;j<=n;j++)if(a[j]<a[i]&&f2[i]<f2[j]+1)f2[i]=f2[j]+1;//從右到左求最大下降子序列}

int

ans=0;for(inti=1;i<=n;i++)if(ans<f1[i]+f2[i]-1)

ans=f1[i]+f2[i]-1;//枚舉中間最高值returnans;//返回最長合唱隊形的長度}Chapter3算法分析

由于解決該問題時使用了兩次動態(tài)規(guī)劃方法來求解，即第一次求最大上升子序列的長度，第二次求最大下降子序列的長度，再枚舉中間最高的一個人所在隊形的長度。算法實現(xiàn)所需的時間復雜度O(n2)，空間復雜度為O(n)。3.3區(qū)域動態(tài)規(guī)劃-----矩陣連乘問題

Chapter3本節(jié)內容1.問題描述2.窮舉法解決3.動態(tài)規(guī)劃法解決

3.1分析最優(yōu)子結構3.2建立遞歸關系3.3計算最優(yōu)值3.4程序描述及算法分析4.類似問題的解決——凸多邊形的最優(yōu)三角剖分3.3

區(qū)域動態(tài)規(guī)劃

——矩陣連乘問題（最佳次序）

Chapter3

可用區(qū)域動態(tài)規(guī)劃法解決的問題的特點是：對整個問題設置最優(yōu)值，枚舉剖分（合并）點，將問題分解為左右兩部分，合并兩部分的最優(yōu)值得到原問題的最優(yōu)值。如求從i到j的最優(yōu)值，枚舉剖分(合并)點，將（i，j）分成左右兩個區(qū)間，分別求左右兩邊的最優(yōu)值，如下圖：圖3-2圖圖圖3-2區(qū)域動態(tài)規(guī)劃示意圖遞歸方程一般為：其中k為劃分點。3.3

矩陣連乘問題（最佳次序）

------問題描述

Chapter3

對于任意兩個矩陣，

它們相乘得到矩陣，即

。由于計算

的標準算法中，主要計算量在三重循環(huán)，具體值為

。當計算三個矩陣的連乘積

，假設

是個

的矩陣，

是個

的矩陣，

是個

的矩陣，可知：

由此可見，通過為矩陣乘法加括號，不同的計算次序所產生的計算量是不同的，因此應該從不同計算量中找出最少計算量，從而確定最優(yōu)計算次序，即尋找矩陣連乘問題的最優(yōu)完全加括號方式。1.問題描述3.3.1

矩陣連乘問題

-----窮舉法解決2. 解決方法一【窮舉法】 列出矩陣連乘問題的所有計算次序，設P(n)為n個矩陣連乘積可能的運算順序的數(shù)目，則有如下遞推關系：Chapter3解此遞歸方程可得，P(n)實際上是Catalan數(shù)，即：

由此可見，窮舉法的時間復雜度為n的指數(shù)函數(shù)。3.3矩陣連乘問題

-----窮舉法解決Chapter3例3-3：求四個矩陣連乘的組合數(shù)目。由此說明3個矩陣連乘有2種組合，即與。而4個矩陣連乘有5種組合：、Chapter3

解決方法二【動態(tài)規(guī)劃法】

1、分析最優(yōu)子結構以四個矩陣連乘最優(yōu)順序為例：列出上述所有的5種不同的乘積結合次序。矩陣連乘問題就是從這5種方式中找出乘法次數(shù)最少的連乘方式，即找到一個最優(yōu)的計算次序。當矩陣個數(shù)增加到n個，計算這n個矩陣的連乘積，簡寫為M[1:n]。3.3矩陣連乘問題-----動態(tài)規(guī)劃法解決

分析最優(yōu)子結構

當在計算M[1:n]的一個最優(yōu)計算次序時，設這個最優(yōu)計算次序在矩陣和之間將矩陣鏈斷開，則完全加括號方式為，最終的結果M[1:n]的最優(yōu)計算次序取決于M[1:k]和M[k+1:n]的最優(yōu)計算次序。即矩陣連乘問題的最優(yōu)解包含著其子問題的最優(yōu)解，具有最優(yōu)子結構的性質，同時這一性質是這類問題可以用動態(tài)規(guī)劃算法解決的前提。Chapter32、建立遞歸關系設n個矩陣連乘，的行列數(shù)分別為，，設是計算的最小值，滿足最優(yōu)性，則有：3.3矩陣連乘問題-----動態(tài)規(guī)劃法解決

建立遞歸關系其中：是計算的最小耗費；是計算的最小耗費；和分別是矩陣的行數(shù)和列數(shù)，和分別是矩陣的行數(shù)和列數(shù)。給出了計算M[i:j]所需的最小數(shù)乘次數(shù)，同時還確定了計算M[i:j]的最優(yōu)次序時的最佳斷開位置k。由于有三個變量i,j,k的三重循環(huán)，所示時間復雜度為：，比窮舉法所需的時間少。Chapter33.3矩陣連乘問題-----動態(tài)規(guī)劃法解決

建立遞歸關系

解：Chapter3例3-4：計算矩陣連乘的最優(yōu)組合。有4個矩陣如下，3、計算最優(yōu)值例3-4：計算矩陣連乘的最優(yōu)組合。有4個矩陣如下，3.3矩陣連乘問題-----動態(tài)規(guī)劃法解決

計算最優(yōu)值Chapter3

由此可知，這四個矩陣連乘所用到的最小乘積次數(shù)是2200，最優(yōu)計算次序是。3.3矩陣連乘問題-----動態(tài)規(guī)劃法解決

計算最優(yōu)值在整個計算過程中可以填寫一下表格：

表3-4矩陣連乘問題的遞推二維表Chapter3

4、程序描述及算法分析

要計算M[i:j]=M[i:k]*M[k+1:j]的值，首先輸入參數(shù){b0,b1,b2,...bn}存儲n個矩陣的階數(shù)下標，并初始化M[i][i]=0，i=1,2,…,n。然后根據遞歸式，按矩陣鏈長增長的方式依次計算M[i][i+1]，i=1,2,…,n-13.3矩陣連乘問題-----動態(tài)規(guī)劃法解決

程序描述及算法分析

陣鏈長度為2)；M[i][i+2]，i=1,2,…,n-2(矩陣鏈長度為3)；……，在計算M[i][j]時，只用到已計算出的M[i][k]和M[k+1][j]。具體如算法3.4所示。

算法3.4用動態(tài)規(guī)劃求解矩陣連乘問題

功能：找出n個矩陣的連乘積的一個所需數(shù)乘次數(shù)最少的連乘方式，即最優(yōu)的計算次序。Chapter3

3.3矩陣連乘問題-----動態(tài)規(guī)劃法解決

程序描述及算法分析輸入：n為連乘矩陣的個數(shù);{b0,b1,b2,...bn}存儲n個矩陣的階數(shù)下標的數(shù)組；M[i][j]是計算的最小值；t[i][j]是連乘時的最佳斷開位置。Chapter3voidMultiplyMatrix(int*b,intn,int**M,int**t){

//初始化

for(intk=1;k<=n;k++)

for(intj=1;j<=n;j++){

M[k][j]=0;

t[k][j]=0;}

for(intr=2;r<=n;r++)//r控制矩陣鏈長度

for(inti=1;i<=n-r+1;i++){

輸出：最小計算次數(shù)矩陣M、最佳斷開位置矩陣t。

3.3矩陣連乘問題-----動態(tài)規(guī)劃法解決

程序描述及算法分析Chapter3

intj=i+r-1;

M[i][j]=M[i+1][j]+b[i-1]*b[i]*b[j];

t[i][j]=i;//最佳斷開位置為i

for(intk=i+1;k<j;k++)//改變k,即改變斷開位置{

intl=M[i][k]+M[k+1][j]+b[i-1]*b[k]*b[j];

if(l<M[i][j]){

M[i][j]=l;

t[i][j]=k;//將矩陣斷開的最佳位置存入數(shù)組t中}}}}

3.3矩陣連乘問題-----動態(tài)規(guī)劃法解決

程序描述及算法分析Chapter3

算法的主要計算量取決于程序中對r，i和k的三重循環(huán)，循環(huán)體內的計算量為，容易得出其時間復雜度為。算法所占用的空間顯然為。3.3矩陣連乘問題-----動態(tài)規(guī)劃法解決

程序描述及算法分析3.3

區(qū)域動態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

問題描述

連接一個多邊形邊界上或其內部的任意兩點，若該連線上的所有的點都在多邊形內部或邊界上，則該多邊形為凸多邊形。通常，可以用多邊形頂點的逆時針序列來表示它，即表示有條邊的一個凸多邊形，其中約定。對平面上的一個凸多邊形進行三角剖分，即通過多邊形的若干條不相交的弦將多邊形分割成互不重疊的若干個三角形，如圖3-2所示。Chapter3

圖3-2凸多邊形的兩個不同三角剖分1.問題描述3.3區(qū)域動態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

問題描述

凸多邊形最優(yōu)三角剖分問題描述：給定一個凸多邊形，以及定義在由多邊形的邊和弦組成的三角形上的權函數(shù)。要求確定該凸多邊形的一個三角剖分，使得該三角剖分對應的權即剖分中諸三角形上的權之和為最小。三角形的權函數(shù)的定義方式很多，如：定義，其中，是點到點的歐氏距離，對應于此權函數(shù)的最優(yōu)三角剖分即為最小弦長三角剖分。Chapter3

凸多邊形的三角剖分與矩陣連乘積的最優(yōu)計算次序問題之間具有十分緊密的聯(lián)系，這些問題之間的相關性可從它們所對應的完全二叉樹的同構性得到。1.問題描述3.3區(qū)域動態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

三角剖分的結構及其相關問題

Chapter3

2.三角剖分的結構及其相關問題三角剖分問題和矩陣連乘問題（表達式的完全加括號問題）都可以表述成一個完全二叉樹（不含度為1的結點的二叉樹）,如圖3-3所示：圖3-3表達式語法樹與三角剖分的對應3.3區(qū)域動態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

三角剖分的結構及其相關問題

Chapter3

一個表達式的完全加括號方式相應于一棵完全二叉樹，稱為表達式的語法樹。例如，完全加括號的矩陣連乘積所相應的語法樹如圖3-3(a)所示。這里有n=6個矩陣連乘，其中的每個矩陣對應于凸(n+1)邊形中的一條邊上的結點。

凸多邊形的三角剖分也可以用語法樹表示。例如，圖3-3(b)中凸多邊形的三角剖分，與圖3-3(a)很類似。(b)圖語法樹的根結點為邊上的圓形結點，且該語法樹的其他內部結點都是用小圓形表示的，并被放置在新增剖分虛線上，(b)圖語法樹的葉子結點使用小方塊表示，被放置在剖分前凸多邊形的各條邊上。多邊形中3.3區(qū)域動態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

三角剖分的結構及其相關問題

除邊外的每一條邊是語法樹的一個葉結點。樹根是三角形的一條邊，該三角形將原多邊形分為三角形,凸多邊形和凸多邊形三個部分。三角形的另外兩條邊，即弦和為根的兩個兒子。以它們?yōu)楦淖訕浞謩e表示凸多邊形和凸多邊形的三角剖分。Chapter3

矩陣連乘積中的每個矩陣對應于凸(n+1)邊形中的一條邊。三角剖分中的一條弦，對應于矩陣連乘積。由此可見，n個矩陣的完全加括號乘積與凸(n+1)邊形的三角剖分之間存在著一一對應的關系。3.3區(qū)域動態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

最優(yōu)子結構性質

3.最優(yōu)子結構性質

凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結構性質。證明：（反證法）事實上，若凸(n+1)邊形的最優(yōu)三角剖分T包含三角形，，則T的權為三角形的權、子多邊形和三個部分權之和。另外可以斷定由T所確定的這兩個子多邊形的三角剖分也是最優(yōu)的。因為若有或的更小權的三角剖分將導致T不是最優(yōu)三角剖分的矛盾。Chapter3

3.3區(qū)域動態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

遞歸結構Chapter3

定義,為凸子多邊形的最優(yōu)三角剖分所對應的權函數(shù)值，即其最優(yōu)值。為方便起見，設退化的多邊形具有權值0。據此定義，要計算的凸(n+1)邊形T的最優(yōu)權值為

。

的值可以利用最優(yōu)子結構性質遞歸地計算。當j-i≥1時，凸子多邊形至少有3個頂點。由最優(yōu)子結構性質，的值應為的值加上的值，再加上三角形的權值，其中i≤k≤j-1。由于在計算時還不知道k的確切位置，而k的所有可能位置只有j-i個，因此可以在這j-i個位置中選出使值達到最小的位置。由此，可遞歸地定義為：4.最優(yōu)三角剖分的遞歸結構3.3區(qū)域動態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

計算最優(yōu)值

可見除了權函數(shù)的定義外，與矩陣連乘的遞歸式完全相同。因此只要對計算的算法做很小的修改就完全適用于計算。Chapter35.計算最優(yōu)值及構造最優(yōu)三角剖分算法3.5用動態(tài)規(guī)劃求解凸多邊形最優(yōu)三角剖分問題功能：將一個凸多邊形進行最優(yōu)三角剖分。輸入：凸多邊形頂點個數(shù)m，各個頂點的坐標。

3.3區(qū)域動態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

計算最優(yōu)值

輸出：記錄最優(yōu)三角剖分所對應的權函數(shù)值的矩陣t、記錄最優(yōu)三角剖分中所有三角形信息的矩陣s和凸(n+1)邊形的最優(yōu)三角剖分所對應的權值。Chapter3bool

CTriangle::MinWeightTriangulation(){ //計算最優(yōu)值 //初始化

for(inti=1;i<=n;i++) {

for(intj=1;j<=n;j++)

{

t[i][j]=0;

s[i][j]=0;

} }

3.3區(qū)域動態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

計算最優(yōu)值

Chapter3for(intr=2;r<=n;r++)

for(inti=1;i<=n-r+1;i++) {

intj=i+r-1;

t[i][j]=t[i+1][j]+w(v[i-1],v[i],v[j]);

s[i][j]=i;//最佳剖分點為i

for(intk=i+1;k<i+r-1;k++)

{

intu=t[i][k]+t[k+1][j]+w(v[i-1],v[k],v[j]);//改變k，即改變

剖分點

if(u<t[i][j])

{

t[i][j]=u;

s[i][j]=k;//將凸多邊形的最佳剖分點存入數(shù)組s中

}

3.3區(qū)域動態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

計算最優(yōu)值Chapter3

與算法MultiplyMatrix一樣，算法MinWeightTriangulation占用空間，耗時。

}

}

returntrue;}3.4背包動態(tài)規(guī)劃-----0-1背包問題

Chapter3本節(jié)內容1.問題分類2.分析最優(yōu)子結構3.建立遞歸關系4.計算最優(yōu)值5.程序描述及算法分析Chapter33.4背包動態(tài)規(guī)劃-----0-1背包問題

問題分類1.背包動態(tài)規(guī)劃問題的分類<1>0-1背包問題：這是最基本的背包問題，特點是：每種物品只有一件，可以選擇放與不放。當用子問題定義狀態(tài)時，若f[i][v]表示前i件物品放入一個容量恰為v的背包中獲得的價值最大。可以得到遞歸方程為：f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+a[i]}(其中a[i]和w[i]分別為每個物體的價值和重量)最后要求f[n][v]的值，因為容量恰為v。其他類型的背包問題往往也是有0-1背包問題轉化而來的。例如采藥、BuyLow，BuyLower、排隊買票問題等。53<2>完全背包問題：與0-1背包問題類似，所不同的是每件物品有無限件。遞歸方程為：f[i][j]=max{f[i-1][j-k*w[i]]+k*a[i](k*v[i]<=j)},在這類問題中，如果當前物品與其它物品相比價值低，體積大，就可以將其舍棄，這樣可以大大減少物品數(shù)。與此同類的問題還有：總分、砝碼稱重、無限硬幣問題等。<3>多重背包問題：

與完全背包類似，所不同的是第i種物品可以使用s[i]次，遞歸方程：f[i][j]=max{f[i-1][j-k*w[i]]+k*a[i](k<=s[i]&&k*v[i]<=j)},類似的問題如郵票問題。Chapter33.4背包動態(tài)規(guī)劃—0-1背包問題

問題分類54<4>混合三種背包的問題：

即有的物品只能使用一次，有的可以使用規(guī)定的次數(shù)，有的可以使用無限次。其實，只需加幾個判斷條件就可以了?？傮w的解決框架如下所示：

for(i=1;i<=n;i++)

for(j=1;j<=V;j++){if是0-1背包問題

f[i][j]=max{f[i-1][j],f[i-1][j-w[i]]+a[i]}if是完全背包問題

f[i][j]=max{f[i-1][j-k*w[i]]+k*a[i](k*w[i]<=j)}if是多重背包問題

f[i][j]=max{f[i-1][j-k*w[i]]+k*a[i](k<=s[i]&&k*w[i]<=j)}

}Chapter33.4背包動態(tài)規(guī)劃—0-1背包問題

問題分類550-1背包動態(tài)規(guī)劃問題

現(xiàn)有n件物品，一個容量為c的背包。第i件物品重量為wi,價值為vi。已知對于一件物品必須選擇取或不取，且每件物品只能被取一次（這就是“0-1”的含義）。求放置那幾件物品進背包，使得背包中物品價值最大？

此問題可形式化表示為求解：物品價值：物品重量：

Chapter33.4

0-1背包問題描述

-----問題描述562.分析最優(yōu)子結構

設（y1y2,…,yn）是所給0-1背包問題的一個最優(yōu)解，則（y2,…,yn）是下面一個子問題的最優(yōu)解：

如若不然，設（Z2,…,Zn)是上述子問題的一個最優(yōu)解，則因此，這說明（y1,Z2,…,Zn）是所給0-1背包問題比（y1,y2,…,yn）更優(yōu)的解，從而導致矛盾。

0-1背包動態(tài)規(guī)劃問題0-1背包動態(tài)規(guī)劃問題Chapter33.40-1背包問題描述

-----分析最優(yōu)子結構

57

如果第i個物品的重量大于背包的容量，則不裝入物品i，計算從i到n的n-i+1個物品得到的最大值和計算i+1到n的n-i個物品得到的最大價值是相同的，即：m(i,j)=m(i+1,j)0≤j≤wi如果第i個物品的重量小于背包的容量，則會出現(xiàn)以下兩種情況：（1）若把第i個物品裝入背包，則背包中物品的價值等于把后i+1個物品裝入容量為j-wi的背包中的價值再加上第i個物品的價值vi。（2）若第i個物品沒有裝入背包，則背包中物品的價值等于把后i+1個物品裝入容量為j的背包中所取得的價值。顯然，應兩者中值較大者作為把后i個物品裝入容量為j的背包總的最優(yōu)解，如下是所示：m(i,j)=max(m(i+1,j),m(i+1,j-wi)+vi)，j≥wi

3.建立遞歸關系

設所給0-1背包問題的子問題：0-1背包動態(tài)規(guī)劃問題0-1背包動態(tài)規(guī)劃問題Chapter33.40-1背包問題描述

-----建立遞歸關系58

下面通過實例對0-1背包的遞歸時進行具體研究：例如，有5個物品，起重量分別是{2,2,6,5,4}，價值分別為{6,3,5,4,6}，背包的容量為10。要求如何是背包的容量最大？根據上面研究的遞歸式可以迅速建立一張二維表V，其建立結果如表3.5所示：

m（i，j）＝m(i+1,j)當wi>j（不夠裝不裝）maxm(i+1,j)夠裝但不裝(性價比低)m(i+1,j-wi)+vi夠裝而且裝

最終建立如下計算m(i,j)的遞歸式如下：

0-1背包動態(tài)規(guī)劃問題Chapter33.40-1背包問題描述

-----建立遞歸關系59

表3-10-1背包問題的遞歸二維表

通過這張二維表，可以發(fā)現(xiàn)在背包裝到容量為8的時候，背包的價值是最大的。但是如何通過這張二維表確定那幾件物品被裝入背包？

0-1背包動態(tài)規(guī)劃問題Chapter33.40-1背包問題描述

-----建立遞歸關系60

表3-10-1背包問題的遞歸二維表

這里可以從m(n，c)的值向前推，如果m(n，c)>m(n-1，c),表明第n個物品被裝入背包，前n-1個物品被裝入容量為C-Wn的背包中；否則，第n個物品沒有被裝入背包，前n-1個物品被裝入容量為c的背包中。以此類推，直到確定第n個物品是否被裝入背包中為止。由此，得如下函數(shù)：

所以，上述0-1背包裝載序列是：當背包所裝容量為8時，背包價值最大15。0-1背包動態(tài)規(guī)劃問題Chapter33.40-1背包問題描述

-----建立遞歸關系61

4.程序描述及算法分析

當物體的重量為正數(shù)時，用二維數(shù)組來存儲嗎（i,j）的相應，可以設計解0-1背包問題的動態(tài)規(guī)劃算法Beibao如算法3.5.【算法3.5用動態(tài)規(guī)劃求0-1背包問題】/*功能：找出裝入容量為c的背包中的，有最大價值的物品輸入：n是背包的物品種類

c是背包的容量

v數(shù)組是每個物品的價值w數(shù)組是每個物品的重量m數(shù)組是0-1背包的最優(yōu)質輸出：背包的最大價值和以0-1方式顯示的裝入的物品*/0-1背包動態(tài)規(guī)劃問題0-1背包動態(tài)規(guī)劃問題Chapter33.4.0-1背包問題描述

-----程序描述及算法分析

62

VoidBeibao(int

v,intw,intc,intn,int**m){

int

jmax=min(w[n]-1,c);

for(intj=0;j<=jmax;j++)

m[n][j]=0;//初始化數(shù)組mfor(intj=w[n];j<=c;j++)

m[n][j]=v[n];

for(inti=n-1;i>1;i--){jmax=min(w[i]-1,c);

for(intj=0;j<jmax;j++)

m[i][j]=m[i+1][j];

for(intj=w[i];j<=c;j++)

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+V[i]);//比較選擇當前物品與沒有選擇當前物品時背包所獲得的最大值}0-1背包動態(tài)規(guī)劃問題0-1背包動態(tài)規(guī)劃問題Chapter33.4.0-1背包問題描述

-----程序描述及算法分析

m[1][c]=m[2][c];if(c>w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}Voidtaceback(int**m,int

w,int

c,int

n,intx){for(inti=1;i<n;i++)

if(m[i][c]==m[i+1][c])//表示序號為i的物品沒有被裝入背包

x[i]=0;else{x[i]=1;//表示序號為i的物品被裝入背包c-=w[i];}X[n]=(m[n][c])?1:0;}

從計算m(i,j)的遞歸公式容易看出，上述算法beibao的關鍵是二維表m(i,j)的建立，所以該算法的時間復雜度為O(n*c),而Traceback中有一個for循環(huán)，該算法的時間復雜度為O（n）。63

5.改進的背包算法通過與現(xiàn)實生活相聯(lián)系發(fā)現(xiàn)，上述算法是極其特殊的情形，其中有兩個比較明顯的缺點。其一是算法要求所給背包重量C和物品重量Wi是整數(shù)，這在現(xiàn)實生活中基本上實行不通的。其次，當背包容量很大時，算法需要計算的時間很多。例如當c>時，算法的時間復雜度為O（n*),這個指數(shù)級得時間對于計算機來說是一個很大的耗費。由計算m(i,j)的遞歸式繪制當i=1是的函數(shù)圖象，如下圖示：0-1背包動態(tài)規(guī)劃問題0-1背包動態(tài)規(guī)劃問題Chapter33.4.0-1背包問題描述

-----改進的背包算法

64

通過觀察發(fā)現(xiàn)在變量j是連續(xù)的情況下，可以對每一個確定的i，用一個表p[i]來存儲函數(shù)m(i,j)的全部跳躍點。對每一個確定的實數(shù)j，可以通過查表p[i]來確定函數(shù)m(i,j)的值。p[i]中全部跳躍點（j,m(i,j))依j的值升序排列。由于函數(shù)m(i,j)是關于變量j的階梯狀單調不減函數(shù)，故p[i]中全部跳躍點的m(i,j)值也是遞增排列的。所以可以記錄每一個i值的跳躍點，最后通過查找得出最優(yōu)解和裝載序列。下面構造不同i值的跳躍點，在構造之前需要明確下面量的含義：

0-1背包動態(tài)規(guī)劃問題Chapter33.4.0-1背包問題描述

-----改進的背包算法

65

（1）函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-Wi)+Vi做max運算得到的。因此，函數(shù)m(i,j)的跳躍點p[i]包含于函數(shù)m(i+1,j)的跳躍點p[i+1]與函數(shù)m(i+1,j-Wi)+Vi的跳躍點集q[i+1]的并集中。其中q[i+1]=p[i+1]⊕(wi,vi)={j+wi,m(i,j)+vi|(j,m(i,j))∈p[i+1]}(其中“⊕”在這代表一個廣義的運算符號)（2）設(a,b)和(c,d)是p[i+1]和q[i+1]并集中的兩個跳躍點，則當c>=a且d<b時，(c,d)受控于(a,b),從而(c,d)不是p(i)中的跳躍點。0-1背包動態(tài)規(guī)劃問題Chapter33.4.0-1背包問題描述

-----改進的背包算法

66

0-1背包動態(tài)規(guī)劃問題

在遞歸地由表p[i+1]計算表p[i]時，可先由p[i+1]計算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳躍點得到表p[i]。如當n=5,c=10,W={2,2,6,5,4},v={6,3,5,4,6}時，構造跳躍點的過程如下：初始時p[6]={(0,0)},(W5,V5)=(4,6)。因此，q[6]=p[6]⊕(W5,V5)={(4,6)}。p[5]={(0,0),(4,6)}。q[5]=p[5]⊕(W4,V4)={(5,4),(9,10)}。從跳躍點集p[5]與q[5]的并集p[5]Ｕq[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳躍點(5,4)受控于跳躍點(4,6)。將受控跳躍點(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)}q[4]=p[4]⊕(6,5)={(6,5),(10,11)}p[3]={(0,0),(4,6),(9,10),(10,11)}q[3]=p[3]⊕(2,3)={(2,3),(6,9)}0-1背包動態(tài)規(guī)劃問題Chapter33.4.0-1背包問題描述

-----改進的背包算法

67

p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)}q[2]=p[2]⊕(2,6)={(2,6),(4,9),(6,12),(8,15)}p[1]={(0,0),(2,6),(4,9),(6,12),(8,15)}p[1]的最后的那個跳躍點(8,15)給出所求的最優(yōu)值為m(1,c)=15。改進后的算法代碼如算法3.6?！舅惴?.6改進的用動態(tài)規(guī)劃求0-1背包問題】/*功能：找出裝入容量為c的背包中的，有最大價值的物品輸入：n是背包的物品種類C是背包的容量v數(shù)組是每個物體的價值w數(shù)組是每個物體的重量p數(shù)組為存放的跳躍點x是以0-1方式顯示的最優(yōu)值輸出：背包的最大價值和裝入的物品求最優(yōu)值時的跳躍點*/0-1背包動態(tài)規(guī)劃問題Chapter33.4.0-1背包問題描述

-----改進的背包算法

68

0-1背包動態(tài)規(guī)劃問題intBeibao(intn,floatc,floatv[],floatw[],floatp[][2],intx[]){int*head=newint[n+2]head[n+1]=0;p[0][0]=0;p[0][1]=0;intleft=0,right=0,next=0;head[n]=1;for(inti=n;i>=1;i--){intk=left;for(intj=left;j<=right;j++){if(p[j][0]+w[i]>c)break;floaty=p[j][0]+w[i],m=p[j][1]+v[i];

0-1背包動態(tài)規(guī)劃問題Chapter33.4.0-1背包問題描述

-----改進的背包算法

while(k<=right&&p[k][0]<y){p[next][0]=p[k][0];p[next++][1]=p[k++][1];}if(k<=right&&p[k][0]==y){if(m<p[k][1])m=p[k][1];k++;}if(m>p[next-1][1]){p[next][0]=y;p[next++][1]=m;}69

0-1背包動態(tài)規(guī)劃問題while(k<=right&&p[k][1]<=p[next-1][1])k++;}while(k<=right){p[next][0]=p[k][0];p[next++][1]=p[k++][1];}left=right+1;right=next-1;head[i-1]=next;}traceback(n,w,v,p,head,x);cout<<“跳躍點是：”<<endl;intj=n;for(i=0;i<next;i++){cout<<"（"<<p[i][0]<<","<<p[i][1]<<"）";

0-1背包動態(tài)規(guī)劃問題Chapter33.4.0-1背包問題描述

-----改進的背包算法

if(i==(head[j]-1)){cout<<endl;j--;}}returnp[next-2][1]+3;}voidtraceback(intn,floatw[],floatv[],floatp[][2],int*head,intx[]){floatj=p[head[0]-1][0];floatm=p[head[0]-1][1];for(inti=1;i<=n;i++){

x[i]=0;

for(intk=head[i+1];k<=head[i]-1;k++){if(p[k][0]+w[i]==j&&p[k][1]+v[i]==m)

x[i]=1;j=p[k][0];m=p[k][1];break;}}}}70

上述算法的主要計算量在于計算跳躍點集p[i](1≤i≤n)。由于q[i+1]=p[i+1]⊕(wi，vi)，故計算q[i+1]需要O(|p[i+1]|)計算時間。合并p[i+1]和q[i+1]并清除受控跳躍點也需要O(|p[i+1]|)計算時間。從跳躍點集p[i]的定義可以看出，p[i]中的跳躍點相應于xi,…,xn的0/1賦值。因此，p[i]中跳躍點個數(shù)不超過。由此可見，算法計算跳躍點集p[i](1≤i≤n)所花費的計算時間為Chapter33.4.0-1背包問題描述

-----改進的背包算法

從而，改進后算法的計算時間復雜性為O()。當所給物品的重量wi(1≤i≤n)是整數(shù)時，|p[i]|≤c+1，(1≤i≤n)。在這種情況下，改進后算法的計算時間復雜性為O(min{nc,})。3.5樹形動態(tài)規(guī)劃

------最優(yōu)二叉搜索樹Chapter3本節(jié)內容1.問題描述2.窮舉法解決3.動態(tài)規(guī)劃法解決

3.1分析最優(yōu)子結構3.2遞歸計算最優(yōu)值3.3程序描述及算法分析3.4構造最優(yōu)值3.5改進的算法3.5樹形動態(tài)規(guī)劃------最優(yōu)二叉搜索樹

問題描述

1.問題描述

樹形動態(tài)規(guī)劃是建立在樹結構的基礎上的，當動態(tài)規(guī)劃的各階段形成一棵樹，利用各階段之間的關系（遞歸方程），從根傳遞有用信息給葉子節(jié)點，從而得到最優(yōu)解或者從葉節(jié)點（邊界）開始逐步向上一層的節(jié)點（即父節(jié)點）進行動態(tài)規(guī)劃，直到動規(guī)到根節(jié)點，（即原問題），求的問題的最優(yōu)解，下面我們就舉例說明：Chapter3二叉搜索樹是一顆滿足如下條件的二叉樹：（1）若它的左子樹非空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；（2）若它的右子樹非空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；（3）它的左、右子樹也分別為二叉搜索樹。0.1*1+0.2*2+0.4*3+0.3*4=2.90.1*2+0.2*1+0.4*3+0.3*2=2.20.1*2+0.2*1+0.4*2+0.3*3=2.10.1*3+0.2*4+0.4*2+0.3*1=2.2鍵的平均比較次數(shù)：

設二叉樹有n個帶權值的結點，則從根結點到各個結點的路徑長度與相應結點權值的積之和叫二叉搜索樹的帶權路徑長度，給定一組有確定權值的結點，可以構造出不同形態(tài)的帶權二叉樹.如概率分別為0.1，0.2，0.4，0.3。鍵值為3，7，9，12的二叉查找樹為：3Chapter3.5樹形動態(tài)規(guī)劃------最優(yōu)二叉搜索樹

問題描述3.5樹形動態(tài)規(guī)劃------最優(yōu)二叉搜索樹

問題描述Chapter3設S={x1,x2,...,xn}是一個有序集，且x1<x