《[其它]Algorithm 03.ppt》由会员分享，可在线阅读，更多相关《[其它]Algorithm 03.ppt（33页珍藏版）》请在三一办公上搜索。
1、算法分析与设计Analysis and Design of Computer Algorithms,第三章 蛮力法Brute Force,2,蛮力法,就像宝剑不是撬棍一样，科学也很少使用蛮力。Edward Lytton认真做事常常是浪费时间。Robert Byrne蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。,3,蛮力法的优点,可以用来解决广阔领域的问题对于一些重要的问题，它可以产生一些合理的算法解决问题的实例很少时，它让你花费较少的代价可以解决一些小规模的问题可以作为其他高效算法的衡量标准,4,教学内容,选择排序和冒泡排序顺序查找和蛮力字符串匹配最近对核凸
2、包问题的蛮力算法穷举查找要求掌握蛮力法的基本思想，了解排序和查找问题的蛮力算法。,5,选择排序,Amin,6,冒泡排序,算法 BubbleSort(A0.n-1)/该算法用冒泡排序对数组A0.n-1排序/输入：一个可排序的数组A/输出：非降序排列的数组for i0 to n-2 do for j0 to n-2-i do if Aj+1Aj swap Aj and Aj+1,7,顺序查找,8,蛮力字符串匹配,9,蛮力字符串匹配,(n+m)=(n),10,最近对问题,11,凸包问题,定义 对于平面上的一个点集合（有限或无限），如果以集合中任意两点P和Q为端点的线段都属于这个集合，则这个集合是凸的
3、。定义 一个点集合S的凸包是包含S的最小凸集合。,12,凸包问题,定理 任意包含n2个点（不共线）的集合S的凸包是以S中的某些点为顶点的凸多边形。凸包问题是为一个n个点的集合构造凸包的问题。极点：对于任何一集合中的点为端点的线段来说，它们不是这种线段的中点。,对于一个n个点集合中的两个点Pi和Pj，当且仅当该集合中的其他点都位于穿过这两点的直线的同一边时它们的连线是该集合凸包边界的一部分。,直线方程：ax+by=ca=y2-y1,b=x1-x2,c=x1y2-y1x2,13,穷举查找,旅行商问题,穷举查找,背包问题,14,0-1背包问题,问题描述：给定n 种物品和一背包。物品i 的重量是i w
4、，其价值为i v，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2 种选择，即装入背包或不装入背包。不能将物品i 装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。此问题的形式化描述是，给定 要求找出n 元0-1向量 使得 而且 达到最大。因此，0-1背包问题是一个特殊的整数规划问题。,编程任务：设计并实现解0-1背包问题的分支限界法。,数据输入：由文件input.txt提供输入数据。文件第1 行有2 个正整数n 和C，分别表示有n种物品，背包的容量为C。接下来的2 行中，每行有n 个数，分别表示各物品
5、的价值和重量。,结果输出:程序运行结束时，将最佳装包方案，及其最大价值输出到文件output.txt 中。文件的第1 行是最大价值，第2 行是最佳装包方案。,输入文件示例input.txt5 106 3 5 4 62 2 6 5 4,输出文件示例output.txt151 1 0 0 1,分支限界问题分析,分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种
6、意义下的最优解。,由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问
7、题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。,0-1背包问题的解空间树是一棵子集树，所要求的解具有最优性质。,如果我们采用回溯法解决这个问题，我们采用如下的搜
8、索策略：只要一个结点的左儿子结点是一个可行结点就搜索其左子树；而对于右子树，我们需要用贪心算法构造一个上界函数(这个函数表明这个结点的子树所能达到的可能的最大容量)，只在这个上界函数的值超过当前最优解时才进入搜索。随着搜索进程的推进，最优解不断得到加强，对搜索的限制就越来越严格。,如果我们采用分支限界法解决这个问题，同样需要用到贪心算法构造的上界函数，所不同的是，这个上界函数的作用不在于判断是否进入一个结点的子树继续搜索，因为在搜索到达叶节点之前，我们也无法知道已经得到的最优解是什么。在这里，我们用一个最大堆来实现活结点的优先队列，上界函数的值将作为优先级，这样一旦有一个叶结点成为扩展结点，就
9、表明已经找到了最优解。,穷举查找,分配问题N个任务分配给n个人，任务j分配给人i的成本是CI,j,24,25,小结,蛮力法是一种简单直接地解决问题的方法，通常直接基于问题的描述和所涉及的概念定义。蛮力法的主要优点是它广泛的适用性和简单性；它的主要缺点是大多数蛮力算法的效率都不高。除了相关问题的一些规模非常小的实例，穷举查找法几乎是不实用的。,习题3.2-10 找词游戏,习题3.4-9 幻方,幻方是我国古代的一种智力游戏，它是在N N 的矩阵方格中填入1.N 2 的正整数，使得其每行每列及对角线的和相等。很明显，这个和对某一阶幻方是一个定值。设此值为SN，则不难解出：SN=N 2(N 2+1)/
10、2N=N(N 2+1)/2。magic square,HCoxeter构造幻方的方法,首先在正方形最上面一行的正中间的小方格内填写1，然后到它的左上方的小格内填写下一个数(注意：我们认为正方形的同一行或同一行的头尾是相连的)。如果走到某个小方格，而该格已填了数，那末就改走到原方格的下面一个方格。,习题3.4-10,问 题 描 述,将一个正整数n表示成一系列正整数之和，正整数n的不同的划分个数称为正整数的划分数，记作p(n).,编程任务：,对于给定的正整数n，编程计算划分数p(n)。,解题思路:,q(n,1)=1,n=1;q(n,m)=q(n,n),m=n;q(n,n)=1+q(n,n-1)q(n,m)=q(n,m-1)+q(n-m,m),nm1注：如果最大加数m小于n，则划分个数可分为最大加数是m-1的划分个数加上第一个加数是m的划分个数，第一个加数是m的划分个数相当于考虑n-m这个整数的最大加数是m的划分个数,递归关系,q(n,m)=,1 n=1,m=1,q(n,n)nm,1+q(n,n-1)n=m,q(n,m-1)+q(n-m,m)nm1,
