算法设计期末复习(共8页).doc

精选优质文档-倾情为你奉上第一章 算法引入1、算法的八大基本步骤：问题分析、数学模型建立、算法的设计与选择、算法分析、算法表示、算法实现、程序调试、结果整理文档编制（算法设计是解决问题的核心）2、算法的三大要素：操作、控制结构、数据结构。3、算法的四大基本特征：输入、输出、确定性、有限性。输入：有零个或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。4、 对算法的评价有两个大的方面：人对算法的维护的方便性、算法在实现运行时占有的机器资源的多少即算法的运行的时间和空间效率。5、 和算法执行时间相关的因素： （1）问题中数据存储的数据结构；（2）算法采用的数学模型 ；（3）算法设计的策略；（4）问题的规模 ；（5）实现算法的程序设计语言 ；（6）编译算法产生的机器代码的质量 ；（7）计算机执行指令的速度 6、算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需要的资源越多该算法的复杂性越高，反之所需要的资源越少该算法的复杂性越低。（算法复杂性包括时间复杂性和空间复杂性）7、一个算法中所有语句的频度之和构成了该算法的运行时间。8、以上时间复杂度级别是由低到高排列的,其随规模n的增长率，图1 T(n)与规模n的函数关系第二章 递归与分治策略1、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。2、（简答题）分治法的适用条件（特征）：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3、 二分搜索技术（P23）二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用O（logn）时间完成搜索任务二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取an/2与x进行比较。如果x=an/2，则找到x，算法终止。如果x<an/2，则只要在数组a的左半部继续搜索x。如果x>an/2，则只要在数组a的右半部继续搜索x。二分搜索算法具体算法描述（代码填空）public static int binarySearch(int a,int x,int n) /在a0<=a1<=.<=an-1中搜索x，找到x时返回其在数组中的位置，否则返回-1 int left = 0;int right = n-1; While(left<=right) int middle O(logn)= (left+right)/2; if(x=amiddle) return middle; if(x>amiddle) left = middle+1； else right = middle-1; return-1; /未找到x4、 合并排序（p29）（选择题计算复杂度，只要记住算法思路）将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。最坏时间复杂度：O(nlogn)，平均时间复杂度：O(nlogn)。5、 快速排序（p31）（只要记住算法思路）在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn)总结：排序的算法复杂性为O(logn)，合并排序与快速排序中，合并排序更稳定。第三章 动态规划1、（简答题）动态规划算法四大基本步骤（必须实现，只有求出最优值才执行）找出最优解的性质，并刻画其结构特征；递归地定义最优值；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造最优解。2、动态规划算法的基本要素：最优子结构性质和子问题重叠性质（2大要素）3、最长公共子序列（P58、P60）（理解补充）若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列问题：给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。总结：2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。 eg.最长公共子序列（代码填空）public static int lcsLength(charx, chary, int b) int m= x.length-1; int n= y.length-1; intc= new intm+1n+1; for(int i=1;i<=m;i+) ci0=0; for(int i=1;i<=n;i+) c01=0; for(int i=1;i<=m;i+) for(int j=1;i<=m;j+) if (xi=yj) cij=ci-1j-1+1; bij=1; else if (ci-1j>=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 第四章 贪心算法1、贪心算法的基本要素：贪心选择性质和最优子结构性质（P88）2、活动安排问题（补充说明）活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。活动安排问题（代码填空）public static int greedySelector(ints,intf,booleana) int n =s.length-1; a1 = true; int j=1; int count = 1; for(int i = 2;i<=n;i+) if(si>=fj) ai=true; j=i; count+; /第二个活动开始时间是否大于前一个 else ai = false; return count;3、多机调度问题（综合题）（P104）（补充解释）多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。按此策略，当时，只要将机器i的0, ti时间区间分配给作业i即可，算法只需要O(1)时间。当时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。例如，设7个独立作业1,2,3,4,5,6,7由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为2,14,4,16,6,5,3。按算法greedy产生的作业调度如下图所示，所需的加工时间为17。 第五章 回溯法 第六章 分支限界法1、（简答题）分支限界法与回溯法的异同相同：分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。不同：（1）分支限界法与回溯法的求解目标不同：回溯法是找出满足约束条件的所有解；分支限界法是找出满足条件的一个解，或某种意义下的最优解。（2）搜索方式不同：回溯法为深度优先；分支限界法为广度优先或最小耗费优先。2、子集树与排列树：当所给的问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间树称为子集树。通常有2n个叶结点。当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。通常有n！个叶结点。3、分支限界法的基本思路（P153）（理解补充）分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。分支限界法与回溯法的主要不同在于对当前扩展结点所采用的扩展方式不同：在分支限界法中，每一个活结点只有一次机会成为扩展结点。成为扩展结点后，就一次性产生其所有儿子结点。其中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法：队列式(FIFO)分支限界法： 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法： 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。4、回溯法解一些组合数相对大的问题。5、回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。6、常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。7、运用回溯法解题通常包含以下三个步骤（简答题）针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。8、上界函数可对装载问题的算法引入上界函数，减去不含最优解的子树。设Z是解空间树第i层上的扩展结点，可取上界函数为：cw+rbestw装载问题解空间：子集树（综合题）重点0-1 背包问题（回溯法（深度优先）与分支限界法（优先队列方法）画出解空间给出数据，利用两个方法其中一个进行解。重点旅行售货问题专心-专注-专业