算法设计与分析算法汇总概述.ppt

主讲：白静Email:算法设计与分析-算法汇总2023/5/31算法设计与分析2第一局部：问题集锦2023/5/31算法设计与分析3问题 问题描述搜索排好序的数组中找到某个特定元素x排序对n 个元素进行排序大整数乘法x、y 都是n 位的二进制整数，计算它们的乘积XYStrassen 矩阵乘法 A、B 是两个n*n 矩阵，求解它们的成绩AB矩阵连乘 矩阵连乘的最优计算次序问题（加括号问题）棋盘覆盖用L型骨牌覆盖特定的特殊棋盘2k*2k（包含一个不同方格）最接近点对给定平面上n 个点，找其中的一对点，使得在n 个点组成的所有点对中，该点对间的距离最小循环赛日程表设有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 个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n 个圆的所有排列中找出有最小长度的圆排列连续邮资n 中不同面值的邮票，每张信封上最多允许贴m 张邮票，给出邮票面值的最佳设计，使邮封上可提出最大连续邮资。2023/5/31算法设计与分析4问题0-1 背包问题背包问题活动安排问题最优装载装载问题哈夫曼编码单源最短路径旅行售货员最小生成树多机调度流水作业调度批处理作业调度符号三角形n 后问题最大团问题图的m 着色线性时间选择给定线性序集中n 个元素和一个整数k，要求找出这n 个元素中第k 小的元素2023/5/31算法设计与分析5其次局部：算法集锦2023/5/31算法设计与分析6算法 一句话描述递归算法 循环调用自己的算法分治算法 大问题分割为小问题，一直分解到非常容易求解的问题，再通过合并算法合并求出大问题的解贪心算法 优化问题，总是做出当前看来最好的选择。该类问题往往具有贪心选择性质及最优子结构性质贪心选择：所求问题的整体最优解可以通过一系列局部最优的选择，及贪心选择来达到。反正，如果A 是最优解，A包含当前最优选择，本来就满足；否则，将A 中某个选择替换为当前最优选择，仍然满足最优解。最优子结构性质：一个问题的最优解包含其子问题的最优解。动态规划 优化问题，递推中往往包含min，max，即当前【i,j】规模的问题往往可以转换为min(【i,k】+【k+1,j】+v(k,k+1)动态规划问题满足最优子结构性质回溯法 通用解题法。既带有系统性又带有跳跃性。找出满足约束条件的所有解。深度优先搜索。盲目搜索。系统性：体现为子集树或排列树的构造跳跃性：体现为子树的剪枝，包括约束性剪枝（不满足约束条件）和限界性剪枝（得不到最优解剪枝）分支限界法 找出满足约束条件的一个解。广度优先搜索或最小耗费优先搜索。启发式搜索。概率算法近似算法根本思想分析-回溯法&分支限界法 回溯法：首先确定解空间的组织构造,接着就从开头结点(根结点)动身,以深度优先的方式搜寻整个解空间。这个开头结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜寻向纵深方向移至一个新结点。这个新结点就成为一个新的活结点,并成为当前扩展结点。假设在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。换句话说,这个结点不再是一个活结点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜寻,直至找到所要求的解或解空间中已没有活结点时为止 分支限界法：确定解空间的组织构造,以广度优先或以最小消耗(最大效益)优先的方式搜寻问题的解空间树。在搜寻问题的解空间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中,每一个活结点只有一次时机成为扩展结点。活结点一旦成为扩展结点,就一次性产生其全部儿子结点。在这些儿子结点中,那些导致不行行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子参加活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程始终持续到找到所求的解或活结点表为空时为止。7用法比较-回溯法&分支限界法 分支限界法类似于回溯法,也是一种在问题的解空间树T 上搜寻问题解的算法。但在一般状况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T 中满足约束条件的全部解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出访某一目标函数值到达极大或微小的解,即在某种意义下的最优解。由于求解目标不同,导致分支限界法与回溯法在解空间树T 上的搜寻方式也不一样。回溯法以深度优先的方式搜寻解空间树T,而分支限界法则以广度优先或以最小消耗优先的方式搜寻解空间树T。分支限界法的搜寻策略是:在扩展结点处,先生成其全部的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点,以加速搜寻的进程,在每一活结点处,计算一个函数值(限界),并依据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜寻朝着解空间树上有最优解的分支推动,以便尽快地找出一个最优解。8用法比较-回溯法&分支限界法 分支限界法常以广度优先或以最小消耗(最大效益)优先的方式搜寻问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。在搜寻问题的解空间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中,每一个活结点只有一次时机成为扩展结点。活结点一旦成为扩展结点,就一次性产生其全部儿子结点。在这些儿子结点中,那些导致不行行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子参加活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程始终持续到找到所求的解或活结点表为空时为止。9用法举例-回溯法&分支限界法(1)一个比较适合承受回溯法解决的问题-n 后问题。在n*n 的国际象棋棋盘上摆下n 个后,使全部的后都不能攻击到对方,找出全部符合要求的状况。n 后问题的解空间树是一棵排列树,一旦一种组合是一种解,则解与解之间不存在优劣的分别。直到搜寻到叶节点时才能确定出一组解。这时我们用回溯法可以系统地搜寻问题的全部解,而且由于解空间树是排列树的特性,在最坏的状况下,堆栈的深度不会超过n。假照实行分支限界法,在解空间树的第一层就会产生n 个活结点,假设不考虑剪枝,将在其次层产生n*(n-1)个活节点,如此下去对队列空间的要求太高。n 后问题不适合使用分支限界法处理的根源是它需要找处全部解的组合,而不是某种最优解(事实上也没有最优解可言)。形象一点来说,假设让人工解决n 后问题,人们的思路应当是放一个后,看是否冲突,假设不冲突放下一个,冲突则转变位置,这样可以只用一个棋盘而且有规律地找到全部符合条件的状况,这正是回溯法的模拟过程。然而分支限界法则可以被这样表述。拿来一个棋盘,摆下一只后;再拿一个棋盘,再摆一只;待到每个棋盘都有一只后以后,每个棋盘又被分解成更多的盘面.,这样,棋盘越来越多,但是由于解和解(包括局部解)之间缺乏因果和限制的联系。棋盘之间并不能依据对方的信息获得什么,这明显是对资源的铺张。10用法举例-回溯法&分支限界法(1)一个比较适合承受回溯法解决的问题-n 后问题。在n*n 的国际象棋棋盘上摆下n 个后,使全部的后都不能攻击到对方,找出全部符合要求的状况。n 后问题的解空间树是一棵排列树,一旦一种组合是一种解,则解与解之间不存在优劣的分别。直到搜寻到叶节点时才能确定出一组解。这时我们用回溯法可以系统地搜寻问题的全部解,而且由于解空间树是排列树的特性,在最坏的状况下,堆栈的深度不会超过n。假照实行分支限界法,在解空间树的第一层就会产生n 个活结点,假设不考虑剪枝,将在其次层产生n*(n-1)个活节点,如此下去对队列空间的要求太高。n 后问题不适合使用分支限界法处理的根源是它需要找处全部解的组合,而不是某种最优解(事实上也没有最优解可言)。形象一点来说,假设让人工解决n 后问题,人们的思路应当是放一个后,看是否冲突,假设不冲突放下一个,冲突则转变位置,这样可以只用一个棋盘而且有规律地找到全部符合条件的状况,这正是回溯法的模拟过程。然而分支限界法则可以被这样表述。拿来一个棋盘,摆下一只后;再拿一个棋盘,再摆一只;待到每个棋盘都有一只后以后,每个棋盘又被分解成更多的盘面.,这样,棋盘越来越多,但是由于解和解(包括局部解)之间缺乏因果和限制的联系。棋盘之间并不能依据对方的信息获得什么,这明显是对资源的铺张。11用法举例-回溯法&分支限界法(2)一个既可以承受回溯法也可以承受分支限界法解决的问题-0-1 背包问题。给定假设干物品的重量和价值,以及一个背包的容量上限。求出一种方案使得背包中存放物品的价值最高。这个问题除了可以考虑回溯法和分支限界法之外,还可以用动态规划的方法解决,但在这里我们主要争论前两种方法的比照。0-1 背包问题的解空间树是一棵子集树,所要求的解具有最优性质。假设承受回溯法解决这个问题,可承受如下的搜寻策略:只要一个结点的左儿子结点是一个可行结点就搜寻其左子树;而对于右子树,需要用贪心算法构造一个上界函数 这个函数说明这个结点的子树所能到达的可能的最大容量(由于只有将0-1 背包问题转变为背包问题才可能利用贪心算法,因此这个上界函数在绝大多数状况下不会是上确界函数),只在这个上界函数的值超过当前最优解时才进入搜寻。随着搜寻进程的推动,最优解不断得到加强,对搜寻的限制就越来越严格。假设承受分支限界法解决这个问题,同样需要用到贪心算法构造的上界函数。所不同的是,这个上界函数的作用不在于推断是否进入一个结点的子树连续搜寻,由于在搜寻到达叶节点之前,大家也无法知道已经得到的最优解是什么。在这里,可用一个最大堆来实现活结点的优先队列,上界函数的值将作为优先级,这样一旦有一个叶结点成为扩展结点,就说明已经找到了最优解。12可以看出,用两种方法处理0-1 背包问题都有肯定的可行性。相比之下回溯法的思路简洁理解一些,但是这是一个查找最优解的问题。由于承受了优先队列处理,不同的结点不再像n 后问题那样没有相互之间的牵制和联系,用分支限界法处理效果一样很好。用法举例-回溯法&分支限界法(3)一个比较适合承受分支限界法解决的问题 布线问题。印刷电路板将布线区域划分成n*m 个方格阵列如图1。准确的电路布线问题要求确定连接方格a 的中点到方格b 的中点的最短布线方案如图2。在布线时,电路只能沿直线或直角布线。为了避开线路相交,已布了线的方格做了封锁标记,其他线路不允许穿过被封锁的方格。13 布线问题的解空间是一个图,适合承受队列式分支限界法来解决。从起始位置a 开头将它作为第一个扩展结点。与该结点相邻并且可达的方格被参加到活结点队列中,并且将这些方格标记为1,表示它们到a 的距离为1。接着从活结点队列中取出队首作为下一个扩展结点,并将与当前扩展结点相邻且未标记过的方格标记为2,并存入活节点队列。这个过程始终连续到算法搜寻到目标方格b 或活结点队列为空时为止(表示没有通路)如图3。现在我们来考虑,为什么这个问题用回溯法来处理就是相当低效的。回溯法的搜寻是依据深度优先的原则进展的,假设把上下左右四个方向规定一个固定的优先挨次去进展搜寻,搜寻会沿着某个路径始终进展下去直到碰壁才换到另一个子路径,但是一开头根本无法推断正确的路径方向是什么,这就造成了搜寻的盲目和铺张。更为致命的是,即使我们搜寻到了一条由a至b 的路径,也无法保证它就是全部路径中最短的。这要求我们必需把整个区域的全部路径逐一搜寻后才能得到最优解如图4。正由于如此,布线问题不适合用回溯法解决。2023/5/31算法设计与分析14