區(qū)間類型動態(tài)規(guī)劃ppt課件-資料下載頁
2025-05-06 12:39本頁面
【正文】 ,0],f[i,j,1]+d[i,j])。 // 停在 j,跳到 i update(f[i,j1,1],f[i,j,1]+d[j1,j])。 // 停在 j,跳到 j1 end。 棋盤分割 ? 將一個８ ８的棋盤進行如下分割：將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了 (n1)次后，連同最后剩下的矩形棋盤共有n塊矩形棋盤。 (每次切割都只能沿著棋盤格子的邊進行 ) 允許的分割方案 不允許的分割方案 任務(wù)： 棋盤上每一格有一個分值，一塊矩形棋盤的 總分 為其所含各格分值之和?，F(xiàn)在需要把棋盤按上述規(guī)則分割成 n塊矩形棋盤，并使各矩形棋盤總分的 均方差 最小。 ? 均方差 ： ? 算術(shù)平均值 ： nxxnii21)(?????nxxnii??? 1樣例 輸入 3 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 3 輸出 均方差公式化簡 2122122112211222122122112121)2()2()()(xxnxxnxxnxxnxnxxxxnnxxxxnxxnxxniiniiniiniiniiniiniiiniinii????????????? ?????????????????????????分析 ? 由化簡后的均方差公式： ? 可知，均方差的平方為每格數(shù)的平方和除以 n，然后減去平均值的平方，而后者是一個已知數(shù)。 ? 因此，在棋盤切割的各種方案中，只需使得每個棋盤內(nèi)各數(shù)值的平方和最小即可。 ? 因此，我們需要求出各棋盤分割后的每個棋盤各數(shù)平方和的最小值，設(shè)為 w，那么 ? 答案為： 2122 1 xxnnii ?? ???2/ xnwans ??棋盤切割后的四種情況 動態(tài)規(guī)劃 ? 設(shè) F(i,x1,y1,x2,y2)表示以 [x1,y1][x2,y2]為四邊形對角線的棋盤切割成 k塊的各塊數(shù)值總平方和的最小值，則有： ? 1=X1,x2,x3,x4=8,1=i=n。 ? 設(shè)棋盤邊長為 m,則狀態(tài)數(shù)為 nm4 ,決策數(shù)最多 m。 ? 先預(yù)處理從左上角 (1,1)到右下角 (i,j)的棋盤和時間復(fù)雜度為 O(m2)，因此轉(zhuǎn)移為 O(1),總時間復(fù)雜度為O(nm5)。 ????????????????????右面不動豎切左面不動豎切下面不動橫切上面不動橫切,],[],1[),1(,],[],[),1,1(,],1,[],[),1(,],][,[)1,1(m i n),(2212112112211112112111112211yxybDybyxifybyxDyxybifaxyxDaxyxifaxyxDaxyxifyxyxif總結(jié) ? 該類問題的基本特征是能將問題分解成為兩兩合并的形式。解決方法是對整個問題設(shè)最優(yōu)值，枚舉合并點，將問題分解成為左右兩個部分，最后將左右兩個部分的最優(yōu)值進行合并得到原問題的最優(yōu)值。有點類似分治的解題思想。 ? 設(shè)前 i到 j的最優(yōu)值，枚舉剖分（合并）點，將 (i,j)分成左右兩區(qū)間，分別求左右兩邊最優(yōu)值，如下圖。 ? 狀態(tài)轉(zhuǎn)移方程的一般形式如下： F(i,j)=Max{F(i,k)+F(k+1,j)+決策， k為劃分點
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1