區(qū)間類型動(dòng)態(tài)規(guī)劃ppt課件(參考版)
2025-05-09 12:39本頁(yè)面
【正文】 ? 設(shè)前 i到 j的最優(yōu)值，枚舉剖分（合并）點(diǎn)，將 (i,j)分成左右兩區(qū)間，分別求左右兩邊最優(yōu)值，如下圖。解決方法是對(duì)整個(gè)問(wèn)題設(shè)最優(yōu)值，枚舉合并點(diǎn)，將問(wèn)題分解成為左右兩個(gè)部分，最后將左右兩個(gè)部分的最優(yōu)值進(jìn)行合并得到原問(wèn)題的最優(yōu)值。 ? 先預(yù)處理從左上角 (1,1)到右下角 (i,j)的棋盤(pán)和時(shí)間復(fù)雜度為 O(m2)，因此轉(zhuǎn)移為 O(1),總時(shí)間復(fù)雜度為O(nm5)。 ? 因此，我們需要求出各棋盤(pán)分割后的每個(gè)棋盤(pán)各數(shù)平方和的最小值，設(shè)為 w，那么 ? 答案為： 2122 1 xxnnii ?? ???2/ xnwans ??棋盤(pán)切割后的四種情況 動(dòng)態(tài)規(guī)劃 ? 設(shè) F(i,x1,y1,x2,y2)表示以 [x1,y1][x2,y2]為四邊形對(duì)角線的棋盤(pán)切割成 k塊的各塊數(shù)值總平方和的最小值，則有： ? 1=X1,x2,x3,x4=8,1=i=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 輸出 均方差公式化簡(jiǎn) 2122122112211222122122112121)2()2()()(xxnxxnxxnxxnxnxxxxnnxxxxnxxnxxniiniiniiniiniiniiniiiniinii????????????? ?????????????????????????分析 ? 由化簡(jiǎn)后的均方差公式： ? 可知，均方差的平方為每格數(shù)的平方和除以 n，然后減去平均值的平方，而后者是一個(gè)已知數(shù)。 (每次切割都只能沿著棋盤(pán)格子的邊進(jìn)行 ) 允許的分割方案 不允許的分割方案 任務(wù)： 棋盤(pán)上每一格有一個(gè)分值，一塊矩形棋盤(pán)的 總分 為其所含各格分值之和。 // 停在 j,跳到 j1 end。 // 停在 i,跳到 j update(f[i,j1,0],f[i,j,1]+d[i,j])。 ??????????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])。狀態(tài)轉(zhuǎn)移方程為： ? 狀態(tài)總數(shù)為 n2，狀態(tài)轉(zhuǎn)移的復(fù)雜度為 O(1)，總的時(shí)間復(fù)雜度為 O(n2)。 動(dòng)態(tài)規(guī)劃 (1) ? f(s,L,0)表示從 s出發(fā)，遍歷 s..s+L1一次且僅一次的最短距離 。 – 如果青蛙跳到了 n號(hào)結(jié)點(diǎn)，則問(wèn)題轉(zhuǎn)化為：從 n出發(fā)，遍歷 2..n一次僅一次的最短距離。 分析 ? 結(jié)論：青蛙在 1號(hào)結(jié)點(diǎn)只能跳到 2號(hào)結(jié)點(diǎn)或者 n號(hào)結(jié)點(diǎn)。 ? 上圖中圖 2的路徑比圖 1要短。 青蛙的煩惱 ? 有一個(gè) n片荷葉正好在一凸多邊形頂點(diǎn)上
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1