算法分析设计期末复习课件.ppt

1、算法分析的基本原则1.正确性n定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。2.工作量时间复杂性分析n计量工作量的标准:对于给定问题，该算法所执行的基本运算的次数。n基本运算的选择：根据问题选择适当的基本运算。3.占用空间空间复杂性分析n两种占用：n存储程序和输入数据的空间n存储中间结果或操作单元所占用空间额外空间算法复杂性算法复杂性算法复杂性时间时间复杂性复杂性考虑时间资源空间空间复杂性复杂性考虑存储器资源需要时间资源的量需要空间资源的量算法运行时所需要的计算机资源的量时间复杂性函数的具体化？一个算法的时间复杂度（一个算法的时间复杂度（time compl

2、exity）是指算法运行所）是指算法运行所需的时间。需的时间。对于给定的对于给定的N、I和和A，如何导出，如何导出T=T(N，I)和和S=S(N，I)？T（N，I）表示算法在一台抽象的计算机上运行需要的时间。）表示算法在一台抽象的计算机上运行需要的时间。设此抽象计算机的元运算有设此抽象计算机的元运算有k种，分别记为种，分别记为O1，O2，,OK。每。每执行一次这些运算所需要的时间分别为执行一次这些运算所需要的时间分别为t1,t2,.,tk.设算法用到元设算法用到元运算运算Oi的次数为的次数为ei(是是N和和I的函数）的函数）,则则),(),(1INeitINTkii 时间复杂度时间复杂度 一般

3、情况下，不可能也没有必要总是对规模为一般情况下，不可能也没有必要总是对规模为n，基基本运算本运算Oi的执行次数的执行次数ei分别进行统计分析。分别进行统计分析。T(N,I)还需进一步简化，只在某些有代表性的合法输还需进一步简化，只在某些有代表性的合法输入中去统计相应的入中去统计相应的ei来评价其复杂性。来评价其复杂性。一般只考虑三种情况下的时间性：最坏情况、最好一般只考虑三种情况下的时间性：最坏情况、最好情况和平均情况下的复杂性，分别记为情况和平均情况下的复杂性，分别记为Tmax(N)、Tmin(N)和和Tavg(N)四种渐近意义下的符号 四种渐近意义下的符号四种渐近意义下的符号Oo假设假设f

4、(N)和和g(N)是定义在正整数集上的正函数是定义在正整数集上的正函数符号“O”的运算规则);()6()()()5()()12()12()(),(12);()()()()()4()()()()();()()()3();()()()2()(),(max()()();,(max()()()1(322222fOfCNfONCfOnOnnOnOnOnOnfOgOfONfONgnOnnOnOnOfgOgOfOgfOgOfOnOnnOnOnOgfOgOfO为常数；，则例：，则如果例：例：四种渐近意义下的符号之“O”的阶。的阶不高于时还说。这是它的一个上界，记为且充分大时有上界，当，则称函数时，使得当和自然

5、数如果存在正的常数)()()()()()()()(00NgNfNgONfNgNNfNCgNfNNNC注：注：用O评估算法的复杂性，所得到的只是当规模充分大时的一个上界一个上界。该上界的阶越低，评估就越上界的阶越低，评估就越精确，结果就越有价值。精确，结果就越有价值。g通常为下列简单函数单项形式：1,logn,n,nlogn,n2,n3,2n,n!算法时间复杂性以多项式为界的有效算法f四种渐近意义下的符号之“”的阶。的阶不低于时还说。这是它的一个下界，记为且充分大时有下界，当，则称函数时，使得当和自然数如果存在正的常数)()()()()()()()(00NgNfNgNfNgNNfNCgNfNNN

6、C注：注：用 评估算法的复杂性，所得到的只是当规模充分大时的一个下界一个下界。该下界的阶越高，评估就越下界的阶越高，评估就越精确，结果就越有价值。精确，结果就越有价值。四种渐近意义下的符号之“”同阶和称且当且仅当)()()()()()()()(NgNfNgNfNgONfNgNf 请简述对算法复杂性概念的认识 算法的复杂性就是对算法计算所需要的时间和空间的一种度量。算法的时间复杂性是指算法运行所需的时间，可以用元运算（基本运算）所需要运行的次数来进行复杂性的评估。一般用最坏情况、最好情况和平均情况下的三种复杂性对算法的时间复杂性进行分析，其中操作性最好且最具有实用价值的是最坏情况下的时间复杂性。

7、课后练习：1-4假设某算法的T(n)=3x2n，在某台机上实现并完成该算法的时间为t秒。如果有一台机的运行速度是前一台机的64倍，则在这台机上用同一算法在t秒内能解多大规模的问题?t=3x2n=3x2n164 n1=n+6课后练习：1-6答案：答案：12n)2(n22n)2(n成立吗?分治法的基本思想 分治法的基本思想分治法的基本思想 将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立并且与原问题相同。通过递归地求解这些子问题，然后再将各个子问题的解合并，就可以实现对原问题的求解。1log0log)/()(1)()/(1)1()(njjjkmmmnfknnTnnfmnkTnOn

8、T通过解递归方程 学习要点学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表。分析分析：根据教材的分治法，两个m位数相乘，耗时O(mlog3);m n，把v分成n/m段，每段分别与u做乘法乘，则共需n/m次m位的乘法；因此，算法所需的计算机时间为O(（n/m）*mlog3)=O(（nmlog（3/2);9 分析分析：（习题：（习题2-9）有序集元素，因为主元素个数大于n/2个，有主元素

9、时，中位数一定是主元素；分析分析：(1)若T 中存在主元素，则将T 分为两部分后，T 的主元素也必为两部分中至少一部分的主元素，因此可用分治法。将元素划分为两部分，递归地检查两部分有无主元素。算法如下：a.若T 只含一个元素，则此元素就是主元素，返回此数。b.将T 分为两部分T1 和T2（二者元素个数相等或只差一个），分别递归调用此方法求其主元素m1和m2。c.若m1 和m2 都存在且相等，则这个数就是T 的主元素，返回此数。d.若m1 和m2 都存在且不等，则分别检查这两个数是否为T 的主元素，若有则返回此数，若无则返回空值。e.若m1 和m2 只有一个存在，则检查这个数是否为T 的主元素，

10、若是则返回此数，若否就返回空值。f.若m1 和m2 都不存在，则T 无主元素，返回空值。(1);4()()(log)2(/2)();4OnT nT nO nnT nO nnCheckMaster(T,p,q):if p q then return Tp and 1 len q p+1 r p+len/2 a and numa CheckMaster(T,p,r 1)b and numb CheckMaster(T,r,q)if a=NIL and b=NIL then return NIL if a=NIL and b NIL then return CheckAnotherPart(T,le

11、n,p,r 1,b,numb)if a NIL and b=NIL then return CheckAnotherPart(T,len,r,q,a,numa)if a NIL and b NIL then if a=b then numa numa+numb return a and numa else re CheckAnotherPart(T,len,p,r 1,b,numb)if re NIL then return re else return CheckAnotherPart(T,len,r,q,a,numa)-CheckAnotherPart(T,len,p,q,c,numc):

12、检查候选主元素是否是主元素检查候选主元素是否是主元素 numc CheckNum(T,p,q,c)+numc if num len/2 then return c and numc else return NIL -CheckNum(T,p,q,element):计算计算Tp.q中中element出现的次数出现的次数 cnt 0 for i p to q do if Ti=element then cnt cnt+1 return cnt (2)线性时间算法 分析分析：因为主元素大于n/2个，可采用相互抵消的方法（模拟打擂台）T1 T2 T3 T4 比较T2i-1 和T2i（1 i n/2）是

13、否相同，相同时，把T2i-1 存入另一个数组Q中，否则什么也不做；比较后数组Q中有m个元素，m n/2，若x是原数组的主元素，则x是Q的主元素；算法实现题：2-2.在一个由元素组成的表中,出现次数最多的元素称为众数.试写一个寻找众数的算法,并分析其计算复杂性.分析与解答:思路一:首先将数组元素按照大小排序,然后按照顺序扫描一遍数组,扫描的同时进行统计,这样通过一次排序和一遍扫描可以找到众数.思路二:直接统计各元素出现的次数,用某一线性数据结构存储统计结果(例如用一个辅助数组存储统计结果,统计时用数组下标对应相应元素)第三章第三章:动态规划动态规划动态规划算法的基本思想 动态规划算法的基本思想动

14、态规划算法的基本思想 其基本思想与分治算法的思想类似分而治之分而治之 与分治法的不同之处 分解后的子问题往往不互相独立；采用记录表的方法来保存所有已解决问题的答案 对每个子问题都只计算一次，不管该子问题以后是否会被用到，都将其保存到一张表中，避免每次遇到各个子问题都要重复计算答案。一个最优化多步决策问题适合用动态规划法求解有两个要素：动态规划算法的一般步骤动态规划算法的一般步骤动态规划算法的一般步骤1.找出最优解的性质，并刻画其结构特征；2.递归地定义最优值；3.以自底向上的方式计算出最优值；4.根据计算最优值时得到的信息，构造最优解；动态规划算法动态规划算法的基本步骤的基本步骤如只需要求出最

15、优值，则步骤如只需要求出最优值，则步骤4可省略；可省略；如需要求解问题的最优解，则必须执行步骤如需要求解问题的最优解，则必须执行步骤4动态规划算法求解思路 动态规划算法求解思路动态规划算法求解思路 将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是与贪婪算法不同的是:在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；在动态规划算法中，还要考察每个最优决策序列

16、中是还要考察每个最优决策序列中是否包含一个最优决策子序列否包含一个最优决策子序列，即问题是否具有最优子结构性质。通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏；（6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。矩阵连乘问题-最优解的结构 将矩阵连乘积AiAi+1Aj记作Ai:j 把问题转化成考察把问题转化成考察A1:n的最优计算次序问题的最优计算次序问题 设计算次序在设计算次序在Ak处将矩阵断开最优，则总计处将矩阵断开最优，则总计算量为：算量为：A1:k 的计

17、算量加上的计算量加上Ak+1:n的计算的计算量，再加上量，再加上A1:k 和和Ak+1:n相乘的计算量。相乘的计算量。l关键特征关键特征lA1:n的最优计算次序所包含的计算矩阵子链A1:k和Ak+1:n的次序也是最优的问题的最优解包含了其子问题的最优解，这种性质称为最优子结构性质最优子结构性质。最优子结构性质是该问题可用动态规划算法求解的第一个标志最优子结构性质是该问题可用动态规划算法求解的第一个标志3-1 设计一个O(n2)时间的算法，找出由n个数组成的序列的 最长单调递增子序列。(1 3 2 5 7 6)分析与解答：分析与解答：设有n个数组成的序列存储在数组a中思路思路1：1、对a进行排序

18、，得到排序后的序列b 2、a和b的最长公共子序列就是题目所求的a 的最长单调递归子序列（可用反证法证明）时间复杂度分析时间复杂度分析：使用快速排序算法，时间复杂度O(n*logn)，而由书本第74页，可知用动态规划方法求解最长公共子序列的时间复杂度是O(n*m)，这里n=m，所以总的时间复杂度为O(n2)。思路思路2：直接使用动态规划求解1、找出具有最优解的性质，并刻画其结构特征 用数组b0:n-1记录以ai（0 in）为结尾元素的最长递归子序列的长度，可知序列a的最长递增子序列的长度为 ，可知bi满足最优子结构的性质。2、递归定义最优值时间复杂度分析时间复杂度分析：需用二重循环来计算bi的值

19、，使用一个循环来扫描a，以求解bi;而在求解bi的当中需要一个循环来扫描a0:i-1,查找小于ai的aj，因此该算法的时间复杂度为O(n2)。3-2 将习题3-1中的算法的计算时间减至O(n*logn)（提示：一个长度为i的候选子序列的最后一个元素至少与一个长度为i-1的候选子序列的最后一个元素一样大，通过指向输入序列中的元素的指针来维持候选子序列）。分析与解答：分析与解答：设有n个数组成的序列存储在数组a中。可用归纳设计策略解决这个问题。1、归纳假设归纳假设是，已知计算序列a0:i-1(in)的最长递增子序列的长度的正确算法。归纳的初始情况是平凡的。对于长度为n的序列a0:n-1,应设法转换

20、成为长度小于n的序列 2、用归纳设计策略解题时，归纳假设对应于算法循环中的循环不变式。本题的循环不变式循环不变式P是：P：k是序列a0:i的最长递增子序列的长度：0 iaj时可以扩展，否则不能扩展。4、考虑一个问题：考虑一个问题：如果序列a0:i-1中存在多个长度为k的递增子序列，那么需要存储那些信息？考虑：数组 1 3 2 5 4 7 5 10 9 容易看出，只需要存储序列a0:i-1中所有长度为k的递增子序列中结尾元素的最小值bk即可。因此，需要将循环不变式P增强为：P：0 in;k是序列a0:i的最长递增子序列的长度；bk 是序列a0:i中所有长度为k的递增子序列中的最小结尾元素值分析与

21、解答：分析与解答：5、相应的归纳假设增强为相应的归纳假设增强为：已知计算序列a0:i-1(ibk时候，k=k+1,bk=ai；否则k值不变。可得到bk值的变化：当aibk,k值增加,则bk=ai;否则k值不变；当aib1,则b1=ai;当b1=ai=bk，则查找下标j,使得bj-1=ai x，则问题归结为在缩短的序列A1.n-1中寻找解答；(2)若sx，则问题归结为在缩短的序列A2.n中寻找解答；(3)若s=x，则问题找到解答。对于上述情况(1)和(2)，在比原序列更短的序列上重复上述过程，直到找到问题的解答，或者缩短的序列长度为1 为止(此时表示原序列中没有两数之积为x).由于算法中最多只需

22、一次扫描序列中所有元素，而每扫描一个元素的操作时间为常数，故时间复杂度为O(n).53 理解贪心算法的一般理论 通过应用范例学习贪心设计策略。（1）活动安排问题；（2）最优装载问题；（3）哈夫曼编码；（4）单源最短路径；（5）最小生成树；（6）多机调度问题。贪心算法(greedy algorithm)：作出在当前看来最好的选择 贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优局部最优选择。希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得

23、到整体最优解，其最终结果却是最优解的很好近似。贪心算法的基本要素 本节着重讨论可以用贪心算法求解的问题的一般特征。对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?一般需具有2个重要的性质：贪心选择性质贪心选择性质和最优子结构性质最优子结构性质。贪心选择性质贪心选择性质所谓贪心选择性质贪心选择性质是指所求问题的整体最优解整体最优解可以通过一系列局部最优局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心选择：只考虑对当前问题的最佳选择，不是考虑子问题的结果。动态规划：每一步都要选择，选择依赖每一个子问题的

24、解；动态规划算法通常以自底向上自底向上的方式解各子问题，而贪心算法则通常以自顶向下自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对每个贪心算法，几乎总是会有一个相对更复杂的动态规划解。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。贪心选择性质的确定 贪心选择性质的确定贪心选择性质的确定 对于一个具体问题，要考察该问题是否具有贪心选择性质，必须证明每一步所做出的贪心选择最终将获得问题的整体最优解。通常可以用类似于证明活动安排问题的贪心选择时所采用的方法来证明。首先考察问题的一个整体最

25、优解，并证明可修改这个最优解，使其以贪心选择开始。在做出贪心选择后，原问题简化为规模更小的类似子问题。用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的全局最优解。贪心算法的基本要素 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。在活动安排问题中，最优子结构的性质表现在：若A是关于E的活动安排问题包含活动1的一个最优解，则相容活动集合A=A-1是关于E=iE:sif1的活动安排问题的一个最优解。最优子结构性质最优子结构性质 贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2

26、类算法的一个共同点。对于具有最优子结构最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?贪心算法与动态规划算法的差异 习题4.1 设有n个正整数，将他们连接成一排，组成一个最大的多位整数。例如:n=3时，3个整数13,312,343,连成的最大整数为:34331213。又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613 请分析其是否满足贪心选择策略、最优子结构，写出算法的伪代码var s:array1.20 of string;t:string;i,j,k,n:longint;begin readln(n);for

27、 i:=1 to n do begin read(k);str(k,si);end;for i:=1 to n-1 do for j:=i+1 to n do if si+sjsj+si then begin交换 t:=si;si:=sj;sj:=t;end;for i:=1 to n do write(si);end.习题4.2 试证明若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列，则用贪心算法可以找出其最优解。首先将各物品依重量递增序（即也是价值递减序）排列，然后依照价值递减顺序选择物品装入背包，直到背包装不下下一件物品为止。这里贪心算法的贪心选择策略是：每次总是选择

28、价值最大（同时重量也最小）的物品，然后检查是否可以装入背包。习题4.4 A驾驶着红旗牌轿车沿着107国道从深圳开往北京。A的车加满油时，可以跑公里。A有一张地图，标出了沿途中加油站之间的距离。为节省时间，A希望在路途中尽量地少加油。请设计出一个有效算法帮助A决定该在那些加油站加油，并证明你的算法能够得到最优解。解：根据实际问题，加油站之间距离不等，若要使加油次数最少，只需做到如果车内的油能够到达下一站点就不加油，即做贪心选择。正确性证明：站点分别记为1,2,n，站点集合记为A，只需证明问题贪心算法的正确性，即满足贪心选择和优化子结构即可。贪心选择：设从初始位置最远可以前行到i站点，则存在最优选

29、择M，M前行到i站点首次加油。M前行到i站点首次加油，问题得证。若M不前行至i站点进行加油，在加油站j进行首次加油，易得ji，存在加油组合N，使N中除第一个加油站点外，剩余的加油站点均一致。因为就ji，故从j站点可以到达的下一加油站k从i站点也可以同样到达。故加油次数Count(M)=Count(N)，故N也为最优选择，问题得证。最优子结构：设最优选择M包含从初始位置前行到i站点首次加油，只需证M-i为A-1,2，i 的最优选择。如果M-i不是A-1,2，i 的最优选择，其最优选择为N,则Count(N)Count(M-i)在分别加上在i站点的加油次数得：1+Count(N)1+Count(M

30、-i)=Count(M)这与M是最优选择矛盾，故M-i为A-1,2，i 的最优选择。所以方案是正确的。第5章 回溯法问题的解空间 问题的解空间问题的解空间 应明确问题的解空间的定义应明确问题的解空间的定义 问题的解空间至少应包含问题的一个（最优解）。对问题解空间进行组织对问题解空间进行组织 通常组织为树或图的形式。有利于回溯法对整个解空间的搜索回溯法的基本思想 回溯法的基本思想回溯法的基本思想 在确定解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索深度优先方式搜索整个解空间。这个开始结点成为活结点活结点，同时也成为当前的扩展结点当前的扩展结点。在当前扩展结点处，搜索向纵深

31、方向移至一个新结点。这个新结点成为新的活结点，并成为扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点死结点。此时，应往回移动（回溯）往回移动（回溯）到最近的活结点处，并使该结点成为当前的扩展结点。回溯法按上述方式递归递归地在解空间中搜索，直到找到所直到找到所要求的解或解空间中以误活结点为止要求的解或解空间中以误活结点为止。如何避免回溯法的无效搜索 如何避免回溯法的无效搜索如何避免回溯法的无效搜索 用约束函数在扩展结点处剪去不满足约束的子树；见0-1背包问题 用限界函数剪去得不到最优解的子树；见TSP问题以上两类函数统称为剪枝函数剪枝函数回溯法的主要步骤 回溯法的主

32、要步骤回溯法的主要步骤 针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。实例分析 旅行商问题旅行商问题 符号三角形问题 皇后问题皇后问题 最大团问题 图的着色问题图的着色问题 圆排列问题 电路板排列问题电路板排列问题 连续邮资问题连续邮资问题 有4个城市的旅行商问题，其费用矩阵如图所示，矩阵的每个元素aij分别为相应i到j城市的旅费代价，表示无意义或无通路。求从第一个城市出发，最后回到城市1的最短路线。请画出解空间树，给出最优解。设计一个回溯算法，确定是否k个王后能够攻击一个n*n 棋盘的所有位置。3、用回溯算法，请画出

33、搜索树，说明最短路径的搜索过程。第6章 分支限界法分支限界法 分支限界法分支限界法 与回溯法类似，都是在问题的解空间树上搜索问题解的算法；求解目标：找出满足约束条件的解 可行解可行解或最优解最优解 搜索策略 根据限界函数值，剔除那些导致不可行解或非最优解的子结点，使搜索过程仅限制在剩余的分支内进行；分支限界法 VS 回溯法 相同点：相同点：两者在进行问题求解前，都需要完成解空间的需要完成解空间的定义和组织定义和组织；都是通过在解空间搜索来寻找问题的解在解空间搜索来寻找问题的解；回溯法和分支限界法的：共同之处：用于解空间的搜索；可作为通用问题求解方法；通过约束剪裁解空间的结点，减小搜索空间；区别

34、之处：采用的数据结构：堆栈VS队列（优先队列、堆）搜索方法：深度优先VS广度优先（额外优先函数）通常的应用：寻找满足约束-所有解VS一个解（或特定前提下的最优解）消耗的存储空间：深度优先算法只需要记录堆栈中的结点；广度优先算法需要保存的结点数较多，需考虑溢出和节约内存空间，但运行速度更快；分支限界法 VS 回溯法 不同点：不同点：搜索方式搜索方式 回溯法：深度优先深度优先；分支限界法：广度优先广度优先；搜索策略搜索策略 回溯法：根据剪枝函数，选择下一个扩展接点并按深度优先方式进行搜索；分支限界法：在扩展结点处，先产生其所有的子结点（分支），然后根据限界函数，确定哪些子结点将导致不可行解或非最优

35、解，将这些子结点剔除，用剩下的子结点构造当前的活结点表，然后从该表中取一个结点作为当前扩展结点，并重复上述过程；分支限界法的主要分类 分支限界法的主要分类分支限界法的主要分类 根据从活结点表中选择下一个扩展结点的方式 队列式队列式FIFO分支限界法分支限界法 算法思想：算法思想：将活结点表组织成一个队列，并按队列的先进先出FIFO原则选取下一个结点作为当前扩展结点；优先队列式分支限界法优先队列式分支限界法 算法思想：算法思想：将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级，选取剩余队列中优先级最高的下一个结点作为当前扩展结点；简述使用分枝限界法求解问题的基本思路。与回溯法相比，它

36、有何优势，和有何不足？答：分枝限界法的基本思想是：宽度优先搜索（优先队列搜索）+剪枝。即，通过对搜索树进 行宽度优先搜索来寻找问题的解答，且在搜索中每搜索到一个结点处，都要考虑是否能使用 剪枝操作来剪枝，从而提高搜索效率。与回溯法相比，这种搜索方法具有更大的灵活 性（搜索跳跃性更大），但是往往需要比回溯法多得多的空间。分治法通过把问题化为较小的问题来解决原问题，从而简化或减少了原问题的复杂度；贪心法通过分阶段地挑选最优解，较快地得到整体的较好解，在问题要求不太严格的情况下，可以用这个较优解替代需要穷举所有情况才能得到的最优解；动态规划法用填表的方法保存了计算的中间结果，从而避免了大量重复的计算

37、；回溯法跳过大量无须测试的元组，很快地得到需要的解。分枝界限法是在系统搜索问题解的空间时，加入上下界的条件检查以达到有效剪枝的目的。2-6章的总结 这些方法的共同之处是运用技巧避免穷举测试。分治法和动态规划法都是将问题分成子问题来做的；贪心法、动态规划法以及回溯法都是从某一集合中选出子集，通过一系列的判定来得到解；贪心法、分枝界限法和回溯法都要进行逐项的测试比较逐步达到整个解；动态规划法和回溯法都是逐步逼近最优解而最终得到满足条件的解。分枝界限法、动态规划法和回溯法可以得到问题的最优解；贪心法既可能得到次优解，也可能得到最优解，依赖于具体问题的特点和贪心策略的选取。对于某一问题来说，能用不同的

38、设计技巧得到不同的算法。一个算法中，也可以结合使用几种算法设计技巧。如快速排序算法是分治的技巧和回溯的技巧的结合，其中分治的技巧是主要的。思考与比较：对TSP问题，分治、贪心、动态规划算法可以获得解吗？能寻找最优解吗？子问题的数量惊人；用动态规划算法求解，要保存各个子问题的解，将消耗巨大的存储空间；什么样的问题适合用回溯法和分支限界法获得解，而不适合用以上三种方法解决？222812 使用最优队列分支限界法，用类似贪心策略的方式选择解的搜索方向，可以尽快找到近似最优解；由于在搜索到某个层面发现解不够优，还可以从更低的树层次获得问题的更优解，因而能获得比贪心算法更优的解；概率算法的主要类型 概率算法的主要类型概率算法的主要类型 数值概率算法：求值；蒙特卡罗算法：求主元素；拉斯维加斯算法：求解n皇后问题；舍伍德算法：快速排序法的改进；考虑产生 1,2,n.的一个随机排列。请简要描述一个时间复杂度为 O(n)的随机算法的思路。答：答：一种随机算法的基本思路是：先初始化 Ai=i，1in；然后用线性同余法生成随机数，根据随机数在 A 中依次选两个元素 出来交换，此操作执行 n 次。显然，这种算法的时间复杂度为O(n)。不要求看懂所有代码，而是要求搞清楚算法的思路，知道如何用伪代码说明；