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