區(qū)間類型動(dòng)態(tài)規(guī)劃ppt課件-wenkub
2023-05-21 12:39:04 本頁(yè)面
【正文】 四次 9 6 9得分 15 第五次 15 9得分 24 第六次 24 總分： 62 然而有更好的方案： 第一次 3 4 6 5 4 2得分 7 第二次 7 6 5 4 2得分 13 第三次 13 5 4 2得分 6 第四次 13 5 6得分 11 第五次 13 11得分 24 第六次 24 總分： 61 顯然，貪心法是錯(cuò)誤的。 ? F[i， j]表示把這個(gè)數(shù)前 i位分成 j段得到的最大乘積。但有反例。 ? 特征：能將問題分解成為兩兩合并的形式 ? 求解：對(duì)整個(gè)問題設(shè)最優(yōu)值，枚舉合并點(diǎn)，將問題分解成為左右兩個(gè)部分，最后將左右兩個(gè)部分的最優(yōu)值進(jìn)行合并得到原問題的最優(yōu)值。有點(diǎn)類似分治算法的解題思想。如 191919分成 3段 19*19*19=6859 但 191*91*9=156429，顯然乘積更大。 ? F[i,j]=F[k,j1]*A[k+1,i], ? 1ki=n, j=m ? 時(shí)間復(fù)雜度為 O[mn2] ? 由于有 10000組數(shù)據(jù)，因此估計(jì)時(shí)間復(fù)雜度為10000*203=8*107 ? 至于說輸出，記錄轉(zhuǎn)移的父親就可以了。 分析 ? 假設(shè)只有 2堆石子，顯然只有 1種合并方案 ? 如果有 3堆石子，則有 2種合并方案， ((1,2),3)和 (1,(2,3)) ? 如果有 k堆石子呢？ ? 不管怎么合并，總之最后總會(huì)歸結(jié)為 2堆，如果我們把最后兩堆分開，左邊和右邊無(wú)論怎么合并，都必須滿足最優(yōu)合并方案，整個(gè)問題才能得到最優(yōu)解。 ? 時(shí)間復(fù)雜度為 O(8n3),如下圖： 猜想 ? 合并第 i堆到第 j堆石子的最優(yōu)斷開位置 s[i,j]要么等于 i+1，要么等于 j1，也就是說最優(yōu)合并方案只可能是： { (i) (i+1… j) } 或者 { (i… j1) (j) } 證明 ? 設(shè)合并第 i堆到第 j堆石子的斷開位置 p，且 ipj1。 情況 2： t[i, p]t[p+1,j] 與情況 1是對(duì)稱。 ? 能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。 ? 分析樣例： N=4， 4顆珠子的頭標(biāo)記與尾標(biāo)記依次為 (2， 3) (3， 5) (5， 10) (10， 2)。 凸多邊形的三角剖分 ? 給定由 N頂點(diǎn)組成的凸多邊形 ? 每個(gè)頂點(diǎn)具有權(quán)值 ? 將凸 N邊形剖分成 N2個(gè)三角形 ? 求 N2個(gè)三角形頂點(diǎn)權(quán)值乘積之和最??？ ? 樣例 上述凸五邊形分成△ 123 ， △ 135， △ 345 三角形頂點(diǎn)權(quán)值乘積之和為： 121*122*123+121*123*231+123*245*231= 12214884 分析 ?性質(zhì)：一個(gè)凸多邊形剖分一個(gè)三角形后，可以將凸多邊形剖分成三個(gè)部分： ?一個(gè)三角形 ?二個(gè)凸多邊形（圖 2可以看成另一個(gè)凸多邊形為 0） 動(dòng)態(tài)規(guī)劃 ? 如果我們按順時(shí)針將頂點(diǎn)編號(hào)，則可以相鄰兩個(gè)頂點(diǎn)描述一個(gè)凸多邊形。 每個(gè)頂點(diǎn)有一個(gè)整數(shù)標(biāo)記 ，每條邊上有一個(gè) “ +”號(hào)或 “ *” 號(hào) 。 7 425+*1234+ *樣例 分析 分析 ? 我們先枚舉第一次刪掉的邊，然后再對(duì)每種狀態(tài)進(jìn)行動(dòng)態(tài)規(guī)劃求最大值 。我們從前的方程，只是盡量使得局部解最大，而從來(lái)沒有想過負(fù)數(shù)的積為正數(shù)這個(gè)問題。 青蛙的煩惱 ? 有一個(gè) n片荷葉正好在一凸多邊形頂點(diǎn)上 ? 有一只小青蛙恰好站在 1號(hào)荷葉的點(diǎn) ? 小青蛙可以從一片荷葉上跳到另外任意一片荷葉上 ? 給出 N個(gè)點(diǎn)的坐標(biāo) ? 求小青蛙想通過最短的路程遍歷所有的荷葉一次且僅一次的最短路徑。 分析 ? 結(jié)論：青蛙在 1號(hào)結(jié)點(diǎn)只能跳到 2號(hào)結(jié)點(diǎn)或者 n號(hào)結(jié)點(diǎn)。 動(dòng)態(tài)規(guī)劃 (1) ? f(s,L,0)表示從 s出發(fā)，遍歷 s..s+L1一次且僅一次的最短距離 。 ????
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1