算法设计与分析实验报告.doc

算法设计与分析报告学生姓名 学 号 专业班级 指导教师 完成时间 目录一、课程内容3二、算法分析31、分治法3（1）分治法核心思想3（2）MaxMin算法分析32、动态规划4（1）动态规划核心思想4（2）矩阵连乘算法分析53、贪心法5（1）贪心法核心思想5（2）背包问题算法分析6（3）装载问题算法分析64、回溯法7（1）回溯法核心思想7（2）N皇后问题非递归算法分析7（3）N皇后问题递归算法分析8三、例子说明91、MaxMin问题92、矩阵连乘93、背包问题104、最优装载105、N皇后问题（非递归）116、N皇后问题（递归）11四、心得体会11五、算法对应的例子代码121、求最大值最小值122、矩阵连乘问题133、背包问题144、装载问题175、N皇后问题（非递归）186、N皇后问题（递归）20一、课程内容1、分治法，求最大值最小值，maxmin算法；2、动态规划，矩阵连乘，求最少连乘次数；3、贪心法，1）背包问题，2）装载问题；4、回溯法，N皇后问题的循环结构算法和递归结构算法。二、算法分析1、分治法（1）分治法核心思想 当要求解一个输入规模为n，且n的取值相当大的问题时，直接求解往往是非常困难的。如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kn， 而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，这类问题可以用分治法求解。 分治法的核心技术 1）子问题的划分技术。2）递归技术。反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。3）合并技术。（2）MaxMin算法分析问题：在含有n个不同元素的集合中同时找出它的最大和最小元素。 分治策略设计思想： 将任一实例I(n，A(1)，A(n)分成两个实例 如果MAX1和MIN1是I1中的最大和最小元素，MAX2和 MIN2是I2中的最大和最小元素， MAX1和MAX2中的大者就是I中的最大元素MAX， MIN1和MIN2中的小者是I中的最小元素MIN。如果I只包含一个元素，则不需要作任何分割直接就可得到其解。核心算法如下：procedure MAXMIN(i,j,fmax,fmin)global n，A1:n case ij： fmaxfminAi /*只有一个元素*/ ij-1：if Ai Aj then /*两个元素*/ fmaxAj ；fminAi else fmaxAi ；fminAj else：mid /*分成两部分*/ MAXMIN(i,mid,max1,min1) MAXMIN(mid+1,j,max2,min2) fmaxmax(max1,max2) fminmin(min1,min2) MAXMIN的时间复杂性分析用T(n)表示比较次数，则所导出的递归关系式：当n是2的幂时，即对于某个正整数k，n=2k，有 T(n)=2T(n/2)+2 =2(2T(n/4)+2)+2 =4T(n/4)+4+ =2k-1T(2)+2k-1+2 =2k-1+2k-2 =3n/2-2对于任意 n ，存在整数k,有2k-1n 2k, T(n) 3n/2-22、动态规划（1）动态规划核心思想动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。设计动态规划法的步骤：1、划分阶段（子问题），分析最优子结构性质。2、找出阶段间的最优决策的递推关系，写出动态规划方程；3、设计自底向上计算出最优值的步骤。4、从最终决策的回溯子问题的决策，构造一个最优解。（2）矩阵连乘算法分析问题：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。两个矩阵相乘所需做的数乘次数为 l*n*m， 矩阵乘法满足结合律，故矩阵连乘有可以有许多不同的计算顺序。计算顺序由加括号的方式确定，加括号的方式决定了矩阵连乘的计算量。核心算法如下：依次计算各层的子问题集 r=1，初始化for i 1 to n do mii 0从 r=2至 r=n for r 2 to n do 计算所有 大小为r的子问题 MatrixChain(p0:n， n，m1:n1:n，s 1:n1:n) 1) for i 1 to n do /初始化 mii 0 2) for r 2 to n do / 子问题由小到大 3) for i 1 to n - r+1 do /子问题的起点 4) ji+r-1 /子问题的终点 5) mijmi+1j+ pi-1*pi*pj / 初值考虑 6) sij i / 记录分割点 7) for k i+1 to j-1 do /求最好的分割k 8) tmik + mk+1j + pi-1*pk*pj; 9) if t 0。如果这些物品重量的和大于M，要求所有选中要装入背包的物品总重量不得超过M，而装入背包物品获得的总效益最大。即满足约束条件的任一集合(x1，xn)是一个可行解(即能装下)，使目标函数取最大值的可行解是最优解。 核心算法如下：用利润/重量为量度 即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。这就需使物品的装人次序按pi/wi比值的非增次序来考虑。procedure KNAPSACK(real P，W，M，X，n) /P(1:n)和W(1:n)分别是n个物品的重量，它们已按 P(i)/W(i)P(i+1)/W(i+1)排序,x(1:n)是解向量/ real cu；int i，n； X0 /将解向量初始化为零/ cuM /cu是背包剩余容量/ for i1 to n do if Wicu then break Xi 1 cucu-Wi if in then Xi cu/ Wi （3）装载问题算法分析问题：有一批集装箱要装上一艘载重量为M的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船设装载入船的集装箱的子集为S maxi | i S，1i n 约束 wi M ,1i n, i S核心算法如下：采用重量最轻者先装的贪心选择策略Loading( M, n) global W1.n，X1.n / W1.n 为非递减序 X 0 / 解向量清0 cu M for i1 to n do if cu0 do /对所有的行执行以下语句/1) X(k)X(k)+1 /移到下一列/ While X(k)n and not PLACE(k) do 2) X(k)X(k)十l if X(k)n /找到一个位置/ then if k=n /是一个完整的解吗/ then print(X) /是，打印这个数组/ 3) else kk+1；X(k)0； 4) else kk1 /回溯/ end NQUEENS 测试X(K)是否合理procedure PLACE(k) /如果一个皇后能放在第k行和X(k)列，则返 回true；否则返回false。X是一个全程数 组，进入此过程时已置了k个值。/ global X(1：k)； integer i，k i1 while ik do if X (i)X(k) /在同一列有两个皇后/ or ABS(X(i)X(k)ABS(ik) /在同条斜角线上/ then return(false) endif ii+1 repeat return(true) /满足约束/ end PLACE（3）N皇后问题递归算法分析使用递归算法使，反复的调用判断函数，判断后在决定位置。核心算法如下：public void setposition(int n) /n表示在第n行，tablen表示列数 for(int i = 0; i = 5; i+) /i表示在第i列上放置皇后 xn = i;if(place(n)=false ) /如果没有皇后在同一列或斜线上（因为是按行依次放置故不可能在同一行上，又因为是每一行是从左到右放置故不可能出现右斜线上有皇后） if(n = 5) /棋盘满时输出方案count+;System.out.println(第 + count + 种解:);for(int j=0;j Max2 ? Max1 : Max2; else int mid = (i + j) / 2; Max1 = getMax(array, i, mid); Max2 = getMax(array, mid, j); / count+; /System.out.println(count); return Max1 Max2 ? Max1 : Max2; /*求最小值*/ public static int getMin(intarray,int i,int j) int Min1=0; int Min2=0; if(i=j) return Min1=Min2=arrayj; else if(i=(j-1) Min1=arrayi; Min2=arrayj; return Min1Min2?Min2:Min1; else int mid=(i+j)/2; Min1=getMin(array,i,mid); Min2=getMin(array,mid,j); return Min1Min2?Min2:Min1; 2、矩阵连乘问题/*矩阵连乘问题，i,r,k的三重循环，时间复杂度为O(n立方)*/public class MatrixChainOrder int p;/矩阵维数int m;/最少乘次数int s;/分割点int length;public MatrixChainOrder(int p,int m,int s)this.p = p; this.length = p.length/2; this.m = m; this.s = s; init(); clac(); printM(); public void init() /m初始化for (int i=0;ilength;i+) mii = 0; public void clac() for (int i=1;ilength;i+) for (int j=0;jlength-i;j+) int r = j+i; /重复计算子问题，长度由1，到length int t = Integer.MAX_VALUE; /定义当前最大值 for (int k = j;k temp) t = temp; mjr = temp; public void printM() for (int i=0;ilength;i+) for (int j=0;jlength;j+) System.out.print(mij+ t); System.out.println(); public static void main(String args) int p = 30,35,35,15,15,5,5,10,10,20,20,25; int length = 6; int m = new int66; int s = new int66; new MatrixChainOrder(p,m,s);3、背包问题/* 利用贪心算法，对背包问题的java实现*/public class Knapsack private float m ; /背包容量 float v ; /三个物品的价值 float w ; /三个物品的质量 float x ; /往背包装东西的比例 int n ; /物品个数double p_w_v ; /每个物品的单位重量价值public Knapsack() this.m = 50.0f ; /背包容量为50 this.v = new float60.0f,120.0f,100.0f ; /三个物品的价值分别为60,120,100 this.w = new float10.0f,30.0f,20.0f, ; /三个物品的质量分别是10,30,20， this.x = new float3; /往背包装东西的比例 this.n = 3 ; /三个物品 this.p_w_v = new doublen ; /每个物品的单位重量价值/对物品的单位重量价值进行排序public void sort(int n , float v ,float w)throws Exception for (int i = 0 ; i n ; i+) p_w_vi = vi / wi ;/单位重量价值 print (p_w_v); System.out.println (); Sort(p_w_v,w,v) ; print (p_w_v);public void print (double a)/打印输出数组 int len = a.length; for (int i = 0; i len; i+) System.out.print(ai + ); public void print (String str)/打印输出数组 System.out.print(str + n); public void Sort(double a , float b , float c)/冒泡排序，实现排序功能 int len = a.length;/获得数组长度 double temp;/临时变量，用于交换值 float w_temp ; float v_temp ; for (int i = 0; i len-1; i+) /通过循环实现主要算法 for (int j = 0; j aj) /如果后一下值比前一个值大，则交换两个值的大小， /以下几行代码是实现数值交换的 temp = aj+1; /从大到小排序 w_temp = wj+1; v_temp = vj+1; aj+1 = aj; wj+1 = wj; vj+1 = vj; wj = w_temp; vj = v_temp; /贪心算法核心思想public void knapsack()throws Exception sort (n , v , w) ; int i ; for (i = 0 ; i n ; i+) xi = 0 ; float c = m ; for (i = 0 ; i c) break ; xi = 1 ; c -= wi ; if (i n) xi = c / wi ; print (n物品一可以装入的比例: + x0); print (物品二可以装入的比例: + x1); print (物品三可以装入的比例: + x2); print (可以装入的最大价值为: + (x0*v0 + x1*v1 + x2*v2); print (可以装入的最大重量为 + (x0*w0 + x1*w1 + x2*w2);public static void main (String args)throws Exception Knapsack ksp = new Knapsack(); ksp.knapsack();4、装载问题/*装载问题，贪心法，时间复杂度上界函数为O(n方)*/public class Loading private float m;/船的称重量private float w;/物品的质量 intx;/物品的选择int n;/物品个数public Loading()this.m=20.0f;/船的称重量为20this.n=9;/10个物品this.w=new float1.0f,5.0f,2.0f,2.0f,4.0f,8.0f,3.0f,1.0f,6.0f,2.0f;/10个物品的重量this.x=new intn;System.out.println(给定的10个可选货物为：);for(int i=0;iw.length;i+)System.out.print(wi+ );System.out.println();/对物品按照重量进行排序public void sort()float temp=0f;for(int i=0;in;i+)for(int j=0;jwj+1)temp=wj;wj=wj+1;wj+1=temp;System.out.println(排序后的数据为：);for(int i=0;iw.length;i+)System.out.print(wi+);public void loading()int i;System.out.println();System.out.println(贪心选择为：);for(i=0;in;i+)xi=0;for(i=0;im)break;xi=1;m=m-wi;if(m 0) xk += 1; / 第k列皇后向下移一行while (xk = n) & !(place(k) / 如果当前第k列皇后未出界或者和其他皇后冲突xk += 1; / 第k列皇后向下移一行继续寻找if (xk = n) / 找到一个值并且未出界if (k = n) / 已是最后一列说明已找到一个方案count+;System.out.println(第 + count + 种解:); for(int i=1;i=k;i+) /打印寻找策略 System.out.print(xi+ ); System.out.println();/ print(); else / 不是最后一列故寻找下一列k+;xk = 0; else/ 找到的值已经出界，回退到上一列k-;/ 判断皇后是否冲突boolean place(int k) for (int j = 1; j k; j+) if (Math.abs(j - k) = Math.abs(xj - xk) | (xj = x