《算法設(shè)計(jì)與分析》第07章-文庫(kù)吧
2025-07-20 10:40 本頁(yè)面
【正文】 int i,j,k。 d= new T*[n]。path=new int *[n]。 for(i=0。in。i++){ d[i]=new T [n]。path[i]=new int[n]。 for (j=0。jn。j++){ d[i][j]=a[i][j]。 if (i!=j amp。amp。 w[i][j]INFTY) path[i][j]=i。 else path[i][j]=1。 } } for (k=0。kn。k++) for (i=0。in。i++) for (j=0。jn。j++) if (d[i][k]+d[k][j] d[i][j] ){ d[i][j]=d[i][k]+d[k][j]。 path[i][j]=path[k][j]。 } }弗洛伊德算法的時(shí)間復(fù)雜度為 O(n3) 算法正確性 定理 7－ 1 弗洛伊德算法得到的 d[i][j]， 0?i,j?n1是從 i到 j的最短路徑 。 矩陣連乘 問(wèn)題描述 ? 給定 n個(gè)矩陣 {A0,A1,… ,An－ 1}， 其中 Ai， i=0,… ,n1的維數(shù)為 pi?pi+1， 并且 Ai與 Ai+1是可乘的 。 考察這 n個(gè)矩陣的連乘積 A0A1… An?1， 由于矩陣乘法滿足結(jié)合律 ，所以計(jì)算矩陣的連乘可有許多不同的計(jì)算次序 。 矩陣連乘問(wèn)題是確定計(jì)算矩陣連乘積的計(jì)算次序 ， 使得按照這一次序計(jì)算矩陣連乘積 ， 需要的 “ 數(shù)乘 ” 次數(shù)最少 。 完全加括號(hào) 的矩陣連乘積可遞歸地定義為： 單個(gè)矩陣是完全加括號(hào)的； 矩陣連乘積 A是完全加括號(hào)的 ， 則 A可表示為兩個(gè)完全加括號(hào)的矩陣連乘積 B和 C的乘積并加括號(hào) ，即 A=(BC)。 例 7－ 4 4個(gè)矩陣連乘積 ABCD， 設(shè)它們的維數(shù)分別為A:50?10， B:10?40, C:40?30, D:30?5。 動(dòng)態(tài)規(guī)劃法求解 最優(yōu)子結(jié)構(gòu) 矩陣連乘 AiAi+1…A j簡(jiǎn)記為 A[i:j]， i?j。于是矩陣連乘 A0A1…A n1可記作 A{0:n1}。將這一計(jì)算次序在矩陣 Ak和 Ak+1， 0?kn1之間斷開(kāi)，則其相應(yīng)的完全加括號(hào)形式為（（ A0A1…A k）（ Ak+1Ak+2…A n?1））?？上确謩e計(jì)算 A[0:k]和 A[k+1:n1]，然后將兩個(gè)連乘積再相乘得到 A[0:n1]。 矩陣連乘 A[0:n1]的最優(yōu)計(jì)算次序的計(jì)算量等于A[0:k]和 A[k+1:n1]兩者的最優(yōu)計(jì)算次序的計(jì)算量之和 ， 再加上 A[0:k]和 A[k+1:n1]相乘的計(jì)算量 。 如果兩個(gè)矩陣子序列的計(jì)算次序不是最優(yōu)的 ， 則原矩陣的計(jì)算次序也不可能是最優(yōu)的 。 這就是說(shuō) ， 矩陣連乘問(wèn)題的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性 。 ??????????????? ji }ppp]j][1k[m]k][i[m{m i nji 0]j][i[m1j1kijki最優(yōu)解的遞推關(guān)系 先定義一個(gè)二維數(shù)組 m， 用來(lái)保存矩陣連乘時(shí)所需的最少計(jì)算量 。 矩陣連乘算法 ? 【 程序 7－ 3】 矩陣連乘算法 class MatrixChain { public: MatrixChain(int mSize,int *q)。 int MChain()。 int LookupChain()。 void Traceback()。 …… private: void Traceback(int i,int j)。 int LookupChain(int i, int j)。 int *p,**m,**s,n。 }。 int MatrixChain::MChain() { //求 A[0:n1]的最優(yōu)解值 for (int i=0。in。i++) m[i][i]=0。 for (int r=2。 r=n。r++) for (int i=0。i=nr。i++) { int j=i+r1。 m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]。 s[i][j]=i。 for (int k=i+1。kj。k++) { int t=m[i][k] +m[k+1][j]+p[i]*p[k+1]*p[j+1]。 if (tm[i][j]) { m[i][j]=t。s[i][j]=k。 } } } return m[0][n1]。 } void MatrixChain::Traceback(int i,int j) { if(i==j) { cout39。A39。i。return。} if (is[i][j]) cout39。(39。 Traceback(i,s[i][j])。if (is[i][j])cout39。)39。 if(s[i][j]+1j)cout39。(39。 Traceback(s[i][j]+1,j)。if(s[i][j]+1j) cout39。)39。 } void MatrixChain::Traceback() { cout39。(39。 Traceback(0,n1)。cout39。)39。 coutendl。 } 例 7－ 5 6個(gè)矩陣連乘積 A0A1A2A3A4A5， 設(shè)它們的維數(shù)分別為 A:30?35， B:35?15 C:15?5 D:5?10， E:10?20，F(xiàn):20?25。 備忘錄方法 ? 矩陣連乘的備忘錄方法 備忘錄方法為每個(gè)已經(jīng)計(jì)算的子問(wèn)題建立備忘錄，即 保存子問(wèn)題的計(jì)算結(jié)果以備需要時(shí)引用，從而避免了 相同子問(wèn)題的重復(fù)求解。 【 程序 7－ 4】 矩陣連乘的備忘錄方法 int MatrixChain::LookupChain
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1