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