算法设计与分析期末试题-考试版

11、用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程3、算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：确定性：可行性：输入：输出：算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。2复杂性的渐近性态设T(N)是算法A的复杂性函数，使得当N→∞时有：(T(N)-T’(N))/T(N)→0那么，我们就说T’(N)是T(N)当N→∞时的渐近性态，或叫T’(N)为算法A当N→∞的渐近复杂性而与T(N)相区别。P=NP经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法分而治之法1、基本思想将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法所能解决的问题一般具有以下几个特征：3（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。3、分治法的基本步骤（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。递归：直接或间接的调用自身的算法，叫做递归算法。1·期盘覆盖用分治策略，可以设计解棋盘问题的一个简捷的算法。当k0时，将2^k*2^k棋盘分割为4个2^(k-1)*2^(k-1)子棋盘特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个L型骨牌覆盖这3个较小的棋盘的汇合处，如下图所示，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘简化为1x1棋盘。2·合并排序合并排序，顾名思义，就是通过将两个有序的序列合并为一个大的有序的序列的方式来实现排序。合并排序是一种典型的分治算法：首先将序列分为两部分，然后对每一部分进行循环递归的排序，然后4逐个将结果进行合并。合并排序最大的优点是它的时间复杂度为O(nlgn)，这个是我们之前的选择排序和插入排序所达不到的。他还是一种稳定性排序，也就是相等的元素在序列中的相对位置在排序前后不会发生变化。他的唯一缺点是，需要利用额外的N的空间来进行排序。合并排序依赖于合并操作，即将两个已经排序的序列合并成一个序列，具体的过程如下：1.申请空间，使其大小为两个已经排序序列之和，然后将待排序数组复制到该数组中。2.设定两个指针，最初位置分别为两个已经排序序列的起始位置3.比较复制数组中两个指针所指向的元素，选择相对小的元素放入到原始待排序数组中，并移动指针到下一位置4.重复步骤3直到某一指针达到序列尾5.将另一序列剩下的所有元素直接复制到原始数组末尾3·快速排序（1）在数据集之中，选择一个元素作为基准（pivot）。（2）所有小于基准的元素，都移到基准的左边；所有大于基准的元素，都移到基准的右边。（3）对基准左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。（1）快速排序问题设a[0:n-1]是一个未排序的数组，如{0，12，45，3，6，29，4，16，77}。实现快速排序算法对该数组进行排序。（2）步骤对于输入的子序列L[p..r]分三步处理：第一步：分解(Divide)先从数据序列中选一个元素，称为基准元素。将序列中所有比基准元素小的元素都放到它的左边，比基准元素大的元素都放到它的右边。在序列L[p..r]中选择基准元素L[q]，经比较和移动后，L[q]将处于L[p..r]中间的适当位置，使得基准元素L[q]的值大于L[p..q-1]中任一元素的值，基准元素L[q]的值小于L[q+1..r]中任一元素的值。第二步：递归求解(Conquer)5再对左右两边分别用同样的方法处理，直到每一个待处理的序列的长度为1。通过递归调用快速排序算法，分别对L[p..q-1]和L[q+1..r]进行排序。第三步：合并(Merge)由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q-1]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序，即自然合并。这个解决流程是符合分治法的基本步骤的。贪心算法贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。(2)特性：贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。能够用贪心算法求解的问题一般具有两个重要特性：贪心选择性质和最优子结构性质(3)贪心算法与动态规划算法的差异:动态规划和贪心算法都是一种递推算法，均有最优子结构性质，通过局部最优解来推导全局最优解。两者之间的区别在于：贪心算法中作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留，贪心算法每一步的最优解一定包含上一步的最优解。动态规划算法中全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。活动安排问题由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。最小生成树6Prim算法设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i∈S,j∈V–S,且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。Kruskal算法给定无向连同带权图G=(V,E),V={1,2,...,n}。Kruskal算法构造G的最小生成树的基本思想是：（1）首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小大排序。（2）从第一条边开始，依边权递增的顺序检查每一条边。并按照下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2的端点是，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看k+1条边。这个过程一个进行到只剩下一个连通分支时为止。动态规划基本思想：基本思想动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。基本步骤（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶7段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。动态规划算法分以下4个步骤：1.描述最优解的结构2.递归定义最优解的值3.按自底向上的方式计算最优解的值//此3步构成动态规划解的基础。4.由计算出的结果构造一个最优解。//此步如果只要求计算最优解的值时，可省略。好，接下来，咱们讨论适合采用动态规划方法的最优化问题的俩个要素：最优子结构性质，和子问题重叠性质。1·最优子结构性简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2·重叠子问题在递归算法自顶向下解决问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算了多次。动态规划正是利用这种重叠子问题性质，对每一子问题直解一次，而后将其解保存在一个表格中，当8每次需要时，只简单用常数时间查看一下结果。3·备忘录方法备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此子问题时，只要简单查看该问题的解答，而不必重新计算。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下，而动态规划算法是自底向上递归。矩阵连乘9最长公共子序列2.1、最长公共子序列的结构最长公共子序列的结构有如下表示：设序列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.若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列；3.若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。其中Xm-1=x1,x2,…,xm-1，Yn-1=y1,y2,…,yn-1，Zk-1=z1,z2,…,zk-1。2.2、子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出X=x1,x2,…,xm和Y=y1,y2,…,yn的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-110和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=x1,x2,…,xi，Yj=y1,y2,…,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。其他情况下