淺談樹型動(dòng)態(tài)規(guī)劃

《淺談樹型動(dòng)態(tài)規(guī)劃》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、淺談樹型動(dòng)態(tài)規(guī)劃一、什么是樹型動(dòng)態(tài)規(guī)劃顧名思義，樹型動(dòng)態(tài)規(guī)劃就是在“樹”的數(shù)據(jù)結(jié)構(gòu)上的動(dòng)態(tài)規(guī)劃，平時(shí)作的動(dòng)態(tài)規(guī)劃都是線性的或者是建立在圖上的，線性的動(dòng)態(tài)規(guī)劃有二種方向既向前和向后，相應(yīng)的線性的動(dòng)態(tài)規(guī)劃有二種方法既順推與逆推，而樹型動(dòng)態(tài)規(guī)劃是建立在樹上的，所以也相應(yīng)的有二個(gè)方向：1．根—>葉：不過這種動(dòng)態(tài)規(guī)劃在實(shí)際的問題中運(yùn)用的不多，也沒有比較明顯的例題，所以不在今天討論的范圍之內(nèi)。2．葉－>根：既根的子節(jié)點(diǎn)傳遞有用的信息給根，完后根得出最優(yōu)解的過程。這類的習(xí)題比較的多，下面就介紹一些這類題目和它

2、們的一般解法。二、例題與解析加分二叉樹【問題描述】設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數(shù)字1,2,3,…,n為節(jié)點(diǎn)編號。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)），記第i個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為di，tree及它的每個(gè)子樹都有一個(gè)加分，任一棵子樹subtree（也包含tree本身）的加分計(jì)算方法如下：subtree的左子樹的加分×subtree的右子樹的加分＋subtree的根的分?jǐn)?shù)若某個(gè)子樹為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空子樹。試求一棵符合中序

3、遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；（1）tree的最高加分（2）tree的前序遍歷【輸入格式】第1行：一個(gè)整數(shù)n（n＜30），為節(jié)點(diǎn)個(gè)數(shù)。第2行：n個(gè)用空格隔開的整數(shù)，為每個(gè)節(jié)點(diǎn)的分?jǐn)?shù)（分?jǐn)?shù)＜100）?！据敵龈袷健康?行：一個(gè)整數(shù)，為最高加分（結(jié)果不會(huì)超過4,000,000,000）。第2行：n個(gè)用空格隔開的整數(shù)，為該樹的前序遍歷?！据斎霕永?571210【輸出樣例】14531245[分析]很顯然，本題適合用動(dòng)態(tài)規(guī)劃來解。如果用數(shù)組value[i,j]表示從節(jié)點(diǎn)

4、i到節(jié)點(diǎn)j所組成的二叉樹的最大加分，則動(dòng)態(tài)方程可以表示如下：value[i,j]=max{value[i,i]+value[i+1,j],value[i+1,i+1]+value[i,i]*value[i+2,j],value[i+2,i+2]+value[i,i+1]*value[i+3,j],…,value[j-1,j-1]+value[i,j-2]*value[j,j],value[j,j]+value[i,j-1]}題目還要求輸出最大加分樹的前序遍歷序列，因此必須在計(jì)算過程中記下從節(jié)點(diǎn)i

5、到節(jié)點(diǎn)j所組成的最大加分二叉樹的根節(jié)點(diǎn)，用數(shù)組root[i,j]表示[PASCAL源程序]{$N+}programNOIP2003_3_Tree;constmaxn=30;vari,j,n,d:byte;a:array[1..maxn]ofbyte;value:array[1..maxn,1..maxn]ofcomp;root:array[1..maxn,1..maxn]ofbyte;s,temp:comp;f1,f2:text;fn1,fn2,fileNo:string;procedurepr

6、eorder(p1,p2:byte);{按前序遍歷輸出最大加分二叉樹}beginifp2>=p1thenbeginwrite(f2,root[p1,p2],'');preorder(p1,root[p1,p2]-1);preorder(root[p1,p2]+1,p2);end;end;beginwrite('InputfileNo:');readln(fileNo);fn1:='tree.in'+fileNo;fn2:='tree.ou'+fileNo;assign(f1,fn1);reset

7、(f1);assign(f2,fn2);rewrite(f2);readln(f1,n);fori:=1tondoread(f1,a[i]);close(f1);fillchar(value,sizeof(value),0);fori:=1tondobeginvalue[i,i]:=a[i];{計(jì)算單個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的加分}root[i,i]:=i;{記錄單個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的根節(jié)點(diǎn)}end;fori:=1ton-1dobeginvalue[i,i+1]:=a[i]+a[i+1];{計(jì)算相鄰兩

8、個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的最大加分}root[i,i+1]:=i;{記錄相鄰兩個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的根節(jié)點(diǎn)；需要說明的是，兩個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹，其根節(jié)點(diǎn)可以是其中的任何一個(gè)；這里選編號小的為根節(jié)點(diǎn)，則編號大的為其右子樹；若選編號大的為根節(jié)點(diǎn)，則編號小的為其左子樹；因此，最后輸出的前序遍歷結(jié)果會(huì)有部分不同，但同樣是正確的。如果最大加分二叉樹的所有節(jié)點(diǎn)的度數(shù)都是0或2，則最后輸出的前序遍歷結(jié)果是唯一的。}end;ford:=2ton-1dobegin{依次計(jì)算間距為d的兩個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的最大加分}for