计算机算法设计与分析

计算机算法设计与分析中 国 地 质 大 学研究生课程论文课程名称: 算法设计与分析 教师姓名: 戴光明 研究生姓名: 研究生学号: 120161* 研究生专业: * 所在院系: 计算机学院 类别: A.博士 B.硕士 C.进修生 日期: 2017.01.13 评 语对课程论文的评语：平时成绩：课程论文成绩：总 成 绩：评阅人签名：注：1、无评阅人签名成绩无效；2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；3、 如有平时成绩，必须在上面评分表中标出，并计算入总成绩。目录第一章算法导引4一、算法及其特性4二、算法分析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三、决策树（博弈树）21第六章回溯法22第七章分支限界法22一、一般方法22二、回溯法解0-1背包问题22三、分支限界法解0-1背包问题23第八章总结24第一章 算法导引课前题目：编写程序：1、 编写两个矩阵相乘的程序；2、 如图，菱形ABCD中，E是AD的中点，EF垂直于AC交CB的延长线于F，求证四边形AFBE是平行四边形。AEDFBNMC图1-1 平行四边形一、 算法及其特性1、算法是什么？ 算法是计算的方法。2、什么是计算？1) 计算是基于规则的符号串的变换；2) 计算是基于规则的物理信息的变换；3) 计算是基于规则的信息的变换。为了使计算机械化，图灵提出了图灵模型，在此基础上将理论进行技术实现，1946年诞生了第一台计算机（读写头、纸带、四元组），在内存条上进行输入输出。3、 算法的特性？4) 无二义性：由于算法是由机器执行的，所以算法的每一步都必须是确定的。5) 能行性（可计算性与不可计算性）：算法的每一步机器都能够执行（计算机能够解决的问题是有限的）。6) 有限性（可计算性与计算复杂性）。二、 算法分析算法分析就是分析算法的复杂性。1、 算法分析的计算机模型：1） 冯诺依曼计算机：串行执行的计算机。2） 均匀存储：假设存储量是够的。3） 基本运算的时间为整数。2、 两个重要的量：1） 问题的规模n。2） 频率的计数f(n)。3、求时间复杂度：1） 冒泡排序：Bubblesort 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，C5 = C2/2）进行分析后可知，运算的上界为：g(n)= O(n2)当n = n0时，若n足够大，f(n) right) 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) O(logn) O(n) O(nlogn) O(n2) O(n3)2） 指数时间复杂度算法NP（理论可行实际不可行，需要限制规模或用近似解）：O(2n) O(n!) NP方法：智能算法(GA)、随机过程。第二章 分治法算法设计的三个基础技术：1. 由难到易的校正技术例，泰勒公式：求2的值，每次取两项，经过多次泰勒公式展开可以得到方程中无线趋近合理的解。2. 由粗到细的松弛技术例，割圆术求圆的面积，超松弛迭代：3. 由大到小的分治技术（加权的方法）一、 一般方法procedure DAN(p,q)globalif Small (p,q)then return G(p,q)else m-DIVIDE(p,q)return (Combine(DAN(p,m),DAN(m+1,q)endifend DAN设算法规模为n=q-p+1， T(n)=gn ,n足够小2Tn2+fn ，n为其它二、 二分检索法输入n个有序数，输出x把n个数输入，放到二叉树，使构造的二叉树树的高度最小。Procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low1; highn. while low high do midlow+high/2 case : xA(mid): highmid+1 :else: jmid; return endcase repeatj0end BINSRCH设树的高度为k，2k+1=n，k=log(n-1)，所以k=O(logn)三、 归并分类procedure MERGESORT(low, high)integerif low highthen mid 1设n=2kfn=2fn2+nc=22fn22+2nc=2kf1+knc=an+nlogC例：输入a，b，c进行排序输出结果：图3-1 排序树由于n个关键字有n!种排列，而每种排列可以是某种特定输入下的分类结果，因此比较树必定至少有n!个外结点，每个外结点表示一种可能的分类序列。设树的高度为h，则2h=n!设比较树的最小高度为T(n)，则：n!2T(n)而当n1时有：n!n(n-1)(n-2)(n/2)(n/2)n/2因此，对于n=4有：T(n)(n/2)log(n/2)(n/4)logn故以比较为基础的分类算法的最坏情况的时间下界为O(nlogn)。四、 特斯拉森矩阵乘法工程计算Ax=B，方程个数和自变量的个数关系：当方程个数多于自变量个数时：超定；当方程个数少于自变量个数时：欠定；当方程个数等于自变量个数是：适定。矩阵相乘：Cnl=AnmBmlCij=k=1maikbkjT(n)=b n比较小7Tn/2+an2 n比较大其中，b和d是常数。根据斯特拉森的设计推理：T(n)=b n27Tn/2+dn2 n2其中，a，b是常数。求解此递推关系式，得：Tn=an21+74+742+74k-1+7kT1=cn274logn=c+1nlog7=Onlog7On2.81五、 总结分治法作用：1、 由大化小求解（并行算法，空间换时间）；2、 能有效的降低算法的时间复杂度。（O(n)- O(logn)，O(n2)- O(nlogn)，O(n3)- O(n2.81)）第三章 贪心算法一、 一般方法给定n个输入，找n个输入的一个子集，这个子集要满足一些约束条件，满足约束条件的子集可能会很多，把满足约束条件的子集都可以叫可行解。我们根据要求去定义一个目标函数，根据目标函数，使目标函数取得的极值的可行解叫最优解。例：给定图（V，E）-树-树的边权值为最小-最小生成树根据问题的特性去找一个量度标准，算法证明包括：证明量度标准、算法正确性证明。一般方法：Procedure GREEDY(A,n) solution for i1 to n do xSELECT(A) if FEASIBLE(solution,x) then solutionUNION(solution,x) endifrepeatreturn(solution)end二、 背包问题有一个背包，容量为M，现有物品N件，物品的质量为W1，W2，.，Wn，权值分别为P1，P2，.，Pn。1、问题分类设有N件物品分别装入X1，X2，.，Xn（代表物品装入的比例）。其中有，此时问题变为0、1背包问题，也就是该物品要么全部放入到背包中，要么不放入到背包中，此时为NP问题。若有，此时该问题变为部分背包问题，也就是该问题可以把物品只放入一部分到背包中，利用W/M进行排序，按排序从大到小放入到背包中，直到背包容量装满，此时为P问题。2、函数表示约束条件：目标函数：利用上述的两个表达函数，在满足约束函数条件的前提下，求取目标函数的最大值，实现背包问题的求解。例：n=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)是一棵生成树，则称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的边集。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), mincost integer NEAR(n), n, i, j,k, l, T(1:n-1,2) (k,l)具有最小成本的边 mincostCOST(k,l) (T(l,1),T(l,2) (k,l) for i1 to n do /将NEAR置初值/ if COST(i,l) COST(i,k) then NEAR(i)l else NEAR(i) k endif repeatNEAR(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) mincostmincost+COST(j,NEAR(j) NEAR(j)0 for k1 to n do /修改NEAR/ if NEAR(k)0 and COST(k,NEAR(k)COST(k,j) then NEAR(k)j endif repeat repeat if mincost then print(no spanning tree) endifend PRIM计算复杂性：O(n2)四、 单源点最短路径即一直的一个n结点有向图G=（V,E）和边的权函数C(e)，求由G中某指定结点V0到其他各个点的最短路径。生成最短路径的贪心算法：Procedure SHORTEST (V,COST,DIST,n)/G是一个有n个结点的有向图，它由其邻接矩阵COST（n，n）表示，DIST（n，n）表示，DIST（j）被置以结点V到结点j的最短路径的长度，这里1=DFN(u)的儿子w时，u是一个关节点。按后根的次序去各结点的最低深度优先数DFN(u)是：L(10)=4 L(9)=5 L(6)=8 L(8)=6 L(7)=6 L(5)=6 L(2)=1 L(3)=1 L(4)=1 L(1)=1 对于关节点：除根结点以外的其它结点，L（w）DFN（u）且w是u的儿子的结点是关节点，当然叶子结点不用考虑。 结点3：儿子结点10有L(10)4而DFN(3)=3。 结点2：儿子结点5有L(5)=6而DFN(2)6结点5：儿子结点6有L(6)8而DFN(5)7由连通图的分类可知分为单连通分图、双连通分图两种类型，每一个图上都有一定的关节点，要识别出图上所有的关节点，根据各个关节点的连通性，找到符合条件的通路。对于宽度优先搜索和深度优先搜索，在这里，首先要对各个关节点之间的连接是单连通还是双连通的关系进行确定，再找到在一个连通图中关结点之间是有实边连接时，还有没有逆边连接，实边用实线来表示，逆边用虚线来表示，再根据DFS算法和BFS算法进行实现，找出符合条件的最优路径。三、 决策树（博弈树）对策树类问题的本质思想，是起源于博弈类游戏，比如，在一盘棋赛中，对弈各方都要根据当前的局势，分析和预见以后可能出现的局面，决定自己要采取的各种对策，以争取更好的结果，博弈类问题是一种竞争，终局是表示为胜局、负局或者和局的情况的棋局，其它的都是非终止棋局。博弈过程在计算机里表示为对策树，对棋局进行判断的评价函数E（X）是maxmin的过程，该过程可采用剪枝策略，如-截断。截断：如果一个求最小值位置的值判断为小于或等于它父亲的值，那么可以停止生成这个求最小值位置其余儿子的值，在这种规则下终止生成结点值的行动称为截断。截断：如果一个求最大值位置的值判断为大于或等于它父亲的值，那么可以停止生成这个求最大值位置其余儿子的值，在这种规则下终止生成结点值的行动称为截断。第六章 回溯法第七章 分支限界法回溯法：深度优先搜索+限界函数分支限界法：宽度优先搜索+限界函数+LC（最小成本）一、 一般方法回溯法其实是求n元组的问题。所要求的解必须能表示成一个n-元组（x1，x2，xn），其中x1是取自某个有穷集Si。|Si|= mi，m1*m2mn。例：8-皇后问题8-皇后问题实际上是一个8元组问题。计算本质上是基于规划的一组符号的变换过程，是物理状态的变迁，而其中的状态及状态的转移（深度优化和宽度优化）本质上就是离散状态的变迁，对于离散问题，可以用迭代法来进行解决，利用迭代法，公式有收敛和发散两种情况，针对不同的情况，对问题进行求解，再就是得用宽度优先和限界函数两者进行求解，对于不同类型的问题采取不同的方法实现对问题的求解。二、 回溯法解0-1背包问题设有0/1背包问题：n=8, M=110, p=11,21,31,33,43,53,55,65，w=1, 11,21, 23,33,43,45,55。即（x1，x2，x8）为28个元组，要从中找到能使价值最大的元组，xi0，1。计算效益值使用的是0-1背包问题的效益不会超过部分背包问题的效益值，计算部分背包问题的效益值。图7-1 回溯法生成的树很容易看出最优解是(1，1，1，0，1，1，0，0)，得到的效益值是159。算法分析效率：状态空间树共有29-1=151个结点，而算法仅生成了35个结点，占总结点的6.85%。三、 分支限界法解0-1背包问题例：已知背包问题n=4, M=15 (p1, p2, p3, p4) =(10,10,12,18) (w1,w2,w3,w4)=(2, 4, 6, 9)下面的数字：背包的下界u， 上面的数字：背包的上界c。首先将根，即结点1作为E-结点，c(1)=-38，u(1)=-32。由于它不是答案结点，因此过程LCBB置ans=0和U=-32+。扩展此E-结点，生成它的两个儿子结点2和3，放入活结点表中，结点2变成下一个E-结点，生成结点4和5。这样一步一步向下扩展，在