實(shí)驗(yàn)三動態(tài)規(guī)劃樣本

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告學(xué)號姓名班級上課地點(diǎn)教師上課時(shí)間實(shí)驗(yàn)三動態(tài)規(guī)劃1. 實(shí)驗(yàn)?zāi)康?.1理解動態(tài)規(guī)劃算法的主要設(shè)計(jì)思想和基本步驟；1.2掌握用動態(tài)規(guī)劃策略解決實(shí)際問題。2. 實(shí)驗(yàn)環(huán)境2.1 Eclipse22 Window XP3. 實(shí)驗(yàn)內(nèi)容3.1矩陣連乘問題3.2取長公共子序列冋題3.3 0-1背包問題4.教師批改意見簽字：日期：成績實(shí)驗(yàn)報(bào)告細(xì)表1. 矩陣連乘問題1.1 算法設(shè)計(jì)思想(1) 分析最優(yōu)解 : 計(jì)算 Ai:j 的最優(yōu)次序所包含的計(jì)算矩陣子鏈Ai:k 和 Ak+1:j 的次序也是最優(yōu)的(2)建立遞歸關(guān)系：設(shè)計(jì)算Ai:j, K i <j <n ,所需要的最少數(shù)乘次數(shù) mi

2、,j, 則原問題的最優(yōu)值為 m1,ni=1,2,n1pk pj當(dāng) i=j 時(shí), Ai:j=Ai, 因此, mi,i=0,當(dāng) i<j 時(shí), mi, j mi,k mk 1, j pi能夠遞歸地定義 mi,j為:i mi, jmi kinjmi,k mk 1, j pi 1pk pj iikjk 的位置有 j-i 種可能( 3) 計(jì)算最優(yōu)值 : 用動態(tài)規(guī)劃算法解此問題 , 可依據(jù)其遞歸式以自底向 上的方式進(jìn)行計(jì)算。 在計(jì)算過程中 , 保存已解決的子問題答案。 每個子問 題只計(jì)算一次 , 而在后面需要時(shí)只要簡單查一下 , 從而避免大量的重復(fù) 計(jì)算, 最終得到多項(xiàng)式時(shí)間的算法public sta

3、tic void MatrixChain(int p,int m,int s) int n=p.length-1;for(int i=1;i<=n;i+)mii=0;for(int r=2;r<=n;r+)for(int i=1;i<=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi+1ij;sij=i;for(int k=i+1;k<j;k+)int t=mik+mk+1j+pi-1kj;if(t<mij)mij=t;sij=k;( 4) 構(gòu)造最優(yōu)解 : 算法 matrixChain 記錄了構(gòu)造最優(yōu)解所需的全部信 息。sij=k 表明計(jì)算矩陣鏈

4、 Ai:j 的最佳方式在矩陣 Ak 和A+i之間斷開,即最優(yōu)的加括號方式為(Ai:k)(Ak+1:j)。因此, 從 s1n 記錄的信息可知計(jì)算 A1:n 的最優(yōu)加括號 方式為 (A1:s1n)(As1n+1:n)。而 A1:s1n 的最優(yōu)加括號方式為(A1:s1s1n)(As1s1n+1:s1s1n)。同理能夠確定 As1n+1:n 的最優(yōu)加括號方式在 ss1n+1n 斷開。照此遞推下去 , 最終能夠得到 A1:n 的最優(yōu)完全加括號方式 , 即構(gòu)造出問題的一個最優(yōu)解。public static void traceback(int s,int i,int j)if(i=j)return;tra

5、ceback(s,i,sij);traceback(s,sij+1,j);System.out.println("Multiply A"+i+","+sij+"and A"+(sij+1)+","+j);1.2 程序源碼矩陣連乘代碼 :/* 下面是矩陣連乘問題的動態(tài)規(guī)劃算法* 假設(shè)有 6 個矩陣 :* A1 A2 A3 A4 A5 A6* 30*35 35*15 15*5 5*10 10*20 20*25則 matrixChain 為* 30, 35, 15, 5, 10, 20, 25結(jié)果為* (A1 * (A2

6、 * A3) * (A4 * A5) * A6) )* author zhanlingxia*/package juzhenliancheng;public class juzhenliancheng public static void main(String args) int p = 30, 35, 15, 5, 10, 20, 25;/ 矩陣的維數(shù)存放于數(shù)組 p中matrixMultiply (p);/ 矩陣連乘public static void matrixMultiply( int p) int dimen = p. length ;int m = new int dimendi

7、men; / 定義了存放最優(yōu)值數(shù)組 mint s = new int dimendimen; / 定義了記錄斷開位置的數(shù)組 sMatrixChain (p,m,s);System.out .println(" 最優(yōu)乘法次數(shù) : " + m1dimen - 1);System.out .println(" 劃分規(guī)則為 : " );traceback (s, 1, dimen - 1);/*1: 首先計(jì)算出 mii2:然后根據(jù)遞歸式按矩陣鏈長遞增的方式以此計(jì)算mii+1i=1,2,3. 。3:計(jì)算 mij 時(shí)，只要用到 mik和mk+1j*/public s

8、tatic void MatrixChain( int p, int m, int s)int n=p. length -1;for (int i=1;i<=n;i+)mii=0; / 計(jì)算單一矩陣/ 根據(jù)遞歸式按矩陣鏈長遞增的方式以此計(jì)算 mii+1i=1,2,3.for (int r=2;r<=n;r+)for (int i=1;i<=n-r+1;i+)int j=i+r-1; mij=mi+1j+pi+1*pi*pj;sij=i;for (int k=i+1;k<j;k+)int t=mik+mk+1j+pi-1*pk*pj;/ 更新 mij, sij的值if (

9、t<mij)mij=t;sij=k;/按算法MatrixChain計(jì)算出斷點(diǎn)矩陣s指示的加括號方式public static void traceback( int s, int i, int j)if (i=j) return ;traceback (s,i,sij);traceback (s,sij+1,j);System, out.pri ntln( "Multiply A" +i+"," +sij+ "andA"+(sij+1)+"," +j);1.3實(shí)驗(yàn)結(jié)論Hi Problems Javadoc 曉，Declaration 貝 Console 詔B< term i n a ted > J uzh e nil i a nch eng Jav 白 Application UP ogram Fi I e a vaj ire 6b injaexe (2014年冬三駆戡二基132S0Multiply A2 2and A3f 3Multiply Al,land A2t3Multiply A4j4and A5f5Multiply A4,Sand A6,&Multiply Al> 2and A4f6*1.4心得體會算法設(shè)計(jì)真的需要邏