《算法设计与分析实验报告》由会员分享，可在线阅读，更多相关《算法设计与分析实验报告（35页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析 报告学生姓名学 号专业班级指导教师完成时间、课程内容二、算法分析1、分治法(1 )分治法核心思想(2) MaxMin算法分析2、动态规划(1)动态规划核心思想(2)矩阵连乘算法分析3、贪心法(1)贪心法核心思想背包问题算法分析装载问题算法分析4、回溯法(1)回溯法核心思想N皇后问题非递归算法分析N皇后问题递归算法分析三、例子说明1、MaxMin问题目录4.5.6.7.9.9.1212.1214.5.1.5.16.2、矩阵连乘.1.6.3、背包问题4、最优装载.1.7.5、N皇后问题（非递归）176、N皇后问题（递归）18四、心得体会18五、算法对应的例子代码.19.1、求最大值
2、最小值192、矩阵连乘问题213、背包问题24.4、装载问题285、N皇后问题（非递归）316、N皇后问题（递归）344、课程内容1、分治法，求最大值最小值，maxmin算法；2、动态规划，矩阵连乘，求最少连乘次数；3、贪心法，1）背包问题，2）装载问题；4、回溯法，N皇后问题的循环结构算法和递归结构算法二、算法分析1、分治法（1）分治法核心思想当要求解一个输入规模为 n ,且n的取值相当大的问题时，直接求解往往是非常困难 的。如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1k wn ,而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，这
3、类问题可以用分治法求解 。分治法的核心技术1）子问题的划分技术。2） 递归技术。反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题3 )合并技术。(2) MaxMin 算法分析问题：在含有n个不同元素的集合中同时找出它的最大和最小元素。分治策略设计思想：将任一实例1= (n , A(1)，A(n)分成两个实例 如果MAX1和MINI是11中的最大和最小元素，MAX2和MIN2是I2中的最大和最小元素 ，MAX1和MAX2中的大者就是I 中的最大元素 MAX , MINI和MIN2中的小者是I中的最小元素 MIN。如果I只包含一个 元素，则不需要作任何分
4、割直接就可得到其解 。核心算法如下：procedureMAXMIN(i,j,fmax,fmi n)global n , A1:ncase i = j：fmax jfmin JAi/* 只有一个元素 */i = j-1 : if Ai A j then/* 两个元素 */fmax jAj ; fmin jAielse fmax jAi ; fmin jA jelse: mid j/*分成两部分*/MAXMIN(i,mid,max1,mi n1)MAXMIN(mid+1,j,max2,mi n2)fmax j max(max1,max2)fmin j min(min 1,min2)MAXMIN的时
5、间复杂性分析用T(n)表示比较次数，则所导出的递归关系式0T (n)1T(n/2) T ( n/2 )2当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=3 n/2-2对于任意 n ,存在整数k,有2k-1n 2k, T(n) 3n/2-22、动态规划(1) 动态规划核心思想,但是动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题经分解得到的子问题往往不是互相独立的。用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解
6、决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法 。设计动态规划法的步骤：1、划分阶段(子问题)，分析最优子结构性质。2、 找出阶段间的最优决策的递推关系，写出动态规划方程；3、 设计自底向上计算出最优值的步骤。4、 从最终决策的回溯子问题的决策，构造一个最优解。(2) 矩阵连乘算法分析问题：给定n个矩阵A1,A2,An,其中Ai与Ai+1是可乘的，i=1 , 2，n-1。如 何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。两个矩阵相乘所需做的数乘次数为l*n*m ,矩阵乘法满足结合律,故矩阵连乘有可以有许多不同的计算
7、顺序。计算顺序由加括号的方式确定，加括号的方式决定了矩阵连乘 的计算量。核心算法如下：依次计算各层的子问题集r=1 ,初始化for i j 1 to n domii J 0从r=2至 r=nfor rj 2 ton do计算所有大小为r的子问题MatrixChain(p0:n, n , m1:n1:n , s 1:n1:n)1) for i j 1 to n do/初始化mii J 02) for r j 2ton do3) for i j 1 to n - r+1 do4) j j i+r-15) mij J mi+1j+ pi-1*pi*p6) sijJ i7) for k j i+1 t
8、o j-1 do/子问题由小到大/子问题的起点/子问题的终点j/初值考虑/记录分割点/求最好的分割k8) t Jmik + mk+1j + pi-1*pk*pj;9) if t mij then10) mi j J t11) sij J k3、贪心法(1)贪心法核心思想顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择 。希望通过局部最优选择 达到全局的最优作出贪心决策的依据称为贪心准则(greedy criterion )。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。贪心法一般方法1
9、) 根据题意，选取一种量度标准。2) 按这种量度标准对这 n个输入排序，3) 依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把 此输入加到这部分解中。(2)背包问题算法分析问题：已知有n种物品和一个可容纳 M重量的背包，每种物品i的重量为wi。假定将物 品i的一部分xi放入背包就会得到pixi的效益，这里，0 xi0。如果这些物品重量的和大于M ,要求所有选中要装入背包的物品总重量不得超过M ,而装入背包物品获得的总效益最大。即max pixi ,WjXjM1 i ni i n满足约束条件的任一集合 (x1，xn)是一个可行解(即能装下)，使目标函数取最大值的可行解
10、是最优解。核心算法如下用利润/重量为量度即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。这就需使物品的装人次序按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; inti, n;Xj 0/将解向量初始化为零/cu j M/cu是背包剩余容量IIfor i j 1 to n doif Wicuthe n breakXi j 1 cu j cu-Wiif i wn the nXi
11、j cu/ Wi(3) 装载问题算法分析问题：有一批集装箱要装上一艘载重量为M的轮船。其中集装箱i的重量为 Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船设装载入船的集装箱的子集为Smax习 | i S, 1 i q约束 Ewi WM ,1 i n, i S核心算法如下：采用重量最轻者先装的贪心选择策略Loading( M, n)global W1.n , X1.n/ W仁n为非递减序X J0 II解向量清0cu J Mfor i j 1 to n do if cu0 do/对所有的行执行以下语句 /1) X(k) X(k)+1/ 移到下一列 /While X(k) wn and not PLACE(k) do2) X(k) X(k)十 Iif X(k) wn/找到一个位置/then if k=n /是一个完整的解吗/then print(X)/是，打印这个数组/3) elsekk+1 ; X(k)0; 4) else k k 1 / 回溯 /end NQUEENS测试X(K)是否合理procedure PLACE(k)/如果一个皇后能
