朱全民樹型動(dòng)態(tài)規(guī)劃ppt課件

.,樹型動(dòng)態(tài)規(guī)劃,.,加分二叉樹,給定一個(gè)中序遍歷為1,2,3,n的二叉樹每個(gè)結(jié)點(diǎn)有一個(gè)權(quán)值定義二叉樹的加分規(guī)則為：左子樹的加分右子樹的加分根的分?jǐn)?shù)若某個(gè)樹缺少左子樹或右子樹，規(guī)定缺少的子樹加分為1。構(gòu)造符合條件的二叉樹該樹加分最大輸出其前序遍歷序列,.,樣例中序遍歷為1,2,3,4,5的二叉樹有很多，下圖是其中的三棵，其中第三棵加分最大，為145.,.,分析,性質(zhì)：中序遍歷是按“左-根-右”方式進(jìn)行遍歷二叉樹，因此二叉樹左孩子遍歷序列一定在根結(jié)點(diǎn)的左邊，右孩子遍歷序列一定在根結(jié)點(diǎn)的右邊！因此，假設(shè)二叉樹的根結(jié)點(diǎn)為k，那么中序遍歷為1,2,n的遍歷序列，左孩子序列為1,2,k-1，右孩子序列為k+1,k+2,n，如下圖,.,動(dòng)態(tài)規(guī)劃,設(shè)f(i,j)中序遍歷為i,i+1,j的二叉樹的最大加分，則有：f(i,j)=maxfi,k-1*fk+1,j+dk顯然f(i,i)=di答案為f(1,n)1=i=k=j=n時(shí)間復(fù)雜度O(n3)要構(gòu)造這個(gè)樹，只需記錄每次的決策值，令b(i,j)=k，表示中序遍歷為i,i+1,j的二叉樹的取最優(yōu)決策時(shí)的根結(jié)點(diǎn)為k最后前序遍歷這個(gè)樹即可。,.,選課,給定M門課程，每門課程有一個(gè)學(xué)分要從M門課程中選擇N門課程，使得學(xué)分總和最大其中選擇課程必須滿足以下條件：每門課程最多只有一門直接先修課要選擇某門課程，必須先選修它的先修課M,N=500,.,分析,每門課程最多只有1門直接先修課，如果我們把課程看成結(jié)點(diǎn)，也就是說每個(gè)結(jié)點(diǎn)最多只一個(gè)前驅(qū)結(jié)點(diǎn)。如果把前驅(qū)結(jié)點(diǎn)看成父結(jié)點(diǎn)，換句話說，每個(gè)結(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)。顯然具有這種結(jié)構(gòu)的模型是樹結(jié)構(gòu)，要么是一棵樹，要么是一個(gè)森林。這樣，問題就轉(zhuǎn)化為在一個(gè)M個(gè)結(jié)點(diǎn)的森林中選取N個(gè)結(jié)點(diǎn)，使得所選結(jié)點(diǎn)的權(quán)值之和最大。同時(shí)滿足每次選取時(shí)，若選兒子結(jié)點(diǎn)，必選根結(jié)點(diǎn)的條件。,.,樣例分析,如圖1，為兩棵樹，我們可以虛擬一個(gè)結(jié)點(diǎn)，將這些樹連接起來，那么森林就轉(zhuǎn)會(huì)為了1棵樹，選取結(jié)點(diǎn)時(shí)，從每個(gè)兒子出發(fā)進(jìn)行選取。顯然選M=4時(shí)，選3，2，7，6幾門課程最優(yōu)。,.,轉(zhuǎn)化為二叉樹,如果該問題僅僅只是一棵二叉樹，我們對(duì)兒子的分配就僅僅只需考慮左右孩子即可，問題就變得很簡(jiǎn)單了。因此我們?cè)囍鴮⒃搯栴}轉(zhuǎn)化為二叉樹求解。圖2就是對(duì)圖1采用孩子兄弟表示法所得到的二叉樹,.,動(dòng)態(tài)規(guī)劃,仔細(xì)理解左右孩子的意義（如右圖）：左孩子：原根結(jié)點(diǎn)的孩子右孩子：原根結(jié)點(diǎn)的兄弟也就是說，左孩子分配選課資源時(shí)，根結(jié)點(diǎn)必須要選修，而與右孩子無關(guān)。因此，我們?cè)O(shè)f(i,j)表示以i為根結(jié)點(diǎn)的二叉樹分配j門課程的所獲得的最大學(xué)分，則有，0=knm;scoren+1=0;brothern+1=0;/輸入數(shù)據(jù)并轉(zhuǎn)化為左兒子右兄弟表示法for(inti=1;iab;if(a=0)a=n+1;scorei=b;brotheri=childa;childa=i;,.,voiddfs(inti,intj)if(visitedij)return;visitedij=1;if(i=0|j=0)return;dfs(brotheri,j);/如果不選i，則轉(zhuǎn)移到狀態(tài)(brotheri,j)fij=fbrotherij;for(intk=0;kfij)fij=fbrotherik+fchildij-k-1+scorei;,.,軟件安裝（2010河南省選）,有N個(gè)軟件，對(duì)于一個(gè)軟件i，它要占用Wi的磁盤空間，它的價(jià)值為Vi。我們希望從中選擇一些軟件安裝到一臺(tái)磁盤容量為M計(jì)算機(jī)上，使得這些軟件的價(jià)值盡可能大（即Vi的和最大）。軟件之間存在依賴關(guān)系，即軟件i只有在安裝了軟件j（包括軟件j的直接或間接依賴）的情況下才能正確工作（軟件i依賴軟件j)。幸運(yùn)的是，一個(gè)軟件最多依賴另外一個(gè)軟件。如果一個(gè)軟件不能正常工作，那么它能夠發(fā)揮的作用為0。我們現(xiàn)在知道了軟件之間的依賴關(guān)系：軟件i依賴軟件Di。一個(gè)軟件只能被安裝一次，如果一個(gè)軟件沒有依賴則Di=0，這時(shí)只要這個(gè)軟件安裝了，它就能正常工作?，F(xiàn)在請(qǐng)你設(shè)計(jì)出一種方案，安裝價(jià)值盡量大的軟件。,.,分析,由于軟件存在先后約束關(guān)系，因此簡(jiǎn)單按軟件先后順序進(jìn)行動(dòng)態(tài)規(guī)劃，會(huì)不符合無后效應(yīng)原理，因此我們需要在進(jìn)行動(dòng)態(tài)規(guī)劃前進(jìn)行預(yù)處理。若安裝軟件i必須先安裝j,則從i向j連一條有向弧，則軟件的約束關(guān)系就構(gòu)成了一個(gè)有向圖。如下圖：可以看出如果有k個(gè)制約關(guān)系，則有k條邊，中間會(huì)存在環(huán),.,分析,處理環(huán)：由于環(huán)為互為前提，要選擇環(huán)中的一個(gè)必須都進(jìn)行選擇，因此可以將環(huán)縮成一個(gè)點(diǎn)，這個(gè)點(diǎn)為權(quán)值和價(jià)值為其他點(diǎn)的和。孤立點(diǎn)沒有與其他點(diǎn)也沒有任何關(guān)系，可以不管。如果把每個(gè)連通分量看成一棵樹，則圖變成了為一個(gè)森林，圖2。,.,樹型動(dòng)態(tài)規(guī)劃,顯然這個(gè)森林可以采用樹型動(dòng)態(tài)規(guī)劃，先將它兒叉樹。設(shè)f(i,j)表示以i為根結(jié)點(diǎn)的二叉樹分配j資源的最大價(jià)值,.,警衛(wèi)安排,一個(gè)有N個(gè)區(qū)域的樹結(jié)構(gòu)上需要安排若干個(gè)警衛(wèi)；每個(gè)區(qū)域安排警衛(wèi)所需要的費(fèi)用是不同的；每個(gè)區(qū)域的警衛(wèi)都可以望見其相鄰的區(qū)域，只要一個(gè)區(qū)域被一個(gè)警衛(wèi)望見或者是安排有警衛(wèi)，這個(gè)區(qū)域就是安全的；任務(wù)：在確保所有區(qū)域都是安全的情況下，找到安排警衛(wèi)的最小費(fèi)用；0n=720；,.,分析樣例該圖有6個(gè)區(qū)域如圖1，安排情況如圖2，紅色點(diǎn)為安排了警衛(wèi)。2號(hào)警衛(wèi)可以觀察1，2，5，6；3號(hào)警衛(wèi)可以觀察1，3；4號(hào)警衛(wèi)可以觀察1，4；費(fèi)用：16+5+4=25,.,分析,對(duì)于每個(gè)點(diǎn)i，都有3種狀態(tài)分別為：要么在父親結(jié)點(diǎn)安排警衛(wèi)，即被父親看到要么在兒子結(jié)點(diǎn)安排警衛(wèi)，即被兒子看到要么安排警衛(wèi)對(duì)于ii被父親看到，這時(shí)i沒有安排警衛(wèi)，i的兒子要么安排警衛(wèi)，要么被它的后代看到。i被兒子看到，即i的某個(gè)兒子安排了警衛(wèi)，其他兒子需要安排警衛(wèi)或者被它的后代看到。i安排了警衛(wèi)，i的兒子可能還需要安排警衛(wèi)，這樣可能有更便易的方式照顧到它的后代；所以i的兒子結(jié)點(diǎn)被i看到，可能安排警衛(wèi)，可能被它的后代看到。,.,.,動(dòng)態(tài)規(guī)劃,設(shè)f(i,0)表示i結(jié)點(diǎn)被父親看到；f(i,1)表示i被它的兒子看到；f(i,2)表示在i安排警衛(wèi)；則狀態(tài)轉(zhuǎn)移方程為：時(shí)間復(fù)雜度O(N2),.,procedurework(now:longint);vari,j,sum,tmp:longint;beginfori:=1totnowdowork(wnow,i);/對(duì)每個(gè)兒子進(jìn)行處理fnow,0:=0;/以下處理now被父親看到fori:=1totnowdoinc(fnow,0,fwnow,i,1);/now的兒子被兒子看到sum:=0;/以下處理在now被兒子看到的fori:=1totnowdo/now的兒子被兒子看到或者或安排警衛(wèi)；inc(sum,min(fwnow,i,1,fwnow,i,2);fnow,1:=maxlongint;fori:=1totnowdo/枚舉哪個(gè)兒子放警衛(wèi)begintmp:=sum-min(fwnow,i,1,fwnow,i,2)+fwnow,i,2;fnow,1:=min(fnow,1,tmp);end;fnow,2:=cnow;/以下處理在now放置警衛(wèi)fori:=1totnowdoInc(fnow,2,min(min(fwnow,i,0,fwnow,i,1),fwnow,i,2);fnow,1:=min(fnow,1,fnow,2);1包含了2狀態(tài)，取優(yōu)值end;,.,總結(jié),樹型動(dòng)態(tài)規(guī)劃有一個(gè)共性，那就是它的基本模型都是一棵樹或者森林，為了考慮方便，一般情況下都將這個(gè)樹或森林轉(zhuǎn)化為二叉樹，如下圖，