動(dòng)態(tài)規(guī)劃dynamicprogrammingdp(編輯修改稿)
2025-08-14 12:37 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ,這種乘法的順序可寫(xiě)為 (A*B)*Cq 第二種方式為 A*(B*C)n 盡管這兩種不同的計(jì)算順序所得的結(jié)果相同 ,但所需元素乘法數(shù)卻不同q 第一種方式乘法數(shù)： mp(n+q)q 第二種方式乘法數(shù)： nq(m+p)MPC 示例n 假定 A為 1001矩陣 ,B為 1100矩陣 ,C為 1001矩陣 ,(A*B)*C需乘法數(shù)為1001100＋ 1001001＝ 20220n 而 A*(B*C)所需乘法數(shù)為 11001＋ 10011＝ 200n 長(zhǎng)度 q的矩陣乘法鏈有指數(shù)量級(jí) Ω(2q)的可能的相乘方式n 找一種相乘方式 ,使得元素乘法數(shù)最少M(fèi)PC動(dòng)態(tài)規(guī)劃解n 用 M(i,j)表示鏈 Mi…,Mj(i≤j)的乘積 .假設(shè)優(yōu)化的乘法順序先計(jì)算 M(i,k)和 M(k+1,j),再將二者相乘n 則計(jì)算 M(i,j)的優(yōu)化乘法順序在計(jì)算 M(i,k)和 M(k+1,j)時(shí)也是優(yōu)化的n 考慮 5個(gè)矩陣的乘法鏈 ,其行列數(shù)為 r =(10,5,1,10,2,10),即 M1為 105的矩陣 ,等等q 優(yōu)化的乘法順序?yàn)?(M1M2)((M3M4)M5))=190q 子鏈 M(3,5)=M3M4M5的優(yōu)化乘法順序?yàn)?M3M4)M5),是上述長(zhǎng)度 5的鏈的優(yōu)化解在子鏈上的乘法順序MPC動(dòng)態(tài)規(guī)劃解 (續(xù) )n 設(shè) c(i,j)為計(jì)算 M(i,j)的優(yōu)化乘法數(shù) (優(yōu)化值 ),根據(jù)優(yōu)化原理 ,優(yōu)化值之間滿(mǎn)足 :q c(i,j)=mini≤kj{c(i,k)+c(k+1,j)+rirk+1rj+1}n c(i,j)的性質(zhì)q c(i,i)=0q c(i,i+1)=ri*ri+1*ri+2n 令 kay(i,j)為使 c(i,j)達(dá)到最小值的 k，則q Kay(i,i+1)=in 基本思路q MPC滿(mǎn)足優(yōu)化原理q 用遞歸算法計(jì)算 c(1,q)q 用 kay(i,j)回溯找到優(yōu)化的乘法順序MPC 例 1513設(shè) q = 5和 r =（ 10 , 5 , 1 , 10 , 2 , 10）求解 MPCc(2,5)=min{c(2,2)+c(3,5)+50, c(2,3)+c(4,5)+500, c(2,4)+c(5,5)+100}c(1,5)=min{ c(1,1)+c(2,5)+500， c(1,2)+c(3,5)+100, c(1,3)+c(4,5)+1000, c(1,4)+c(5,5)+200}c(1,5)=190,kay(1,5)=2c(3,5)=min{c(3,3)+c(4,5)+100, c(3,4)+c(5,5)+20} =min{300,40}c(3,5)=40,kay(3,5)=4c(2,4)=min{c(2,2)+c(3,4)+10, c(2,3)+c(4,4)+100} =min{30,150}c(2,4)=30,kay(2,4)=2c(2,5)=90,kay(2,5)=2c(1,3)=150,kay(1,3)=2c(1,4)=90,kay(1,4)=2M(1,5)=M(1,2)M(3,5) M(3,5)=M(3,4)M(5,5)n 在函數(shù) C中 ,r為全局一維數(shù)組，kay是全局二維數(shù)組 .n 函數(shù) C返回 c(ij)之值且置 kay[i][j]=kay (i,j).n 函數(shù) Traceback利用函數(shù) C中已算出的 kay值來(lái)推導(dǎo)出最優(yōu)乘法算法的步驟n 存儲(chǔ) c[i,j]以避免重復(fù)計(jì)算MPC 遞歸算法//檢查 c(i,j) 是否已計(jì)算If c[i][j]0 return c[i][j]。c[i][j]=u。A deep look at the structures of MPCMPC 迭代算法n 函數(shù) c 的動(dòng)態(tài)規(guī)劃遞歸式可用迭代的方法來(lái)求解 .若按 s=2,3,…,q1的順序計(jì)算 c(i,i+s),每個(gè) c 和 kay 僅需計(jì)算一次 .但需很大的存儲(chǔ)空間。MPC 迭代算法 :示例1 2 3 4 51 0 50 150 90 1902 0 50 30 903 0 20 404 0 2005 0設(shè) q = 5和 r =（ 10 , 5 , 1 , 10 , 2 , 10）求解 MPCMPC 迭代程序時(shí)間復(fù)雜度n 復(fù)雜性為 O(q3).q 計(jì)算 C(i,i+s)需 Θ(s)時(shí)間 .q 對(duì) s＝ 2,…q1,要 計(jì)算 qs個(gè) C(i,i+s),時(shí)間復(fù)雜度為 Θ((qs)s).q 所以時(shí)間復(fù)雜度為 Θ(q3)n 計(jì)算出 kay后同樣可用程序 156中的Traceback函數(shù)算出相應(yīng)的最優(yōu)乘法順序最短路徑 (All Pairs Shortest Paths: APSP)n 最短路徑 :假設(shè) G為有向圖 ,其中每條邊都有一個(gè)成本 (cost),圖中每條有向路徑的長(zhǎng)度 (或成本 )定義為該路徑上各邊的成本之和n 對(duì)于每對(duì)頂點(diǎn) (i,j),定義從 i 到 j的所有路徑中 ,具有最小長(zhǎng)度的路徑為從 i到 j的最短路徑n 求每對(duì)點(diǎn)間的最短路n 假定圖上無(wú)負(fù)成本的環(huán)路APSP: 例 1515n 如 圖 154所示。從頂點(diǎn) 1到頂點(diǎn) 3的路徑有1)1,2,5,32)1,4,33)1,2,5,8,6,34)1,4,6,3n 由該圖可知 ,各路徑相應(yīng)的長(zhǎng)度為 10,28,9,27.因而路徑 3)是該圖中頂點(diǎn) 1到頂點(diǎn) 3的最短路徑。APSP: 動(dòng)態(tài)規(guī)劃解n 將節(jié)點(diǎn)按 1到 n編號(hào) .n 定義 c(i,j,k)=i到 j的中間節(jié)點(diǎn)編號(hào)不超過(guò) k的最短路長(zhǎng)度 .q c(i,j,0)=cost(i,j)ifi,j∈ Gelsec(i,j,0)=∞q c(i,i,k)=0forallkq c(i,j,n)是要求的 i到 j的最短路長(zhǎng)度n 我們建立 c(i,j,k)和 c(i,j,k1)之間的遞歸關(guān)系A(chǔ)PSP:遞歸式n 對(duì)于任意 k＞ 0，q c(i,j,k)=min{c(i,j,k1),c(i,k,k1)+c(k,j,k1)}n 性質(zhì)q c(i,k,k1)=c(i,k,k)q c(k,j,k)=c(k,j,k1)n 如果直接用遞歸程序求解上式 ,則計(jì)算 c(i,j,n)的復(fù)雜度極高 .利用迭代方法 .可將計(jì)算 c值的時(shí)間減少到 O(n3).n 迭代算法的偽代碼如圖 155所示。APSP：迭代算法n 令 C(k)代表矩陣(c(i,j,k))i,j=1,…,nn 初始 C(0)=(c(i,j)),即圖的鄰接矩陣 .n 算法迭代計(jì)算 C(k):q 對(duì) k行 k列的元素n C(k)(i,k)=C(k1)(i,k)n C(k)(k,j)=C(k1)(k,j).q 對(duì) k行 k列以外的元素n C(k)(i,j)=max{C(k1)(i,j),C(k1)(i,k)+C(k1)(k,j)}APSP：改進(jìn)的遞歸算法 (1)Kay[i][j]是從 i到 j的最短路徑中編號(hào)最大的節(jié)點(diǎn) ,通過(guò)該節(jié)點(diǎn)可以回溯最短路徑節(jié)點(diǎn)APSP：改進(jìn)的遞歸算法 (2)APSP: 例 1517n 圖 156a給出某圖的長(zhǎng)度矩陣 a， 156b給出由程序 159所計(jì)算出的 c 矩陣， 156c為對(duì)應(yīng)的 kay值。根據(jù) 156c中的 kay 值，可知從 1到 5的最短路徑是從 1到 kay[1][5]=4的最短路徑再加上從4到 5的最短路徑，因?yàn)?kay
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1