《穷举法、贪心法、分枝限界法》由会员分享，可在线阅读，更多相关《穷举法、贪心法、分枝限界法（11页珍藏版）》请在金锄头文库上搜索。
1、1穷举法、贪心法、分枝限界法讲解人： 一、穷举法（枚举法）（一）算法思路就是从可能的解的集合中一一枚举各元素，用题目给定的检验条件，判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。（二）例子（第二章介绍过的货郎担问题）假定以编号为 1 的城市为始发城市，那么就会有 4！=24 个不同的路线，我们只要列举出每一条路线并分别计算出相应的费用即可。从中就可以找出最小费用及对应的路线。（三）算法复杂度：O(n!)（四）算法评价优点：可得到精确值。当 n 较小时，是可行的；缺点：较笨拙，由于须列举所有情况，且记录下每次的情况，需要大量的机时和内存空间。当 n 较大时，该算法是不可行性的。二、贪心
2、法贪心法是一种对某些求最优解问题的更简单、更迅速的设计方法。（一）引言 在给出贪心法的具体定义和算法步骤之前，我们先来看两个例子。例 1 假设有 4 种硬币，它们的面值分别为 1 角、5 分、2 分和 1 分。现要找给某顾客3 角 7 分钱，这时，我们几乎不假思索地拿出 3 个 l 角、 1 个 5 分和 1 个 2 分的硬币交给顾客。我们不仅能很快决定要拿哪些硬币，而且与其它找法相比我们拿出的硬币的个数肯定是最少的。在这里，我们实际使用了这样的算法：首先选出一个面值不超过 3 角 7 分的最大硬币(1 角)，然后从 3 角 7 分中减去 1 角，剩下 2 角 7 分再选出一个不超过 2 角
3、7 分的最大硬币(另一个 1 角) ，如此做下去，直到找足 3 角 7 分。例 2 如图 11，其中，顶点可解释为城市，边上的代价可解释为两城市问的里程。在图中找一条经过所有结点一次的回路，并使里程的总和为最小。这同样还是货郎担问题。在解此题时，我们可以按这样一个想法去做：首先在图中选一条代价最小的边。为了选择下一条边，先要检查一下候选边与已选入的边之间是否满足以下两点：1)不会有三条边(候选边及已入选边)与同一顶点相关联。2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数。在满足以上两点的候选边中，挑选最短的边作为入选边。如此做下去，直到得到一个经过所有顶点的回路。2图 1-1最
4、后求得的回路是 125341，代价是 14。实际图 11 最小代价的回路是12543 一 1，代价是 10。在这两个例子中，我们使用的方法就是贪心法。（二）问题的定义事实上，贪心法是我们经常自觉使用的一种方法。下面我们从一般意义上再来认识一下贪心法。在现实世界中，有这样的一类问题，它有 n 个输入，而它的解由这 n 个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。我们把那些必须满足的条件称为约束条件，而把满足约束条件的子集称为该问题的可行解。显然，满足约束条件的子集可能不止一个，因此，可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也给出了一定的标准。这些标准一般以函数形式给
5、出，这些函数称为目标函数。那些使目标函数取极值( 极大或极小)的可行解，称为最优解。对于这一类需求最优解的问题，又可以根据描述约束条件和目标函数的数学模型的特性或求解问题方法的不同进而细分为线性规划、整数规划、非线性规划和动态规划等问题。尽管各类规划问题都有求解本类问题的一些基本方法，但对于其中的某些问题，则可用一种更直接的方法来设计求解，这种方法就是贪心法。（三）算法思想从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止，得到问题的一个解。（四）实现该算法的过程贪心法是一种改进了的分级处理方法。它首先根据题意，选取一种量度
6、标淮。然后将这 n 个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。要注意的是，对于一个给定的问题。往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的。但实际上，用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。尤其值得指出的是，把目标函数作为量度标准所得到的解也不一定是问题的最优解。因此，选择能产生问题最优解的最优量度标准是使用贪心法的核心问题。在一般情况下，要选出最优量度标准并不是一件容易的事，不过，一旦对某问题能选择
7、出最优量度标准。用贪心法求解则特别有效。贪心法可以用下面的抽象过程来描述。Procedure Greedy (A，n)；A1 n包含 n 个输入begin solution 将解向量 solution 初始化为空for i1 to n do3xselect (A)；if feasible (solutioin ,x) then solution union (solution,x);return (solution )end;Greedy函数 select 的功能是按某种量度标准从 A 中选择一个输入，把它的值赋给 x 并从 A 中消去它。feasible 是一个布尔函数，它判定 x 是否可以
8、包含在解向量中， union 将 x 与解向量结合并修改目标函数。过程 Greedy 描述了用贪心法设计算法的主要工作和基本控制路线。一旦给出一个特定的问题，就可将 select、feasible 和 union 具体化并付诸实现。（五）算法评价优点：简单、快捷；存在问题：1）不能保证求得的最后解是最佳的；在第一个例子中，解是最优的。在第二个例子中，解不是最优的。这一点也是我们要强调的。即贪心法并不保证求得全局最优解。在例 2 中，我们可以看到，在产生回路的过程中，总是从已入选的顶点中寻求连向未入选的顶点，以得代价最小的边，这样就使一些代价较小的边可能并不能入选，从而造成结果不是最优。可以看出
9、，具体到每一步，贪心法做出的选择只是某种意义上的“局部最优选择” 、最终结果一般不一定是最优的。例 1 找钱的贪心算法结果之所以是最优的，是由于硬币面值的特殊性。如果现在硬币的面值分别是 1 角 1 分、7 分、5 分和 1 分，按贪心法拿出的硬币是 3 个 1 角 1 分和 4 个 1 分，共 7 枚。这比 2 个 1 角 1 分和 3 个 5 分至多 2 枚。这是由于我们总是从局部的最优出发，没有看到全局的情况，致使目光短浅，欲速不达。也正是由于它不再去看全局，使得这一方法成为简单、快捷的方法。对于某些问题，我们并不知道是否能用贪心法得出最优解。但一般使用贪心法会很快得到问题的“满意”解(
10、即次优解) 。如果一个问题的最优解只能用穷举法得到，那么用贪心法(或其它启发式方法 )去寻找问题的次优解就是唯一可行的方法了。2）只能求满足某些约束条件的可行解的范围。（六）具体实例例 1：五个城市的售货员问题。费用矩阵和无向网络如下：1 2 3 4 5 1 2 7 51 4 4 32 4 1 27 4 1 35 3 2 3 4我们可以把路线费用最小这个目标落实在每前进一步的子目标上，这个子目标就是有一个城市通向所有其他未到过的城市通路中具有最小费用的弧。这条弧就是可行解的一个元素。现在我们用以下几张图来解释这个算法：我们假设从基地城市 N=1 出发的路线结构。图中：用过的节点用小方块表示，尚
11、未到达的节点用圆圈表示。11 15 3 2 15 3 24 4 4 3 23 4 3 11 5 3 2 132 24 1 3 17 1321从图中不难发现，最后返回基地城市 1 时，费用为 7，这个费用时最昂贵的。这条路线的总费用为 14，路线为1 2 5 3 4 1 很明显这条路线不是最佳路线。最佳路线时：1 2 5 4 3 1总费用为 10。所以登山法没有求得最佳解。我们可以看出虽然每步它都去最佳值，但5412314135242375没考虑后面几个点得费用，有可能后面得费用较高。根据这种情况我们对此做一些改进：从选择 p(n) 个不同得城市出发，分别调用函数，得到 p 个结果。比较这些结果
12、，从中找出最小花费路线。例 2：登山法求解背包问题背包问题，给定一个装载量为 M 得背包及分别重量为 wi 得 n 个物体得序列 I。X i 表示物体 I 的一部分，0X i 1。X i =1 表示第 i 个物体整个放进背包。P i 为第 i 个物体的价值/问应怎样选择物品的种类及数量，使背包装满且价值达到最大值。即给定 M0，Pi0, 0i n,求 n 元向量(X 1 ，X 2 ，, X n ),使maxP iXi ( 0i n )而且 Xi 满足：w i Xi =M ( 0i n )可以采用登山法来选取物体的序列：每次从剩下的物体序列中选取 Pi 为最大的物体放进背包。这样作，虽然上式增长
13、最快，但是背包的装载量下降的很快，加入背包的 Pi 的个数少了，不一定能使这个目标函数达到最大值。因此考虑目标函数的增量之外，还应考虑背包装载量的消耗的速度。根据这个想法可根据每次选取的 Pi / wi 最大的物体放进背包。从这个例子中不难发现在用登山法求解问题时选取什么作为最优化量度来求解显的非常的重用。如果有多个约束条件的话一定要在最优化量度当中有所体现。从以上两个例子可以领会贪心法的基本思想，对于最小化问题来说，总是先消耗最小的元素加入集合；而对于最大化问题，则反之。这种方法的优点时求解速度快，时间复杂性具有较低的阶。它的缺点时一般找不到最优解，因为它有一个致命的弱点：后进入解向量的元素
14、一般都有较大的消费。三、分支定界法（分支与限界）（一）算法的基本思想分支定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。下面首先介绍它的基本思想。分支定界法是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支） ，并为每个子集内的解的植计算一个下界或上界（称为定界） 。再每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索的范围。这一过程一直进行到找出可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。（二）算法实现过程（通过推销员问题来说明分支定界法的思想）1型推销员问题设有 5 个城 ,从某一城市出发，遍历各城市一次且仅一次，最后返1v5432,v回原地，求最短路径。其费用矩阵如下：6D= 69321653246将矩阵 D 对角线以上的元素从小到大排列为： K345425153,dd去最小的
