動態(tài)規(guī)劃策略教材-文庫吧在線文庫
【正文】 陣鏈長度 for( i ?1 to n?r+1) { //nr+1為最后 r鏈的始位置 j ?i+r?1 // 計算鏈 i— j m[i,j] ? m[i+1,j] + pi?1*pi*pj // Ai(Ai+1..Aj) s[i,j] ? i //記錄分割位置 for(k ?i+1 to j?1){ t ?m[i,k]+m[k+1,j]+ pi?1*pk*pj //(Ai..Ak)(Ak+1..Aj) if( tm[i,j]){ m[i,j]?t s[i,j]?k }//end if }// end for(k=…) }//end for(i=….) A1 A2 A3 A4 A5 A6 30?35 35?15 15?5 5?10 10?20 20?25 ??????????????????????????????11 37520233504375]5][5[]4][2[71252053510002625]5][4[]3][2[13 00020233525000]5][3[]2][2[min]5][2[541531521pppmmpppmmpppmmm算法復(fù)雜度分析： 算法 matrixChain的主要計算量取決于算法中對 r，i和 k的 3重循環(huán)。 ? 給定 2個序列 X={x1,x2,… ,xm}和 Y={y1,y2,… ,yn}， X和 Y的公共子序列有很多， 找出 X和 Y的最長公共子序列。其中， Xi={x1,x2,…,x i}； Yj={y1,y2,…,y j}。 19:51:2619:51:2619:513/23/2023 7:51:26 PM 1以我獨沈久，愧君相見頻。 , March 23, 2023 很多事情努力了未必有結(jié)果，但是不努力卻什么改變也沒有。 下午 7時 51分 26秒 下午 7時 51分 19:51: 楊柳散和風(fēng)，青山澹吾慮。 2023年 3月 下午 7時 51分 :51March 23, 2023 1業(yè)余生活要有意義，不要越軌。 19:51:2619:51:2619:51Thursday, March 23, 2023 1知人者智，自知者明。 :51:2619:51:26March 23, 2023 1意志堅強的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 3月 23日星期四 下午 7時 51分 26秒 19:51: 1比不了得就不比，得不到的就不要。0,。 由此可見， 2個序列的最長公共子序列包含了這 2個序列的前綴的最長公共子序列。 例 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。 ?若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法計算出矩陣連乘積 ?給定 n個矩陣｛ A1,A2,… ,An｝，其中 Ai與Ai+1是可乘的 (i=1,2 ,… ,n1)。 求的 a[i][j]之后，就可以求的每個項目分的資源量： j=n。 ?無論第一步?jīng)Q策取 {2,3,4}中那一節(jié)點，其后的決策序列必須是該節(jié)點到目的節(jié)點的最短路 ?節(jié)點 1到目的節(jié)點的最短路長度可從 2,3,4到目的節(jié)點的最短路長度＋節(jié)點 1到這些節(jié)點的邊成本經(jīng)枚舉得到 ?應(yīng)用優(yōu)化原理設(shè)計算法的過程如下： ?選擇子問題的表示：設(shè) f(i)為 i到目的節(jié)點的最短路長度 ?建立 f(i)的遞歸方程 ?設(shè) A[i]為與 i相鄰的結(jié)點集合，則有 )}(),({co s)()}(),1({co s)1(minmin][]1[jfjitifjfjtfiAjAj??????初始 f(7)=0 依次計算 f(6),… ,f(1)： f(6)=1,f(5)=2, f(4)=8+f(6) f(3)=min{1+f(5),5+f(6)} f(2)=min{7+f(5),6+f(6)} f(1)=min{1+f(2),4+f(3),6+f(4)} 遞歸還可從前向后： f(i)=節(jié)點 1到節(jié)點 i的最短路的長度；遞歸從 f(1)=0開始。 ?例 1: (數(shù)字三角問題 )如圖所示的數(shù)字三角形，從頂部出發(fā)，在每一個節(jié)點可以選擇向左走或者向右走，一直走到底部，要求找到一條路徑，使路徑上的數(shù)字和最大。 for(i=m。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少 ? 為了表示方便 , 以 矩陣 加括號表示矩陣相乘的順序 輸入：向量 P = P0, P1, … , Pn， n個矩陣的行數(shù)、列數(shù) 實例： P = 10, 100, 5, 50 A1:
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1