區(qū)間類型動(dòng)態(tài)規(guī)劃ppt課件-文庫(kù)吧資料
2025-05-12 12:39本頁(yè)面
【正文】 ? 有一只小青蛙恰好站在 1號(hào)荷葉的點(diǎn) ? 小青蛙可以從一片荷葉上跳到另外任意一片荷葉上 ? 給出 N個(gè)點(diǎn)的坐標(biāo) ? 求小青蛙想通過最短的路程遍歷所有的荷葉一次且僅一次的最短路徑。fmax(i,j) 表示從點(diǎn) i開始，到但 j為止進(jìn)行刪邊操作所能得到的最大值， fmin(i,j) 表示最小值。我們從前的方程，只是盡量使得局部解最大，而從來(lái)沒有想過負(fù)數(shù)的積為正數(shù)這個(gè)問題。以前的方程還適不適用呢？ ? 這個(gè)例子的最優(yōu)解應(yīng)該是 （ 3+2） *（ 10） *（ 5） =250， 然而如果沿用以前的方程 ， 得出的解將是 （（ 10）*3+2） *（ 5） =125。 7 425+*1234+ *樣例 分析 分析 ? 我們先枚舉第一次刪掉的邊，然后再對(duì)每種狀態(tài)進(jìn)行動(dòng)態(tài)規(guī)劃求最大值 。 第一步 ， 一條邊被拿走；隨后各步包括如下： ? 選擇一條邊 E和連接著 E的兩個(gè)頂點(diǎn) V1和 V2； ? 得到一個(gè)新的頂點(diǎn) ， 標(biāo)記為 V1與 V2通過邊 E上的運(yùn)算符運(yùn)算的結(jié)果 。 每個(gè)頂點(diǎn)有一個(gè)整數(shù)標(biāo)記 ，每條邊上有一個(gè) “ +”號(hào)或 “ *” 號(hào) 。 多邊形（ IOI98） ? 多角形是一個(gè)單人玩的游戲 ， 開始時(shí)有一個(gè) N個(gè)頂點(diǎn)的多邊形 。 凸多邊形的三角剖分 ? 給定由 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è)凸多邊形。 ? 設(shè)鏈中的第 i顆珠子頭尾標(biāo)記為 (Si1與 Si)。 ? 分析樣例： N=4， 4顆珠子的頭標(biāo)記與尾標(biāo)記依次為 (2， 3) (3， 5) (5， 10) (10， 2)。如果前一顆能量珠的頭標(biāo)記為 m，尾標(biāo)記為 r，后一顆能量珠的頭標(biāo)記為 r，尾標(biāo)記為 n，則聚合后釋放的能量為 m r n（ Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為 m，尾標(biāo)記為 n。 ? 能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。 Fmax(i,j)表示將從第 i堆石子合并到第 j堆石子的最大的得分 Fmin(i,j)表示將從第 i堆石子合并到第 j堆石子的最小的得分 同理， ? Fmax[i,i] = 0， Fmin[i,i] = 0 ? 時(shí)間復(fù)雜度為 O(n2) ],[)}1,m ax (),1m ax ({),m ax ( m a x jitjiFjiFjiF ????],[)}1,m i n (),1m i n ({),m i n ( m i n jitjiFjiFjiF ????能量項(xiàng)鏈 ? 在 Mars星球上，每個(gè) Mars人都隨身佩帶著一串能量項(xiàng)鏈。 情況 2： t[i, p]t[p+1,j] 與情況 1是對(duì)稱。如下圖； 情況 1： t*i, p+≤t*p+1,j+ 合并方案 1： { [ (i… q) (q+1...p) ] (p+1… j) } ，它的得分 : F1=Fmax(i, q)+Fmax(q+1,p])+Fmax(p+1,j)+t[i, j]+t[i, p] 合并方案 2: { (i… q) [ (q+1...p) (p+1… j) ] }，它的得分： F2 = Fmax [i, q]+Fmax [q+1,p]+Fmax [p+1,j]+t[i, j]+t[q+1,j] 由于 qp，所以 t*i, p+≤t*p+1,j+t*q+1,j+，所以 F1F2。 ? 時(shí)間復(fù)雜度為 O(8n3),如下圖：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1