《區(qū)間類型動態(tài)規(guī)劃》ppt課件(文件)
【正文】 ??????jijid i s tjifiiiid i s tjifjif跳到停在跳到停在,],[)1,1(1,],1,[)0,1(m i n)0,(?????????ijid i s tjifjjjd i s tjifjif，跳到停在，跳到停在j],[)0,1,(1j],1,[)1,1,(m i n)1,(主程序 for i:=1 to n do for j:=n downto i+1 do begin update(f[i+1,j,0],f[i,j,0]+d[i,i+1])。 // 停在 j,跳到 j1 end。 ? 均方差 ： ? 算術平均值 ： 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ù)。 ? 先預處理從左上角 (1,1)到右下角 (i,j)的棋盤和時間復雜度為 O(m2)，因此轉移為 O(1),總時間復雜度為O(nm5)。 ? 設前 i到 j的最優(yōu)值，枚舉剖分（合并）點，將 (i,j)分成左右兩區(qū)間，分別求左右兩邊最優(yōu)值，如下圖。解決方法是對整個問題設最優(yōu)值，枚舉合并點，將問題分解成為左右兩個部分，最后將左右兩個部分的最優(yōu)值進行合并得到原問題的最優(yōu)值。 ? 因此，我們需要求出各棋盤分割后的每個棋盤各數(shù)平方和的最小值，設為 w，那么 ? 答案為： 2122 1 xxnnii ?? ???2/ xnwans ??棋盤切割后的四種情況 動態(tài)規(guī)劃 ? 設 F(i,x1,y1,x2,y2)表示以 [x1,y1][x2,y2]為四邊形對角線的棋盤切割成 k塊的各塊數(shù)值總平方和的最小值，則有： ? 1=X1,x2,x3,x4=8,1=i=n。 (每次切割都只能沿著棋盤格子的邊進行 ) 允許的分割方案 不允許的分割方案 任務： 棋盤上每一格有一個分值，一塊矩形棋盤的 總分 為其所含各格分值之和。 // 停在 i,跳到 j update(f[i,j1,0],f[i,j,1]+d[i,j])。狀態(tài)轉移方程為： ? 狀態(tài)總數(shù)為 n2，狀態(tài)轉移的復雜度為 O(1)，總的時間復雜度為 O(n2)。 – 如果青蛙跳到了 n號結點，則問題轉化為：從 n出發(fā)，遍歷 2..n一次僅一次的最短距離。 ? 上圖中圖 2的路徑比圖 1要短。fmax(i,j) 表示從點 i開始，到但 j為止進行刪邊操作所能得到的最大值， fmin(i,j) 表示最小值。以前的方程還適不適用呢？ ? 這個例子的最優(yōu)解應該是 （ 3+2） *（ 10） *（ 5） =250， 然而如果沿用以前的方程 ， 得出的解將是 （（ 10）*
教學課件相關推薦
鄂ICP備17016276號-1