《大学算法分析与设计复习总结》由会员分享，可在线阅读，更多相关《大学算法分析与设计复习总结（20页珍藏版）》请在金锄头文库上搜索。
1、大学算法分析与设计复习总结大学算法分析与设计复习总结第第 1 1 章章 绪论绪论考点：1、算法的 5 个重要特性。（P3）答：输入、输出、有穷性、确定性、可行性2、 描述算法的四种方法分别是什么，有什么优缺点。（P4）答：1.自然语言 优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。2.流程图 优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。3.程序设计语言 优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。4.伪代码 优点：表达能力强
2、，抽象性强，容易理解3、了解非递归算法的时间复杂性分析。(P13)要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。非递归算法分析的一般步骤是：（1）决定用哪个（或哪些）参数作为算法问题规模的度量。（2）找出算法的基本语句。（3）检查基本语句的执行次数是否只依赖问题规模。（4）建立基本语句执行次数的求和表达式。（5）用渐进符号表示这个求和表达式。 例例 1.41.4：求数组最小值算法：求数组最小值算法intint ArrayMin(intArrayMin(int aa , intint n)n) min=a0;min=a0;for
3、for (i=1;(i=1; iint findr(ints,int begin,int end)if(begin=end)if(sbegin=begin) return begin;else return 0;elseint m=(begin+end)/2;if(smm) return findr(s,begin,m-1);else if (sm=m)return m;else return findr(s,m+1,end);void main()int s=0,1,1,2,4,6,8;coutv46,x5=1,v56v46,x5=1, j=6-w5=1j=6-w5=1i=4,j=1;i=4
4、,j=1; v41=v31,v41=v31, x4=0x4=0i=3,j=1;i=3,j=1; v31v21,v31v21, x3=1,x3=1, j=1-w3=0j=1-w3=0i=2,j=0;i=2,j=0; v21=v10,v21=v10, x2=0x2=0i=1,j=0;i=1,j=0; v10=v00,v10=v00, x1=0x1=0结果是把第结果是把第 3 3 个和第个和第 5 5 个放入了背包个放入了背包掌握最长公共子序列问题的动态规划法算法及具体实现（P58）求求 X=“xzyzzyx”X=“xzyzzyx”和和 Y=“zxyyzxz”Y=“zxyyzxz”序列的最长公共子序
5、列的动态规划函数为：序列的最长公共子序列的动态规划函数为：LijLij表示表示 X X 中前中前 i i 个元素和个元素和 Y Y 中前中前 j j 个元素构成的序列的最长公共子序列的长度。个元素构成的序列的最长公共子序列的长度。为了确定具体的最长公共子序列，需要同时计算为了确定具体的最长公共子序列，需要同时计算 SijSij的值，的值，SijSij表示在计算表示在计算 LijLij的的过程中的搜索状态。过程中的搜索状态。子序列为斜箭头所标示的行或列：子序列为斜箭头所标示的行或列：X2,X3,X6X2,X3,X6 ,X7,X7或或 Y1,Y1, Y3,Y3, Y4Y4 , , Y6Y6最最长公
6、共子序列的长度为长公共子序列的长度为 4 4即为：即为：zyyxzyyx流水作业调度：最优二叉搜索树：第第 3 3 章章 贪心法贪心法了解贪心法的设计思想贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。贪心法的关键在于决定贪心策略。掌握可以用贪心法解决的问题：TSP 问题中的两种解决方法：最近领点策略，最短链接策略最小生成树问题的两种算法：最近顶点策略（Prim 算法），最短边策略（Kruskal 算法）背包问题，活动安排问题，多机调度问题，哈夫曼编码。掌握最小生成树的两种贪心算法：prim 算法和 krus
7、kal 算法（P100-102），给出具体的例子，能够用两种方法画出树的生成过程。掌握背包问题的贪心算法问题：求如下背包问题的最优解：有 7 个物品，价值 P=(10,5,15,7,6,18,3),重量w=(2,3,5,7,1,4,1),背包容量 W=15.解决方法：解决方法：先对物品的单位重量价值按照降序排列先对物品的单位重量价值按照降序排列物品重量物品重量物品价值物品价值物品价值物品价值/ /物品重量物品重量1 16 66 62 210105 54 418184.54.55 515153 31 13 33 33 35 51.671.677 77 71 1依次把物品放入容量为依次把物品放入容
8、量为 1515 的背包，直到背包被装满的背包，直到背包被装满1+2+4+5+1=131+2+4+5+1=13，前，前 5 5 个物品装入背包，还剩下容量为个物品装入背包，还剩下容量为 2 2，第，第 6 6 个物品只能装入个物品只能装入 2/32/3所以总价值为：所以总价值为：6+10+18+15+3+5*2/3=55.33336+10+18+15+3+5*2/3=55.3333给出字符集和对应的频率，能够画出对应的哈夫曼树，并对给定的字符串进行哈夫曼编码。（P92）活动安排： 最优装载：第第 8 8 章章 回溯法回溯法了解回溯法的设计思想设计思想：从解空间树根结点出发，按照深度优先策略遍历解
9、空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。步骤：确定解向量和分量的取值范围，构造解空间树；确定剪枝函数；对解空间树按深度优先搜索，搜索过程中剪枝；从所有的可能解中确定最优解。了解可以用回溯法解决的问题：属于组合问题和排列问题中求最优解的问题都可以用回溯法解决，例如：图着色问题，哈密顿回路问题，八皇后问题（4 皇后问题）
10、，批处理作业调度问题。掌握 m 颜色图着色判定问题的回溯法算法，并能画出解空间树的搜索过程（P168-170），习题 8-4对图对图 8.148.14 使用回溯法求解图问题，画出生成的搜索空间。使用回溯法求解图问题，画出生成的搜索空间。解：图着色问题求解的是满足图着色要求的最小颜色数。对图解：图着色问题求解的是满足图着色要求的最小颜色数。对图 8.148.14 应该从应该从1 1、2 2、3 3、44种颜色依次尝试用回溯法判定是否满足种颜色依次尝试用回溯法判定是否满足 M M 着色的要求。着色的要求。经搜索，经搜索，1 1 种和种和 2 2 种颜色均不能满足图着色的要求，种颜色均不能满足图着色
11、的要求，3 3 种颜色可以满足图着色要求，搜索过种颜色可以满足图着色要求，搜索过程如下，所以图程如下，所以图 8.148.14 的着色的最少颜色数应该为的着色的最少颜色数应该为 3 3搜索空间为：搜索空间为：掌握 n 皇后问题的回溯法算法，并能画出解空间树的搜索过程（P173-174）,自己看书掌握 0/1 背包问题的回溯算法，并能画出解空间树的搜索过程（P163-164），习题 8-5自己看书第第 9 9 章章 分治限界法分治限界法了解分支限界法的设计思想设计思想：1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down, up ，并确定限界函数；2）然后按照广度优先策略遍历问
12、题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表 PT）中；4）依次从表 PT 中选取使限界函数的值是极值的结点成为当前扩展结点；5）重复上述过程，直到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。步骤：确定解空间树确定限界函数按广度优先搜索解空间树，计算限界函数的值，填入 PT 表从 PT 表中寻找极值，继续扩展结点，直到找到限界函数值为极值的叶子结点。了解可以使用分支限界法解决的问题：TSP 问题，多段图的最短路径问题，任务分配问题，批处理作业调度问题，0/1 背包问题。掌握任务分配问题的分支限界法（P195-197），习题 9-5掌握 0/1 背包问题的分支限界法（P184-185），习题 9-6掌握批处理作业问题的分支限界法（P198-200），习题 9-7
