動態(tài)規(guī)劃算法(共10頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實驗02動態(tài)規(guī)劃算法實驗目的1. 掌握動態(tài)規(guī)劃算法的基本方法2. 掌握動態(tài)規(guī)劃算法中最優(yōu)子結(jié)構(gòu)的分析3. 掌握遞歸求解最優(yōu)值的方法4. 掌握最優(yōu)解的構(gòu)造.預習要求1. 認真閱讀算法設(shè)計教材,了解動態(tài)規(guī)劃原理;2. 設(shè)計用動態(tài)規(guī)劃算法求解矩陣連乘、最長公共子序列以及電路布線的java程序.實驗題1. 給定n個矩陣A1, A2, ,An，其中，Ai與Ai+1是可乘的，計算這n個矩陣的連乘積。從中找出一種乘次數(shù)最少的計算次序。2. 給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。3. 在一塊電路板的上、下2端分別有n個接線柱。根據(jù)電路設(shè)計

2、，要求用導線(i,(i)將上端接線柱與下端接線柱相連，確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。該問題要求確定導線集Nets=(i,(i),1in的最大不相交子集。 實驗步驟1. 設(shè)計并實現(xiàn)算法并準備測試用例,修改并調(diào)試程序,直至正確為止;2. 應用設(shè)計的算法和程序求解問題;3. 將程序整理成功能模塊存盤備用. 實驗報告要求1. 闡述實驗目的和實驗內(nèi)容;2. 闡述求解問題的算法原理;3. 提交實驗程序的功能模塊;4. 記錄最終測試數(shù)據(jù)和測試結(jié)果。參考1./矩陣連乘類public class Matrix private int MN;/表示矩陣鏈中矩陣的數(shù)目private in

3、t p;/存放各個矩陣的維數(shù)private int A;/存放要進行連乘的多個矩陣private int m;/用來存放Ai到Aj的最少乘次數(shù)private int s;/用來存放Ai到Aj的最后斷開位置/public Matrix()MN=0;p=new int MN;/構(gòu)造函數(shù),L為矩陣的數(shù)目public Matrix(int L)MN=L;p=new int MN+1;A=new int MN;m=new int MN+1MN+1;s=new int MN+1MN+1;/隨機生成連乘矩陣的維數(shù)1-11for(int i=0;i<=MN;i+)pi=(int) Math.round(

4、Math.random()*10)+1;/隨機生成各個矩陣for(int i=0;i<MN;i+)Ai=new int pipi+1;CreatMatrix(Ai,pi,pi+1);/創(chuàng)建矩陣a，維數(shù)為m*nprivate void CreatMatrix(int a,int m,int n)for(int i=0;i<m;i+)for(int j=0;j<n;j+)aij=(int) Math.round(Math.random()*99)-50;/輸出連乘的所有矩陣private void printAllM()for (int i=0;i<this.MN;i+)S

5、ystem.out.println("A"+(i+1)+": "+Ai.length +"*"+Ai0.length );printM(Ai);/輸出矩陣a的每個元素private void printM(int a)for(int i=0;i<a.length ;i+)System.out.print(" ");for(int j=0;j<ai.length;j+)System.out.print(String.format("%4d", aij);System.out.print

6、ln();public static void main(String args)Matrix M=new Matrix(7);M.printAllM();M.matrixChain(M.p,M.m,M.s);System.out.print("矩陣鏈所需的最少乘次數(shù)為："+M.m1M.MN);System.out.println();String s=new StringM.MN+1;for(int i=1;i<=M.MN;i+)si="A"+i;M.traceback(M.s, 1, M.MN,s);for(int i=1;i<=M.MN

7、;i+)System.out.print(si);/作用：計算a，b矩陣的乘積，將結(jié)果保存在c中，/參數(shù)：ra為a的行數(shù)，ca為a的列數(shù)，rb為b的行數(shù)，cb為b的列數(shù)public static void matrixMultiply(int a,int b,int c,int ra,int ca,int rb,int cb)if(ca!=rb)throw new IllegalArgumentException("矩陣不可乘");/i為乘積矩陣元素的行下標for(int i=0;i<ra;i+)/j為乘積矩陣元素的列下標for (int j=0;j<cb;j+

8、)/sum初始化為a中i行第一個原素和b中j列第一個元素的乘積int sum =ai0*b0j;/計算a中第i行和b中第j列對應元素乘積的和for(int k=1;k<ca;k+)sum+=aik*bkj;/將乘積的和賦值給乘積矩陣的相應元素cij=sum;/作用：計算矩陣連乘時，矩陣鏈的最少乘次數(shù)/參數(shù)：p0:n表示矩陣A1,A2.An的維數(shù)。Ai為pi-1*pi/ m，用來存放矩陣鏈的最少乘次數(shù)，mij表示Ai,j最少乘次數(shù)/ s，用來存放矩陣鏈最優(yōu)次序的斷開位置。public static void matrixChain(int p, int m, int s)/n為矩陣個數(shù)in

9、t n=p.length-1;/矩陣鏈長度為1,不需要進行乘運算，即mii值為0for (int i=1;i<=n;i+) mii=0;/計算矩陣鏈長度大于1的m值for (int r=2;r<=n;r+)/針對長度為r的各個矩陣鏈Ai,j計算最少乘次數(shù)mfor(int i=1;i<=n-r+1;i+) int j=i+r-1;/計算初始值mij=mii+mi+1j+pi-1*pi*pjmij=mi+1j+pi-1*pi*pj;/記錄對應的斷開位置isij=i;/斷開位置k從i+1到j(luò)-1，依次計算m值for (int k=i+1; k<j; k+)/計算斷開位置為k的

10、乘計算次數(shù)，保存到tint t=mik+mk+1j+pi-1*pk*pj;/若t比所記錄的最少乘計算次數(shù)少，則用t替換，并記錄新的斷開位置if (t<mij) mij=t;sij=k;public static void traceback(int s,int i,int j,String c)if(i=j) return;traceback(s,i,sij,c);traceback(s,sij+1,j,c);ci="("+ci;cj=cj+")"System.out.println("Multiply A"+i+",

11、"+sij+"and A"+(sij+1)+","+j);2./最長公共子序列類public class Xl private char x;private char y;private int xl;private int yl;public Xl(int m,int n)xl=m;yl=n;x=new char xl;y=new char yl;for(int i=0;i<m;i+)int t=(int)(Math.random()*8)+65;xi=(char) t;for(int i=0;i<n;i+)int t=(int)

12、(Math.random()*8)+65;yi=(char) t;private void print()for(int i=0;i<this.xl;i+)System.out.print(String.format("%3s", xi);System.out.println();for(int i=0;i<this.yl;i+)System.out.print(String.format("%3s", yi);public static void main(String args)Xl xl1=new Xl(10,12);int b=new

13、 int xl1.xlxl1.yl;int lcsl=lcsLength(xl1.x,xl1.y,b);xl1.print();System.out.println();System.out.print("最長公共子序列的長度為："+lcsl);System.out.println();xl1.lcs(xl1.xl-1,xl1.yl-1,xl1.x, b);/計算x和y最長公共子序列的長度，b用來記錄標記/最優(yōu)值存放在c中public static int lcsLength(char x,char y,int b)int m=x.length-1;int n=y.leng

14、th-1;int c=new int m+1n+1;/j=0,最長公共子序列為0for(int i=1;i<= m;i+) ci0=0;/i=0,最長公共子序列為0for(int i=1;i<= n;i+) c0i=0;/i,j>0時，計算最長公共子序列的長度for(int i=1;i<= m;i+) for (int j=1;j<=n;j+)/xi=yj,cij=ci-1j-1+1if (xi=yj) cij=ci-1j-1+1;bij=1;/xi<>yj,cij=maxcij-1,ci-1jelse if (ci-1j>=cij-1) cij

15、=ci-1j;bij=2;else cij=cij-1;bij=3; return cmn;/構(gòu)造最長公共子序列public static void lcs(int i,int j,char x,int b)if (i =0 | j=0) return;if (bij= 1)lcs(i-1,j-1,x,b);System.out.print(String.format("%3s", xi);else if (bij= 2) lcs(i-1,j,x,b);else lcs(i,j-1,x,b);./電路步線public class WireSet private int n;

16、/導線的數(shù)目private int m;private int c;/存放導線private int size;private int net;/存放最大公共不相交子集/構(gòu)造函數(shù)：根據(jù)num的值所表示的導線的數(shù)目，進行初始化public WireSet(int num)n=num;c=new int n+1;size=new int n+1n+1;net=new int n+1;/對c進行賦初值，為1-n的任一個排列c1=(int)(Math.random()*(n)+1);int i=2;while(i<=n)int f=0;int t=(int)(Math.random()*(n)+

17、1);for(int j=1;j<i;j+)if (cj=t) f=1;break;if (f=0)ci=t;i+;/用來輸出相關(guān)信息public void print()/輸出上端線路編號System.out.print("上端線路編號：");for(int i=0;i<=n;i+)System.out.print(String.format("%3d", i);System.out.println();System.out.println();/輸出下端線路編號System.out.print("下端線路編號：");f

18、or(int i=0;i<=n;i+)System.out.print(String.format("%3d", ci);System.out.println();/輸出最大不相交子集的個數(shù)System.out.print("最大不相交子集的大小為："+sizenn);System.out.println();/輸出最大不相交子集中的各個導線System.out.print("上端線路編號：");for(int i=this.m-1;i>=0;i-)System.out.print(String.format("%3d", i);System.out.println();System.out.print("下端線路編號：");for(int i=this.m-1;i>=0;i-)System.out.print(String.format("%3d", ci);public static void main(String args)WireSet ws= new WireSet(10);/計算最優(yōu)值ws.mnset(ws