0算法设计与分析-算法汇总概述

1、主讲：白静主讲：白静Email: Email: 算法设计与分析算法设计与分析- -算法汇总算法汇总2022-5-4算法设计与分析2第一部分第一部分：问题集锦：问题集锦2022-5-4算法设计与分析3问题问题问题描述问题描述搜索排好序的数组中找到某个特定元素x排序对n个元素进行排序大整数乘法x、y都是n位的二进制整数，计算它们的乘积XYStrassen矩阵乘法A、B是两个n*n矩阵，求解它们的成绩AB矩阵连乘矩阵连乘的最优计算次序问题（加括号问题）棋盘覆盖用L型骨牌覆盖特定的特殊棋盘2k*2k（包含一个不同方格）最接近点对给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的

2、距离最小循环赛日程表设有n=2k个运动员进行网球循环赛。设计一个比赛日程表，满足1）每个选手必须与其他n-1个选手各赛一次；2）每个选手一天只能赛一次；3）循环赛一共进行n-1天最长公共子序列给定两个序列X=x1，x2，xm和Y=y1，y2，yn，找出X和Y的最长公共子序列凸多边形最优三角剖分给定凸多边形P=v0,v1,vn-1,以及定义在由多边形的边和弦组成的三角形上的权函数W。要求确定该凸多边形的三角剖分，使得该三角剖分所对应的权，即该三角剖分中诸三角形上权之和为最小。圆排列给定n个大小不等的圆c1，c2,Cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从

3、n个圆的所有排列中找出有最小长度的圆排列连续邮资n中不同面值的邮票，每张信封上最多允许贴m张邮票，给出邮票面值的最佳设计，使邮封上可提出最大连续邮资。2022-5-4算法设计与分析4问题问题0-1背包问题背包问题活动安排问题最优装载装载问题哈夫曼编码单源最短路径旅行售货员最小生成树多机调度流水作业调度批处理作业调度符号三角形n后问题最大团问题图的m着色线性时间选择给定线性序集中n个元素和一个整数k，要求找出这n个元素中第k小的元素2022-5-4算法设计与分析5第二部分：算法集锦第二部分：算法集锦2022-5-4算法设计与分析6算法算法一句话描述一句话描述递归算法循环调用自己的算法分治算法大问

4、题分割为小问题，一直分解到非常容易求解的问题，再通过合并算法合并求出大问题的解贪心算法优化问题，总是做出当前看来最好的选择。该类问题往往具有贪心选择性质及最优子结构性质贪心选择：所求问题的整体最优解可以通过一系列局部最优的选择，及贪心选择来达到。反正，如果A是最优解，A包含当前最优选择，本来就满足；否则，将A中某个选择替换为当前最优选择，仍然满足最优解。最优子结构性质：一个问题的最优解包含其子问题的最优解。动态规划 优化问题，递推中往往包含min，max，即当前【i,j】规模的问题往往可以转换为min(【i,k】+【k+1,j】+v(k,k+1)动态规划问题满足最优子结构性质回溯法通用解题法。

5、既带有系统性又带有跳跃性。找出满足约束条件的所有解。深度优先搜索。盲目搜索。系统性：体现为子集树或排列树的构造跳跃性：体现为子树的剪枝，包括约束性剪枝（不满足约束条件）和限界性剪枝（得不到最优解剪枝）分支限界法找出满足约束条件的一个解。广度优先搜索或最小耗费优先搜索。启发式搜索。概率算法近似算法基本思想分析-回溯法&分支限界法回溯法：首先确定解空间的组织结构, 接着就从开始结点(根结点) 出发, 以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点, 同时也成为当前的扩展结点。在当前的扩展结点处, 搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点, 并成为当前扩展结

6、点。如果在当前的扩展结点处不能再向纵深方向移动, 则当前扩展结点就成为死结点。换句话说, 这个结点不再是一个活结点。此时, 应往回移动(回溯) 至最近的一个活结点处, 并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索, 直至找到所要求的解或解空间中已没有活结点时为止分支限界法：确定解空间的组织结构, 以广度优先或以最小耗费(最大效益) 优先的方式搜索问题的解空间树。在搜索问题的解空间树时, 分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中, 每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点, 就一次性产生其所有儿子结点。在这些儿子结点

7、中, 那些导致不可行解或导致非最优解的儿子结点被舍弃, 其余儿子结点被子加入活结点表中。此后, 从活结点表中取下一结点成为当前扩展结点, 并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。7用法比较-回溯法&分支限界法分支限界法类似于回溯法, 也是一种在问题的解空间树T 上搜索问题解的算法。但在一般情况下, 分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T 中满足约束条件的所有解, 而分支限界法的求解目标则是找出满足约束条件的一个解, 或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解, 即在某种意义下的最优解。由于求解目标不同, 导致分

8、支限界法与回溯法在解空间树T 上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T, 而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索策略是: 在扩展结点处, 先生成其所有的儿子结点(分支), 然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点, 以加速搜索的进程,在每一活结点处, 计算一个函数值(限界) , 并根据这些已计算出的函数值, 从当前活结点表中选择一个最有利的结点作为扩展结点, 使搜索朝着解空间树上有最优解的分支推进, 以便尽快地找出一个最优解 。8用法比较-回溯法&分支限界法分支限界法常以广度优先或以最小耗费(最大效

9、益) 优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树, 常见的有子集树和排列树。在搜索问题的解空间树时, 分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中, 每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点, 就一次性产生其所有儿子结点。在这些儿子结点中, 那些导致不可行解或导致非最优解的儿子结点被舍弃, 其余儿子结点被子加入活结点表中。此后, 从活结点表中取下一结点成为当前扩展结点, 并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。9用法举例-回溯法&分支限界法( 1) 一个比较适合采用回溯法解决的

10、问题- n后问题。在n* n的国际象棋棋盘上摆下n个后, 使所有的后都不能攻击到对方, 找出所有符合要求的情况。n后问题的解空间树是一棵排列树, 一旦一种组合是一种解, 则解与解之间不存在优劣的分别。直到搜索到叶节点时才能确定出一组解。这时我们用回溯法可以系统地搜索问题的全部解, 而且由于解空间树是排列树的特性, 在最坏的情况下,堆栈的深度不会超过n。如果采取分支限界法, 在解空间树的第一层就会产生n个活结点, 如果不考虑剪枝, 将在第二层产生n* ( n - 1) 个活节点, 如此下去对队列空间的要求太高。n后问题不适合使用分支限界法处理的根源是它需要找处所有解的组合, 而不是某种最优解(事

11、实上也没有最优解可言)。形象一点来说, 如果让人工解决n后问题, 人们的思路应该是放一个后, 看是否冲突, 若不冲突放下一个, 冲突则改变位置, 这样可以只用一个棋盘而且有规律地找到所有符合条件的情况, 这正是回溯法的模拟过程。然而分支限界法则可以被这样表述。拿来一个棋盘, 摆下一只后; 再拿一个棋盘, 再摆一只; 待到每个棋盘都有一只后以后, 每个棋盘又被分解成更多的盘面. . . , 这样, 棋盘越来越多, 但是由于解和解(包括局部解) 之间缺乏因果和限制的联系。棋盘之间并不能根据对方的信息获得什么, 这显然是对资源的浪费。10用法举例-回溯法&分支限界法( 1) 一个比较适合采用

12、回溯法解决的问题- n后问题。在n* n的国际象棋棋盘上摆下n个后, 使所有的后都不能攻击到对方, 找出所有符合要求的情况。n后问题的解空间树是一棵排列树, 一旦一种组合是一种解, 则解与解之间不存在优劣的分别。直到搜索到叶节点时才能确定出一组解。这时我们用回溯法可以系统地搜索问题的全部解, 而且由于解空间树是排列树的特性, 在最坏的情况下,堆栈的深度不会超过n。如果采取分支限界法, 在解空间树的第一层就会产生n个活结点, 如果不考虑剪枝, 将在第二层产生n* ( n - 1) 个活节点, 如此下去对队列空间的要求太高。n后问题不适合使用分支限界法处理的根源是它需要找处所有解的组合, 而不是某

13、种最优解(事实上也没有最优解可言)。形象一点来说, 如果让人工解决n后问题, 人们的思路应该是放一个后, 看是否冲突, 若不冲突放下一个, 冲突则改变位置, 这样可以只用一个棋盘而且有规律地找到所有符合条件的情况, 这正是回溯法的模拟过程。然而分支限界法则可以被这样表述。拿来一个棋盘, 摆下一只后; 再拿一个棋盘, 再摆一只; 待到每个棋盘都有一只后以后, 每个棋盘又被分解成更多的盘面. . . , 这样, 棋盘越来越多, 但是由于解和解(包括局部解) 之间缺乏因果和限制的联系。棋盘之间并不能根据对方的信息获得什么, 这显然是对资源的浪费。11用法举例-回溯法&分支限界法( 2)一个既

14、可以采用回溯法也可以采用分支限界法解决的问题-0- 1背包问题。给定若干物品的重量和价值, 以及一个背包的容量上限。求出一种方案使得背包中存放物品的价值最高。这个问题除了可以考虑回溯法和分支限界法之外, 还可以用动态规划的方法解决,但在这里我们主要讨论前两种方法的对比。0- 1背包问题的解空间树是一棵子集树, 所要求的解具有最优性质。如果采用回溯法解决这个问题, 可采用如下的搜索策略: 只要一个结点的左儿子结点是一个可行结点就搜索其左子树; 而对于右子树, 需要用贪心算法构造一个上界函数 这个函数表明这个结点的子树所能达到的可能的最大容量(因为只有将0- 1背包问题改变为背包问题才可能利用贪心

15、算法, 因此这个上界函数在绝大多数情况下不会是上确界函数), 只在这个上界函数的值超过当前最优解时才进入搜索。随着搜索进程的推进,最优解不断得到加强, 对搜索的限制就越来越严格。如果采用分支限界法解决这个问题, 同样需要用到贪心算法构造的上界函数。所不同的是,这个上界函数的作用不在于判断是否进入一个结点的子树继续搜索, 因为在搜索到达叶节点之前,大家也无法知道已经得到的最优解是什么。在这里, 可用一个最大堆来实现活结点的优先队列,上界函数的值将作为优先级, 这样一旦有一个叶结点成为扩展结点, 就表明已经找到了最优解。12可以看出, 用两种方法处理0- 1背包问题都有一定的可行性。相比之下回溯法

16、的思路容易理解一些, 但是这是一个寻找最优解的问题。由于采用了优先队列处理, 不同的结点不再像n 后问题那样没有相互之间的牵制和联系, 用分支限界法处理效果一样很好。用法举例-回溯法&分支限界法(3)一个比较适合采用分支限界法解决的问题 布线问题。印刷电路板将布线区域划分成n* m 个方格阵列如图1。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案如图2。在布线时, 电路只能沿直线或直角布线。为了避免线路相交, 已布了线的方格做了封锁标记, 其他线路不允许穿过被封锁的方格。13布线问题的解空间是一个图, 适合采用队列式分支限界法来解决。从起始位置a开始将它作为第一个扩展结点。与该结点相邻并且可达的方格被加入到活结点队列中, 并且将这些方格标记为1,表示它们到a的距离为1。接着从活结点队列中取出队首作为下一个扩展结点, 并将与当前扩展结点相邻且未标记过的方格标记为2, 并存入活节点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止(表示没有通路) 如图3。现在我