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