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

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

算法设计与分析期末试题考试版M6握x第57rjj-5"W4?rE・帚孑欢k。君2国zr-3第1次尸1*I十^程力*rx%%2^415-6-b30*35*15=(At)AiAHA2A3){A1AJA3-d(A2A3A4](AlA)tAjA4)，(A1A^^}A4.■[AM3A1AH{A1A2KAJA4A5).{AlA\J}{A^A?)(《：mi4}aiAi{A2^3A4A$A6]t'PUA2HAWA5A6)(Al '){AJA'A6)(4]4?A*AJ)iA;A6){A1A_43A-AJA61充THA二{a*A1}A44A2{AJA4A5]'3A3*A4A5MWA3A41QAEA3A4A?A6^(a2AJHA4A5A6}h《为",1为二}{R、A6},gYW)ASJr♦3卜30二(A_Z；AdrAj{A4Ai).-|A.Al}A?Aj{A4A2iA6}，-{A/A；A>A6}(AjA-aJA6^船.atA』)“15^*10=.(AJ]A5-A』(A>AJ{%-%)A6*0fA5)*11)*20*25=(A51A6礼.**,(k26人最长公共子序列最长公共子序列的结构最长公共子序列的结构有如下表示：设序列X=<x,x 2,…，x m>和Y=<yi,y 2,…，y n>的一个最长公共子序列 Z=<zi, z2,…，z k>,则:.若xm=yn,则zk=xm=yn且Zk-i是Xm-i和Yn-i的最长公共子序列；.若Xm^yn且zkwXm，则Z是Xm-i和Y的最长公共子序列；.若Xm^yn且zkWyn，则Z是X和Y>-i的最长公共子序列。其中Xm-i=<xi,x2,…，xm-i>,Y)-i=<yi,y2,…，yn-i>,Zk-i=<zi,z2,…，zk-i>。子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出 X=<xi,x2,…，xm>和丫=<y,y2,…，yn>的最长公共子序列，可按以下方式递归地进行：当 xm=yn时，找出Xm-i禾口Y-i的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和丫的一个最长公共子序列。当 xmWyn时，必须解两个子问题，即找出 Xm-i9/26算法设计与分析期末试题考试版和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为 X和丫的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。 例如，在计算X和丫的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Y-1的最长公共子序列。与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用c[i,j]记录序列X和丫的最长公共子序列的长度。其中X=<x1,x2,•••,xi>,Y=<y1,y2,•••,yj>。当i=0或j=0时，空序列是X和丫的最长公共子序列，故c[i,j]=0o其他情况下，由定理可建立递归关系如下：(} if/=Ocrj=1((/-L/—I]+I ifJ>(>undxt=>,j—l]t-I,j])ifLJ>(IandXf#皆.计算最优值直接利用上节节末的递归式，我们将很容易就能写出一个计算 c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有 0(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法 LCS_LENGTH(X,Y)X序歹UX=<X1,X2,…，xm^DY=<y1,y2,…，yn>作为输入。输出两个数组c[0..m,0..n]和b[1..m,1..n]。其中c[i,j]存储X与丫的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和丫的最长公共子序列的长度记录于 c[m,n]中。由算法LCS_LENGT计算得到的数组b可用于快速构造序列X=<x,x2,…，x„>和Y=<y,y2,…，yn>的最长公共子序列。首先从b[m,n]开始，沿着其中的箭头所指的方向在数组 b中搜索。当b[i,j]中遇到"\"时(意味着xi=yi是LCS的一个元素)，表示X与丫的最长公共子序列是由X-1与Y-1的最长公共子序列在尾部加上 xi得到的子序列；当b[i,j]中遇到"T"时，表示X与Y的最长公共子序列和X-1与Y的最长公共子序列相同;当b[i,j]中遇到"一"时，表示X与丫的最长公共子序列和Xi与Y-1的最长公共子序列相同。这种方法是按照反序来找LCS的每一个元素的。由于每个数组单元的计算耗费 0(1)时间，算法LCS_LENGTH时O(mn。10/26算法设计与分析期末试题考试版,012 3 4 5 6流水线调度在M1上加工时间短的任务优先，而在M2上加工时间短的任务排在最后如果最小的时间是Tk1则将任务k排在第一位，如果最小的任务Tk2则排在最后一个。最优二叉搜索树对于有n个关键码的集合，其关键码有 n!种不同的排列，可构成的不同二叉搜索树有1棵。（n个结点的不同二叉树，卡塔兰数）。如何评价这些二叉搜索树，可以用树的搜索效率来衡量。例如：标识符集 {1,2,3}={do,if,stop} 可能的二分检索树为：11/26算法设计与分析期末试题考试版TOC\o"1-5"\h\z(a) (b)若P1=0.5,P2=0.1,P3=0.05,q0=0.15, q1=0.1,q2=0.05,q3=0.05,求每棵树的平均比较次数(成本)。Pa(n)=1 Xp1+2X p2+3Xp3+1Xq0+2Xq1+3X(q2+q3) =1义 0.5+2义 0.1+3X0.05 +1X0.05+2X0.1+3X(0.05+0.05) =1.5Pb(n)=1Xp1+2X p3+3Xp2+1Xq0+2Xq3+3X(q1+q2 ) =1义 0.5+2义 0.05+3X0.1+1X0.15+2X0.05+3X(0.1+0.05) =1.6Pc(n)=1Xp2+2X(p1+ p3)+2X(q0+q1+q2+q3) =1乂0.1+2义(0.5+0.05)+2X(0.15+0.1+0.05+0.05) =1.9Pd(n)=1Xp3+2Xp1+3Xp2+1Xq3+2乂q0+3乂(q1+q2)=1X0.05+2X0.5+3X0.1+1X0.05+ 2X0.15+3X(0.1+0.05) =2.1512/26算法设计与分析期末试题考试版Pe(n)=1Xp3+2Xp2+3Xpl+1Xq3+2乂q2+3乂(q0+q1) =1X0.05+2X0.1+3X0.5+1X0.05+2X0.15+3X(0.15TOC\o"1-5"\h\z+0.1) =2.85因此，上例中的最小平均路长为 Pa(n)=1.5。可以得出结论：结点在二叉搜索树中的层次越深，需要比较的次数就越多，因此要构造一棵最小二叉树，一般尽量把搜索概率较高的结点放在较高的层次 。p=y深度+ *路径长。最优二叉搜索树：在一个表示S的二叉树T中，设存储元素Xi的结点深度为Ci；叶结点(xj,xj+1)的结点深度为dj。\o"CurrentDocument"n nP二，二1 六0注：在检索过程中，每进行一次比较，就进入下面一层，对于成功的检索，比较的次数就是所在的层数加1。对于不成功的检索，被检索的关键码属于那个外部结点代表的可能关键码集合，比较次数就等于此外部结点的层数。又t于图的内结点而言，第 0层需要比较操作次数为1,第1层需要比较2次，第2层需要3次。13/26

算法设计与分析期末试题考试版根层士M=1键值：自顶向下分析A—1概率：pi,…,pk_i,Pg?pfc+根层士M=1键值：自顶向下分析A—1lr-1专口k^^k+J，■一，口左子树一』报' , 左子树右手轲k-i=i：左子隅缩为单节点.k+1=j：右子树缩为单节点.k<h左子树为空朝.k>h右子树为空糊.■力=吗粳血xi+Zm（〃即）+D+Ep。（吗+i）｝左子树（成功查找） 石子朝（硼查找）TOC\o"1-5"\h\zI7 A-l J=恩思（4+2>『+Za+2>内。]）十汇凡上（初｝- l-i 修+1 l-i 13-1,…一人"全^节^R率和 平趾上昌£子砌嘀QhL；]递推卜I算式 jq。力冒■｛qj,大一1]+q左+1,力｝+2区1wiqwnT 5=rOpfintalBST(A[L»/t]?P[l„ji]?C[L,./!+。0-矶£[1../+1,。…〃])00.104id1；00.20.814D0.41.000.30j=0 12 3 4C[/,/-i]<-0;Cj=0 12 3 4C[iJ]^P[i];C次对角元；/R次对角元C仍+1t川<-0;”c对角元最后一个元素for(d 而for(i<-\ton-rf)do*匚1 1jyf+d;”范围;2~nminval-8；for（k<^itojydo戈最优根 if（C[f;fr-ll+C[fr+lJ1<mimal）/基本操作 立方型效率加m亦。八曰1+CW+1,力；卜〃.一纪口间可以限短长d/I一后收加；”记录最优根，此句教材上错为IRpj-1]^R[i+1j]sum<-P[i]; 之间，效率降至for（si+1toj）dosumsain+P[s]; 平方型.C[i,7]=niimat+5«w/;14/26算法设计与分析期末试题考试版0.(15仆$。0.(15仆$。回溯法1.简单概述回溯法思路的简单描述是：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。基本思想类同于：•图的深度优先搜索・二叉树的后序遍历【分支限界法：广度优先搜索思想类同于：图的广度优先遍历15/26算法设计与分析期末试题考试版二叉树的层序遍历】一些概念(1)问题的解向量：回溯法希望一个问题的解能够表示成一个 n元式(x1,x2,…,xn)的形式。(2)显约束：对分量xi的取值限定。(3)隐约束：为满足问题的解而对不同分量之间施加的约束。(4)解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。(5)扩展结点：一个正在产生儿子的结点称为扩展结点(6)活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点(7)死结点：一个所有儿子已经产生的结点称做死结点(8)深度优先的问题状态生成法：如果对一个扩展结点R一旦产生了它的一个儿子C,就把C当做新的扩展结点。在完成对子树C(以C为根的子树)的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子(如果存在)(9)宽度优先的问题状态生成法 ：在一个扩展结点变成死结点之前，它一直是扩展结点(10)回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的活结点， 以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法基本思想：按照深度优先策略，从根结点出发搜索解空间。算法搜索至解空间的任一结点时总是先判断该结点是否问题的约束条件。 如果满足进入该子树，继续按深度优先的策略搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：.使用约束函数，剪去不满足约束条件的路径；.使用限界函数，剪去不能得到最优解的路径。16/26

算法设计与分析期末试题考试版问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。解空间树分为两种：子集树和排列树。两种在算法结构和思路上大体相同。.子集树所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间成为子集树。如0-1背包问题，从所给重量、价值不同的物品中挑选几个物品放入背包，使得在满足背包不超重的情况下，背包内物品价值最大。它的解空间就是一个典型的子集树。回溯法搜索子集树的算法范式如下：[cpp]viewplaincopyvoidbacktrack(intt)TOC\o"1-5"\h\z{if(t>n)output(x);elsefor (inti=0;i<=1;i++) {backtrack(t+1);x[t]=i;backtrack(t+1);if(constraint(t)&&bound(t))}.排列树所给的问题是确定n个元素满足某种性质的排列时，相应的解空间就是排列树。17/26

算法设计与分析期末试题考试版如旅行售货员问题，一个售货员把几个城市旅行一遍，要求走的路程最小它的解就是几个城市的排列，解空间就是排列树。回溯法搜索排列树的算法范式如下：[cpp]viewplaincopy<spanstyle="font-size:18px;">voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++) {swap(x[t],x[i]);if(constraint(t)&&bound(t)) backtrack(t+1);swap(x[t],x[i]);}基本步骤：确定问题的解空间：应用回溯法时，首先应明确定义问题的解的空间。问题的解空间应至少包含问题的一个解。确定结点的扩展规则搜索解空间：从开始结点出发，以深度优先的方式搜索整个解空间。分支限界法一、分支限界法与回溯法的区别与联系(1)求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解， 或是在满足约束条件的解中找出在某种意义下的最优解。(2)搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。18/26算法设计与分析期末试题考试版二、分支限界法的基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。 活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点， 并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止⑴描述：采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率。⑵原理：按照广度优先的原则，一个活结点一旦成为扩展结点（ E-结点）R后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。然后，从活结点表中取出一个结点作为当前扩展结点。重复上述结点扩展过程，直至找到问题的解或判定无解为止。（3）分支限界法与回溯法1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的 所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。19/26算法设计与分析期末试题考试版2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。（4）常见的分支限界法1）FIFO分支限界法（队列式分支限界法）基本思想：按照队列先进先出（FIFO）原则选取下一个活结点为扩展结点0搜索策略：一开始，根结点是唯一的活结点，根结点入队。从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。2）LC（leastcost） 分支限界法（优先队列式分支限界法）基本思想：为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。搜索策略：对每一活结点计算一个优先级（某些信息的函数值），并根据这些优先级；从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快20/26算法设计与分析期末试题考试版地找出一个最优解。再从活结点表中下一个优先级别最高的结点为当前扩展结点，……，直到找到一个解或活结点队列为空为止。2、单源最短路径问题问题描述在下图所给的有向图G中，每一边都有一个非负边权。要求图 G的从源顶点s到目标顶点t之间的最短路径。(2)解空间数一一排列树下图是用优先队列式分支限界法解有向图 G的单源最短路径问题产生的解空间树。从根节点s到一个叶子的一条路径表示从结点 s到结点t的一条路径，路径上边的权的和为路径长度。其中，每一个结点旁边的数字表示该结点所对应的当前路长。21/26算法设计与分析期末试题考试版(3)算法思想采用优先队列式分支限界法来解本问题:(3)算法思想采用优先队列式分支限界法来解本问题:用一极小堆来存储活结点表，其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点 i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点 s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。22/26

算法设计与分析期末试题考试版动态规划思想：石子合并问题描述：在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。图1精图2总行号="一】圻£="图加开始以为通过贪心算法可能很快解决问题，可是是行不通的。首先我们可以把这么堆石子看成一列我们假如5堆的石子，其中石子数分别为7,6,5,7,100?按照贪心法，合并的过程如下：每次合并得分第一次合并 76 5 7 100 =1123/26算法设计与分析期末试题考试版第二次合并 7 117 100=18第三次合并 18 7 100=25第四次合并25 100