【正文】 19:51:2619:51:2619:513/23/2023 7:51:26 PM 1越是沒有本領(lǐng)的就越加自命不凡。 19:51:2619:51:2619:51Thursday, March 23, 2023 1乍見翻疑夢，相悲各問年。 (2)若 xi≠yj且 zk≠xi， 則 ZK是 Xi1和 Yj的最長公共子序列。考察這 n個矩陣的連乘積 A1A2A3… An ?由于矩陣乘法滿足結(jié)合律，所以計算矩陣的連乘可以有許多不同的計算次序。 ?優(yōu)化原理指：相對于初始決策 1－ 3造成的問題狀態(tài)，（ 3， 5， 7）必須是 3到 7的最短路。i){ x[i]=a[i][j]。 ? 給定 2個序列 X和 Y，當(dāng)另一序列 Z既是 X的子序列又是 Y的子序列時，稱 Z是序列 X和 Y的 公共子序列 。 , March 23, 2023 雨中黃葉樹，燈下白頭人。 2023年 3月 23日星期四 7時 51分 26秒 19:51:2623 March 2023 1空山新雨后，天氣晚來秋。勝人者有力，自勝者強(qiáng)。 2023年 3月 下午 7時 51分 :51March 23, 2023 1行動出成果，工作出財富。因此，最長公共子序列問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) 。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少 ? 為了表示方便 , 以 矩陣 加括號表示矩陣相乘的順序 輸入：向量 P = P0, P1, … , Pn， n個矩陣的行數(shù)、列數(shù) 實例： P = 10, 100, 5, 50 A1: 10 ? 100, A2: 100 ? 5, A3: 5 ? 50, ?完全加括號的矩陣連乘積可遞歸地定義為： （ 1）單個矩陣是完全加括號的； （ 2）矩陣連乘積 A是完全加括號的，則 A可 表示為 2個完全加括號的矩陣連乘積 B和 C 的乘積并加括號，即 A=((B)(C)) ?設(shè)有四個矩陣 A、 B、 C、 D,它們的維數(shù)分別是 1050 ?? 4010 ?? 3040 ??C 530?D )))((( DBCA )))((( DCAB )))((( BCA )))((( CDB )))((( CDAB16000 10500 36000 87500 34500 四種加括號方式 ?窮舉法 ?列舉出所有可能的計算次序，并計算出每一種計算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。 ?例 1: (數(shù)字三角問題 )如圖所示的數(shù)字三角形，從頂部出發(fā)，在每一個節(jié)點可以選擇向左走或者向右走，一直走到底部，要求找到一條路徑，使路徑上的數(shù)字和最大。 求的 a[i][j]之后，就可以求的每個項目分的資源量： j=n。 例 4:(最長公共子序列 ) 概念： ? 若 給定序列 X={x1,x2,…,x m},另 一 序列 Z={z1,z2,…,z k}， 如果存在 一個嚴(yán)格遞增下標(biāo)序列 {i1,i2,…,i k}使得對于所有j=1,2,…,k 有： zj=xij。0,。 :51:2619:51:26March 23, 2023 1意志堅強(qiáng)的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 3月 下午 7時 51分 :51March 23, 2023 1業(yè)余生活要有意義，不要越軌。 , March 23, 2023 很多事情努力了未必有結(jié)果，但是不努力卻什么改變也沒有。其中， Xi={x1,x2,…,x i}； Yj={y1,y2,…,y j}。設(shè)這個計算次序在矩陣 Ak和 Ak+1之間將矩陣鏈斷開， i≤kj，則其相應(yīng)完全加括號方式為 )...)(...( 211 jkkkii AAAAAA ???計算量： A[i:k]的計算量加上 A[k+1:j]的計算量，再加上 A[i:k]和 A[k+1:j]相乘的計算量 ?動態(tài)規(guī)劃 ① 劃分子問題，確定子問題的邊界，有 i和 j確定子問題的邊界 ?設(shè)計算 A[i:j]， 1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為 m[1,n] ?當(dāng) i=j時， A[i:j]=Ai，因此， m[i,i]=0 ?當(dāng) ij時 jki pppjkmkimjim 1],1[],[],[ ?????這里 的維數(shù)為 iA ii pp ??1 ?????????????? jipppjkmkimjijimjki }],1[],[{min0],[1jki 的位置只有 種 可能 k ij??可以遞歸地定義 m[i,j]為： ② 確定優(yōu)化函數(shù)和遞推方程： ③設(shè)立標(biāo)記函數(shù)（決策函數(shù)） 為了 確定加括號的次序 ，定義 s[i,j],記錄 m[i,j]最優(yōu)時k的位置 s[i,j]=k 問題：如何編程實現(xiàn)？ ① 自頂向下遞歸實現(xiàn) ② 自底向上迭代（遞推）實現(xiàn) int RecurMatrixChain(P,i,j) { m[i,j]=? s[i,j]=i for( k=i to j?1 ){ q = RecurMatrixChain(P,i,k) + RecurMatrixChain(P,k+1,j) + pi?1 pk pj