中国地质大学研究生课程论文课程名称:算法设计与分析教师姓名:戴光明研究生姓名:研究生学号: ********** 研究生专业: *********** 所在院系:计算机学院类别: 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 是平行四边形。
图1-1 平行四边形一、 算法及其特性1、算法是什么？算法是计算的方法。
2、什么是计算？1) 计算是基于规则的符号串的变换； 2) 计算是基于规则的物理信息的变换； 3) 计算是基于规则的信息的变换。
为了使计算机械化，图灵提出了图灵模型，在此基础上将理论进行技术实现，1946年诞生了第一台计算机（读写头、纸带、四元组），在内存条上进行输入输出。
3、 算法的特性？4) 无二义性：由于算法是由机器执行的，所以算法的每一步都必须是确定的。
5) 能行性（可计算性与不可计算性）：算法的每一步机器都能够执行（计算机能够解决的问题是有限的）。
6) 有限性（可计算性与计算复杂性）。
二、 算法分析算法分析就是分析算法的复杂性。
1、 算法分析的计算机模型：1） 冯诺依曼计算机：串行执行的计算机。
2） 均匀存储：假设存储量是够的。
3） 基本运算的时间为整数。
2、 两个重要的量：1） 问题的规模n 。
2） 频率的计数f(n)。
3、求时间复杂度：1） 冒泡排序：AEDFBNMCBubblesort A(1->n)do i->1 to ndo j->i+1 to nif A[j] < A[j] then exchange A[j] and A[j];continue j;continue I;print A(i->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) <= Cn2。
2）汉诺塔：hanoi (int n,char left,char middle,char right){ if (n==1) printf (left-> 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!) <O(n n)3）P->NP方法：智能算法(GA)、随机过程。
第二章 分治法算法设计的三个基础技术： 1. 由难到易的校正技术例，泰勒公式：200000()()'()()''()()......f x f x f x x x f x x x =+-+-+求√2的值，每次取两项，经过多次泰勒公式展开可以得到方程中无线趋近合理的解。
2. 由粗到细的松弛技术例，割圆术求圆的面积，超松弛迭代：30721921929636()105S S S S =-- 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))) endif end DAN设算法规模为n=q -p+1， T(n)={g (n ) ,n 足够小2T (n2)+f (n ) ，n 为其它二、 二分检索法输入n 个有序数，输出x把n 个数输入，放到二叉树，使构造的二叉树树的高度最小。
Procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low ←1; high ←n. while low ≤ high do mid ←[low+high]/2 case: x<A(mid): high ←mid -1 : x>A(mid): high ←mid+1 :else: j ←mid; return endcase repeat j ←0end BINSRCH设树的高度为k ，2k +1>=n ，k=log(n -1)，所以k=O(logn)三、 归并分类procedure MERGESORT(low, high)integer if low < high then mid <- [(low+ high)/2] call MERGESORT(low, mid) call MERGESORT(mid+1,high) call MERGE(low, mid, high) end if end设规模为n ，则f (n )={a ,n =12f (n )+nc ,n >1设n=2kf (n )=2f (n 2)+nc =22f (n22)+2nc =⋯=2k f (1)+knc =an +nlogC例：输入a ，b ，c 进行排序输出结果：图3-1 排序树由于n 个关键字有n!种排列，而每种排列可以是某种特定输入下的分类结果，因此比较树必定至少有n!个外结点，每个外结点表示一种可能的分类序列。
设树的高度为h ，则2h >=n! 设比较树的最小高度为T(n)，则：n!≤2T(n) 而当n>1时有：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 ，方程个数和自变量的个数关系： 当方程个数多于自变量个数时：超定； 当方程个数少于自变量个数时：欠定； 当方程个数等于自变量个数是：适定。
矩阵相乘：C nl =A nm B ml C ij =∑a ik m k=1b kj T(n)={b n 比较小7T (n/2)+an 2 n 比较大其中，b 和d 是常数。
根据斯特拉森的设计推理：T(n)={b n ≤27T (n/2)+dn 2 n >2其中，a ，b 是常数。
求解此递推关系式，得： T (n )=an 2(1+74+(74)2+⋯+(74)k−1)+7k T (1)=……≤cn 2(74)log n =(c+1)n log 7=O(n log 7)≈O (n 2.81)五、 总结分治法作用：1、 由大化小求解（并行算法，空间换时间）；2、 能有效的降低算法的时间复杂度。
（O(n)-> O(logn)，O(n 2)-> O(nlogn)，O(n 3)-> O(n 2.81)）第三章 贪心算法一、 一般方法给定n 个输入，找n 个输入的一个子集，这个子集要满足一些约束条件，满足约束条件的子集可能会很多，把满足约束条件的子集都可以叫可行解。
我们根据要求去定义一个目标函数，根据目标函数，使目标函数取得的极值的可行解叫最优解。
例：给定图（V ，E ）->树->树的边权值为最小->最小生成树根据问题的特性去找一个量度标准，算法证明包括：证明量度标准、算法正确性证明。
一般方法：Procedure GREEDY(A,n)solution ←∅ for i ←1 to n do x ←SELECT(A)if FEASIBLE(solution,x)then solution ←UNION(solution,x) endifrepeatreturn(solution) end二、 背包问题有一个背包，容量为M ，现有物品N 件，物品的质量为W1，W2，....，Wn ，权值分别为P1，P2，...，Pn 。
1、问题分类设有N 件物品分别装入X1，X2，...，Xn （代表物品装入的比例）。
其中有{}0,1i x ∈，此时问题变为0、1背包问题，也就是该物品要么全部放入到背包中，要么不放入到背包中，此时为NP 问题。
若有[]0,1i x ∈，此时该问题变为部分背包问题，也就是该问题可以把物品只放入一部分到背包中，利用W/M 进行排序，按排序从大到小放入到背包中，直到背包容量装满，此时为P 问题。
2、函数表示约束条件：1niii X WM =≤∑目标函数：1maxniii X W =∑利用上述的两个表达函数，在满足约束函数条件的前提下，求取目标函数的最大值，实现背包问题的求解。
例：n=3，M=20，（P1，P2，P3）=（25，24，15），（W1，W2，W3）=（18，15，10），（X1，X2，X3）=？量度标准：X1，X2，X3属在0~1之间。