區(qū)間類型動(dòng)態(tài)規(guī)劃ppt課件-閱讀頁(yè)
2025-05-21 12:39本頁(yè)面
【正文】 ),m ax (jkfkijkfkijkfkijkfkijif????????????),1m a x (*),(f m a x),1m a x (*),(f m i n),1m i n (*),(f m a x),1m i n (*),(f m i n),m i n (jkfkijkfkijkfkijkfkijif當(dāng) OP=‘*’ 完美解決 ? 初始值 Fmax(i,i)=num(i) Fmin(i,i)=num(i) ? 1=i=k=j=n ? 空間復(fù)雜度 :O(n2) ? 時(shí)間復(fù)雜度 :先要枚舉每一條邊為 O(n)，然后動(dòng)態(tài)規(guī)劃為 O(n3 )， 因此總為 O(n4)。 ? 分析一個(gè)簡(jiǎn)單例子 ? 最優(yōu)遍歷方法為： 1,2,3,4,5,10,9,8,7,6 (圖中紅線 ) ? D=d(1,5)+d(5,10)+d(6,10) =2*(82+42)1/2+8 = 分析 ? 性質(zhì)：青蛙遍歷的路徑不會(huì)相交。 ? 證明：圖 1: D1=d(1,3)+d(2,3)+d(2,4) 圖 2: D2=d(1,2)+d(2,3)+d(3,4) 要證明 D1D2,只要證明 d(1,3) +d(2,4)d(1,2)+d(3,4) 連接兩邊，見圖 3，由三角形的三邊關(guān)系定理即可證明。 – 如果青蛙跳到了 2號(hào)結(jié)點(diǎn)，則問(wèn)題轉(zhuǎn)化為：從 2出發(fā)，遍歷 2..n一次僅一次的最短距離。 ? 這實(shí)際上是遞歸的思維，把問(wèn)題轉(zhuǎn)化為了本質(zhì)相同但規(guī)模更小的子問(wèn)題 ,如下圖。 f(s, L,1)表示從 s+L1出發(fā)，遍歷 s..s+L1一次且僅一次的最短距離。 ?????????????????1],1,[)1,1,11(1],1,[)0,1,1(m i n)0,(LsLssd i s tLsfsssd i s tLsfLsf跳到跳到????????????????2],2,1[)1,1,(],1,[)0,1,(m i n)1,(LsLsLsd i s tLsfsLssd i s tLsfLsf跳到跳到動(dòng)態(tài)規(guī)劃 (2) ? F(i,j,0)表示還有 i~j號(hào)點(diǎn)沒(méi)訪問(wèn) ,且青蛙停在 i的最小值 F(i,j,1)表示還有 i~j號(hào)點(diǎn)沒(méi)訪問(wèn) ,且青蛙停在 j的最小值 ? 狀態(tài)總數(shù)為 n2，狀態(tài)轉(zhuǎn)移的復(fù)雜度為 O(1)，總的時(shí)間復(fù)雜度為 O(n2)。 // 停在 i,跳到 i+1 update(f[i+1,j,1],f[i,j,0]+d[i,j])。 // 停在 j,跳到 i update(f[i,j1,1],f[i,j,1]+d[j1,j])。 棋盤分割 ? 將一個(gè)８ ８的棋盤進(jìn)行如下分割：將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了 (n1)次后，連同最后剩下的矩形棋盤共有n塊矩形棋盤?，F(xiàn)在需要把棋盤按上述規(guī)則分割成 n塊矩形棋盤，并使各矩形棋盤總分的 均方差 最小。 ? 因此，在棋盤切割的各種方案中，只需使得每個(gè)棋盤內(nèi)各數(shù)值的平方和最小即可。 ? 設(shè)棋盤邊長(zhǎng)為 m,則狀態(tài)數(shù)為 nm4 ,決策數(shù)最多 m。 ????????????????????右面不動(dòng)豎切左面不動(dòng)豎切下面不動(dòng)橫切上面不動(dòng)橫切,],[],1[),1(,],[],[),1,1(,],1,[],[),1(,],][,[)1,1(m i n),(2212112112211112112111112211yxybDybyxifybyxDyxybifaxyxDaxyxifaxyxDaxyxifyxyxif總結(jié) ? 該類問(wèn)題的基本特征是能將問(wèn)題分解成為兩兩合并的形式。有點(diǎn)類似分治的解題思想。 ? 狀態(tài)轉(zhuǎn)移方程的一般形式如下： F(i,j)=Max{F(i,k)+F(k+1,j)+決策， k為劃分點(diǎn)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1