區(qū)間類型動態(tài)規(guī)劃ppt課件-在線瀏覽
2025-06-23 12:39本頁面
【正文】 第五次 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 顯然，貪心法是錯誤的。如下圖： 動態(tài)規(guī)劃 ? 設(shè) t[i,j]表示從第 i堆到第 j堆石子數(shù)總和。 ? 這樣顯然很高，其實我們可以將這條鏈延長 2倍，擴展成2n1堆，其中第 1堆與 n+1堆完全相同，第 i堆與 n+i堆完全相同，這樣我們只要對這 2n堆動態(tài)規(guī)劃后，枚舉f(1,n),f(2,n+1),…,f(n,2n 1)取最優(yōu)值即可即可。設(shè)在i,p之間存在一種斷開方案 q。 這說明方案 2的合并方案比方案 1好，因此這種情況下應(yīng)盡可能靠左邊決策。（證明略） 狀態(tài)轉(zhuǎn)移方程 ? 設(shè) t[i,j]表示從第 i堆到第 j堆石子數(shù)總和。 ? 在項鏈上有 N顆能量珠。 ? 對于相鄰的兩顆珠子，前一顆珠子的尾標記一定等于后一顆珠子的頭標記。 ? 顯然，對于一串項鏈不同的聚合順序得到的總能量是不同的，請你設(shè)計一個聚合順序，使一串項鏈釋放出的總能量最大。 ? 我們用記號 ⊕ 表示兩顆珠子的聚合操作，釋放總能量： ((4⊕ 1)⊕ 2)⊕ 3） =10*2*3+10*3*5+10*5*10=710 動態(tài)規(guī)劃 ? 該題與石子合并完全類似。 ? 令 F(i,j)表示從第 i顆珠子一直合并到第 j顆珠子所能產(chǎn)生的最大能量，則有： F(i,j)=Max{F(i,k)+F(k+1,j)+Si1*Sk*Sj, i=kj} ? 邊界條件： F(i,i)=0 ? 1=ikj=n ? 至于圈的處理，與石子合并方法完全相同，時間復(fù)雜度 O(8n3) 。 ? 設(shè) f(i,j)表示 i~j這一段連續(xù)頂點的多邊形劃分后最小乘積 ? 枚舉點 k， i、 j和 k相連成基本三角形，并把原多邊形劃分成兩個子多邊形，則有 ? f(i,j)=min{f(i,k)+f(k,j)+a[i]*a[j]*a[k]} ? 1=ikj=n ? 時間復(fù)雜度 O(n3) 討論 ?為什么可以不考慮這種情況？ ? 可以看出圖 1和圖 2是等價的，也就是說如果存在圖 1的剖分方案，則可以轉(zhuǎn)化成圖 2的剖分方案，因此可以不考慮圖 1的這種情形。 如圖 ， 這里 N=4。邊從 1編號到 N。 ? 最后 ， 游戲中沒有邊 ， 游戲的得分為僅剩余的一個頂點的值 。 ? 用 f(i,j)表示從點 i到點 j進行刪邊操作所能得到的最大值， num(i)表示第 i個頂點上的數(shù)，若為加法，那么： )(),i()),(),((m a x),(11in u mifkikjfikfjifik????? ???進一步分析 ? 最后，我們允許頂點上出現(xiàn)負數(shù)。 為什么 ？ ? 我們發(fā)現(xiàn)，兩個負數(shù)的積為正數(shù)；這兩個負數(shù)越小，它們的積越大。 10 3 2 5 * * 圖六 + 分析 ? 對于加法，兩個最優(yōu)相加肯定最優(yōu)，而對于乘法 ? 求最大值： – 正數(shù) 正數(shù)，如果兩個都是最大值，則結(jié)果最大 – 正數(shù) 負數(shù)，正數(shù)最小，負數(shù)最大，則結(jié)果最大 – 負數(shù) 負數(shù)，如果兩個都是最小值，則結(jié)果最大 ? 求最小值： – 正數(shù) 正數(shù)，如果兩個都是最小值，則結(jié)果最小 – 正數(shù) 負數(shù)，正數(shù)最大，負數(shù)最小，則結(jié)果最小 – 負數(shù) 負數(shù)，如果兩個都是最大值，則結(jié)果最小 最終？ ? 我們引入函數(shù) fmin和 fmax來解決這個問題。 當(dāng) OP=‘+’ Fmax(i,j)=max{fmax(i,k)+fmax(k+1,j)} Fmin(i,j)=min{fmin(i,k)+fmin(k+1,j)} ????????????),1m i n (*),(f m i n),1m ax (*),(f m i n),1m i n (*),(f m ax),1m ax (*),(f m ax
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1