數(shù)塔問(wèn)題PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 數(shù)塔問(wèn)題數(shù)塔問(wèn)題 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 n是否滿(mǎn)足貪婪選擇性質(zhì)？ n是否滿(mǎn)足最優(yōu)子結(jié)構(gòu)性質(zhì)？ 第1頁(yè)/共17頁(yè) 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 n重復(fù)工作 ： 循環(huán)、遞歸 。 n如何循環(huán) ？ n遞歸如何 ？ q使問(wèn)題向邊界條件轉(zhuǎn)化的規(guī)則(遞歸定 義)。 q遞歸邊界條件； 第2頁(yè)/共17頁(yè) 算法算法1 int a100100; /下三角形存放數(shù)據(jù)下三角形存放數(shù)據(jù) int max(int i, int j, int n) /遞歸函數(shù)遞歸函數(shù) int left,right; if (i=n)|(j

2、=n) /到達(dá)邊緣到達(dá)邊緣 return aij; left=max(i+1,j,n); /左邊左邊 right=max(i+1,j+1,n); /右邊右邊 return (leftright)? (left+aij) : (right+aij); max(1,1,n ) max(2,1,n) max(2,2,n) max(3,1,n) max(3,2,n) 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 重疊子問(wèn)題：計(jì)算了重疊子問(wèn)題：計(jì)算了 兩次兩次18的最大路徑。的最大路徑。 第3頁(yè)/共17頁(yè) 9 1215 1068 21895 19710416 階段階段5 階段

3、階段4 階段階段3 階段階段2 (21)(28)(19 ) (21 ) (38)(34)(29) (50)(49) (59) 決策決策 決策決策 決策決策 決策決策 階段階段1 59 50 49 38 34 29 21 28 19 21 19 7 10 4 16 取第取第i行第行第j個(gè)個(gè) 數(shù)，一般有數(shù)，一般有 兩種方案。兩種方案。 第4頁(yè)/共17頁(yè) 9 1215 1068 21895 19710416 (33)(49)(41 ) (37 ) (31)(30)(32) (21)(24) (52)(56)(59)(45)(53) 決策決策 決策決策 決策決策 決策決策 階段階段1 階段階段2 階段

4、階段3 階段階段4 階段階段5 第5頁(yè)/共17頁(yè) n一般當(dāng)初始狀態(tài)唯一給定時(shí)可用逆序解法； n如需比較到達(dá)不同終點(diǎn)狀態(tài)的各個(gè)路徑及最 大結(jié)果時(shí)，使用順序法比較簡(jiǎn)便； n如需知道塔中每一點(diǎn)到最下層的最大值和路 徑時(shí)，使用逆序法比較簡(jiǎn)便。 第6頁(yè)/共17頁(yè) n動(dòng)態(tài)規(guī)劃過(guò)程存儲(chǔ) q必須用二維數(shù)組d 存儲(chǔ)各階段的決策結(jié)果。二 維數(shù)組d的存儲(chǔ)內(nèi)容如下： qdnj=datanj，其中j=1,2,n； qdij=max(di+1j，di+1j+1)+dataij，其中 i=n-1,n-2,1，j=1,2,i； 逆序法逆序法 59 50 49 38 34 29 21 28 19 21 19 7 10 4 16

5、 n最后d11存儲(chǔ)的就是問(wèn)題的最大值。 n可以通過(guò)分析d，得到路徑。 第7頁(yè)/共17頁(yè) 數(shù)組數(shù)組d 59 50 49 38 34 29 21 28 19 21 19 7 10 4 16 數(shù)組數(shù)組data 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 第8頁(yè)/共17頁(yè) for( i=1 ;i=n;i+) for (j=1;j=1;i-) for (j=1 ;j= i ;j+) if (ai+1j2ai+1j+12) aij2=aij2+ai+1j2; aij3=0; else aij2=aij2+ai+1j+12; aij3=1; print(max=,a112);

6、for( i=1 ;i); j=j+aij3; print (anj1); 第9頁(yè)/共17頁(yè) q由于動(dòng)態(tài)規(guī)劃的問(wèn)題有重疊子問(wèn)題的特點(diǎn)，為了 減少重復(fù)計(jì)算，對(duì)每一個(gè)子問(wèn)題只解一次，將其 不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。 n動(dòng)態(tài)規(guī)劃=貪婪策略+遞推(降階)+存儲(chǔ)遞推結(jié) 果 第10頁(yè)/共17頁(yè) 第11頁(yè)/共17頁(yè) 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 n狀態(tài)：dij，即取第i行，第j個(gè)數(shù)能夠 達(dá)到的最大值； n決策：取第i行第j個(gè)數(shù)，則可以有兩種方案：取第i-1行第 j-1個(gè)數(shù)或取第i-1行第j個(gè)數(shù)后再取第i行第j個(gè)數(shù)； n狀態(tài)轉(zhuǎn)移方程： qdij = m

7、ax (di+1j，di+1j+1) + dataij； q表示取第i行第j個(gè)數(shù)所能達(dá)到的最大和； 第12頁(yè)/共17頁(yè) n算法1改進(jìn)：也會(huì)存儲(chǔ)中間計(jì)算結(jié)果。 該動(dòng)態(tài)規(guī)劃算法遞歸實(shí)現(xiàn)該動(dòng)態(tài)規(guī)劃算法遞歸實(shí)現(xiàn) 記憶化搜索記憶化搜索。 第13頁(yè)/共17頁(yè) n能夠體現(xiàn)動(dòng)態(tài)規(guī)劃優(yōu)點(diǎn)的性質(zhì)： q子問(wèn)題重疊性質(zhì)； q動(dòng)態(tài)規(guī)劃用空間換取時(shí)間，在有大量重疊子問(wèn) 題的時(shí)候其優(yōu)勢(shì)才能充分體現(xiàn)出來(lái)。 第14頁(yè)/共17頁(yè) 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 n無(wú)后效性 q如，計(jì)算到12的最大和只要考慮到10的最大和與 到6的最大和哪個(gè)更大，而不要考慮到10的最大 和或者到6的最大和具體是哪幾個(gè)數(shù)構(gòu)成的。 第15頁(yè)/共17頁(yè) n實(shí)際應(yīng)用當(dāng)中的簡(jiǎn)化步驟：