计算机算法设计与分析.docx

1、中 国 地 质 大 学研 究 生 课 程 论 文课 程 名 称 : 算法设计与分析 教 师 姓 名: 戴光明 研究生姓名: 研究生学号: 120161* 研究生专业: * 所 在 院 系: 计算机学院 类别: A.博士 B.硕士 C.进修生 日期: 2017.01.13 计算机算法设计与分析2 / 25评 语对课程论文的评语：平时成绩： 课程论文成绩：总 成 绩： 评阅人签名：注：1、无评阅人签名成绩无效；2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；3、 如有平时成绩，必须在上面评分表中标出，并计算入总成绩。计算机算法设计与分析3 / 25目录第一章 算法导引 .4一、 算法及其特性 .4二、

2、 算法分析 .4第二章 分治法 .6一、 一般方法 .6二、 二分检索法 .6三、 归并分类 .7四、 特斯拉森矩阵乘法 .8五、 总结 .8第三章 贪心算法 .9一、 一般方法 .9二、 背包问题 .9三、 最小生成树 .10四、 单源点最短路径 .11第四章 动态规划 .12一、 优化问题 .12二、 一般原理 .12三、 多段图 .12四、 每对结点间的最短路径 .14五、 最优二分检索树 .14六、 0-1 背包问题 .16七、 调度问题 .16八、 TSP 问题 .17第五章 基本检索与周游算法 .18一、 一般方法 .18二、 双连通图和深度优先检索 .19三、 决策树（博弈树）

3、.21第六章 回溯法 .22第七章 分支限界法 .22一、 一般方法 .22二、 回溯法解 0-1 背包问题 .22三、 分支限界法解 0-1 背包问题 .23第八章 总结 .24计算机算法设计与分析4 / 25第一章 算法导引课前题目：编写程序：1、 编写两个矩阵相乘的程序；2、 如图，菱形 ABCD 中，E 是 AD 的中点，EF 垂直于 AC 交 CB 的延长线于 F，求证四边形AFBE 是平行四边形。A E DF BNMC图 1-1 平行四边形一、 算法及其特性1、算法是什么？ 算法是计算的方法。2、什么是计算？1) 计算是基于规则的符号串的变换；2) 计算是基于规则的物理信息的变换；

4、3) 计算是基于规则的信息的变换。为了使计算机械化，图灵提出了图灵模型，在此基础上将理论进行技术实现，1946 年诞生了第一台计算机（读写头、纸带、四元组） ，在内存条上进行输入输出。3、 算法的特性？4) 无二义性：由于算法是由机器执行的，所以算法的每一步都必须是确定的。5) 能行性（可计算性与不可计算性）：算法的每一步机器都能够执行（计算机能够解决的问题是有限的） 。6) 有限性（可计算性与计算复杂性） 。二、 算法分析算法分析就是分析算法的复杂性。1、 算法分析的计算机模型：1） 冯诺依曼计算机：串行执行的计算机。2） 均匀存储：假设存储量是够的。3） 基本运算的时间为整数。2、 两个重

5、要的量：1） 问题的规模 n。2） 频率的计数 f(n)。3、求时间复杂度：1） 冒泡排序：计算机算法设计与分析5 / 25Bubblesort A(1-n)do i-1 to ndo j-i+1 to nif Aj n); 计算过程：f(n) = nC1 + n(n+1)C2/2 + nC3f(n) = n(C1 + C2/2 + C3) + n2C2/2对以上公式进行简化，表示如下：f(n) = n2C4 + nC5 （其中 C4 = C1 + C2/2 + C3，C 5 = C2/2）进行分析后可知，运算的上界为：g(n)= O(n2)当 n = n0 时，若 n 足够大，f(n) ri

6、ght)else hanoi (n-1, left, right, middle)print( left- right)hanoi (n-1, middle, left, right)设时间为 f(n),规模为 n:f(n) = 2f(n-1)+ C1=2(f(n-2)+ C1)+ C1= C12n所以 g(n)=O(2n)。3、 根据算法的时间界 g(n)对算法进行分类：两类：1） 多项式时间复杂度算法 P（理论可行实际也可行）：O(c) NP 方法：智能算法(GA)、随机过程。计算机算法设计与分析6 / 25第二章 分治法算法设计的三个基础技术：1. 由难到易的校正技术例，泰勒公式： 20

7、00()()().fxfxfx求 的值，每次取两项，经过多次泰勒公式展开可以得到方程中无线趋近合理的解。22. 由粗到细的松弛技术例，割圆术求圆的面积，超松弛迭代： 3072191926()5SS3. 由大到小的分治技术（加权的方法）一、 一般方法procedure DAN(p,q)globalif Small (p,q)then return G(p,q)else mA(mid): high mid+1:else: j mid; returnendcaserepeatj 0end BINSRCH计算机算法设计与分析7 / 25设树的高度为 k，2 k+1=n，k=log(n-1)，所以 k=

8、O(logn)三、 归并分类procedure MERGESORT(low, high)integerif low 1设 n=2k()=2(2)+=22(22)+2=2(1)+=+例：输入 a，b，c 进行排序输出结果：a ba cb c b ca cNNY Na , b , cc , b , aY Ya , b , c a , b , c a , b , c a , b , cYNYN输入 a ， b ， c图 3-1 排序树由于 n 个关键字有 n!种排列，而每种排列可以是某种特定输入下的分类结果，因此比较树必定至少有 n!个外结点，每个外结点表示一种可能的分类序列。设树的高度为 h，则

9、2h=n!设比较树的最小高度为 T(n)，则： n!2T(n)而当 n1 时有： n!(1)(2)(/2)(/2)/2因此，对于 n=4 有： T(n)(/2)(/2)(/4)故以比较为基础的分类算法的最坏情况的时间下界为 O(nlogn)。计算机算法设计与分析8 / 25四、 特斯拉森矩阵乘法工程计算 Ax=B，方程个数和自变量的个数关系：当方程个数多于自变量个数时：超定；当方程个数少于自变量个数时：欠定；当方程个数等于自变量个数是：适定。矩阵相乘：C nl=AnmBmlCij=1T(n)= 其中，b 和 d 是常数。 比 较 小7(/2)+2 比 较 大 根据斯特拉森的设计推理：T(n)=

10、 其中，a，b 是常数。 27(/2)+2 2求解此递推关系式，得：=()=2(1+74+(74)2+(74)1)+7(1)=2(74)log(+1)log7=(log7)(2.81)五、 总结分治法作用：1、 由大化小求解（并行算法，空间换时间） ；2、 能有效的降低算法的时间复杂度。 （O(n)- O(logn)，O(n 2)- O(nlogn)，O(n 3)- O(n2.81)）计算机算法设计与分析9 / 25第三章 贪心算法一、 一般方法给定 n 个输入，找 n 个输入的一个子集，这个子集要满足一些约束条件，满足约束条件的子集可能会很多，把满足约束条件的子集都可以叫可行解。我们根据要求

11、去定义一个目标函数，根据目标函数，使目标函数取得的极值的可行解叫最优解。例：给定图（V，E）-树-树的边权值为最小 -最小生成树根据问题的特性去找一个量度标准，算法证明包括：证明量度标准、算法正确性证明。一般方法：Procedure GREEDY(A,n)solution for i1 to n doxSELECT(A)if FEASIBLE(solution,x)then solutionUNION(solution,x)endifrepeatreturn(solution)end二、 背包问题有一个背包，容量为 M，现有物品 N 件，物品的质量为 W1，W2，.，Wn，权值分别为 P1，P

12、2 ， .，Pn。1、问题分类设有 N 件物品分别装入 X1，X2，.，Xn（代表物品装入的比例） 。其中有 ，此时问题变为 0、1 背包问题，也就是该物品要么全部放入到背包0,1ix中，要么不放入到背包中，此时为 NP 问题。若有 ，此时该问题变为部分背包问题，也就是该问题可以把物品只放入一部,i分到背包中，利用 W/M 进行排序，按排序从大到小放入到背包中，直到背包容量装满，此时为 P 问题。2、 函数表示约束条件： 1niiXWM目标函数： 1maxnii利用上述的两个表达函数，在满足约束函数条件的前提下，求取目标函数的最大值，实现背包问题的求解。计算机算法设计与分析10 / 25例：n

13、=3，M=20， （P1，P2，P3）= （25 ，24，15） ， （W1，W2，W3）=（18 ，15，10） ，（X1，X2，X3 ）=？量度标准：X1，X2 ，X3 属在 01 之间。可能的可行解如下： (x1,x2,x3) (1/2,1/3,1/4) 16.5 24.25 /没有放满背包 / (1,2/15,0 ) 20 28.2 /效益由大到小顺序装包 (0,2/3,1) 20 31 /质量由大到小顺序装包 (0,1,1/2) 20 31.5 单位质量的效益值从大到小顺序装包（最优）三、 最小生成树定义：设 G(V,E)是一个无向连通图。如果 G 的生成子图 T=(V,E)是一棵生

14、成树，则称 T是 G 的一棵生成树。当树的各边权重之和达到最小时，则称之为最小生成树。Prim 算法的基本思想是：设图 G 顶点集合为 U，首先任意选择图 G 中的一点作为起始点 a，将该点加入集合 V，再从集合 U-V 中找到另一点 b 使得点 b 到 V 中任意一点的权值最小，此时将 b 点也加入集合 V；以此类推，现在的集合 V=a，b，再从集合 U-V 中找到另一点 c 使得点 c 到 V 中任意一点的权值最小，此时将 c 点加入集合 V，直至所有顶点全部被加入 V，此时就构建出了一颗 MST。普里姆算法：procedure PRIM(E,COST,n,T,mincost)/E 是 G

15、 的边集。COST(n,n)是 n 结点图 G 的成本邻接矩阵，矩阵元素 COST(i,j)是一个正实数，如果不存在边(i,j)，则为。计算一棵最小生成树并把它作为一个集合存放到数组 T(1:n-1,2)中(T(i,1),T(i,2)是最小成本生成树的一条边。最小成本生成树的总成本最后赋给 mincost。NEAR(j)是树中使得 COST(j,NEAR(j)是对 NEAR(j)所有选择中的最小值/real COST(n,n), mincostinteger NEAR(n), n, i, j,k, l, T(1:n-1,2)(k,l)具有最小成本的边mincostCOST(k,l)(T(l,1

16、),T(l,2) (k,l)for i1 to n do /将 NEAR 置初值/ if COST(i,l) COST(i,k) then NEAR(i)lelse NEAR(i) kendifrepeatNEAR(k)NEAR(l)0 for i2 to n-1 do /找 T 的其余 n-2 条边/设 j 是 NEAR(j)0 且 COST(j,NEAR(j)最小的下标(T(i,1),T(i,2)(j,NEAR(j)mincost mincost+COST(j,NEAR(j)NEAR(j)0for k1 to n do /修改 NEAR/if NEAR(k)0 and COST(k,NEAR(k)COST(k,j)then NEAR(k)jendifiwxip