穷举法、贪心法、分枝限界法.doc

穷举法、贪心法、分枝限界法 讲解人： 一、穷举法（枚举法） （一）算法思路 就是从可能的解的集合中一一枚举各元素，用题目给定的检验条件，判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。 （二）例子（第二章介绍过的货郎担问题） 假定以编号为1的城市为始发城市，那么就会有4！=24个不同的路线，我们只要列举出每一条路线并分别计算出相应的费用即可。从中就可以找出最小费用及对应的路线。 （三）算法复杂度：O(n!) （四）算法评价 优点：可得到精确值。当n较小时，是可行的； 缺点：较笨拙，由于须列举所有情况，且记录下每次的情况，需要大量的机时和内存空间。当n较大时，该算法是不可行性的。 二、贪心法 贪心法是一种对某些求最优解问题的更简单、更迅速的设计方法。 （一）引言 在给出贪心法的具体定义和算法步骤之前，我们先来看两个例子。 例1 假设有4种硬币，它们的面值分别为1角、5分、2分和1分。现要找给某顾客3角7分钱，这时，我们几乎不假思索地拿出3个l角、1个5分和1个2分的硬币交给顾客。我们不仅能很快决定要拿哪些硬币，而且与其它找法相比．我们拿出的硬币的个数肯定是最少的。 在这里，我们实际使用了这样的算法：首先选出一个面值不超过3角7分的最大硬币(1角)，然后从3角7分中减去1角，剩下2角7分再选出一个不超过2角7分的最大硬币(另一个1角)，如此做下去，直到找足3角7分。 例2 如图1—1，其中，顶点可解释为城市，边上的代价可解释为两城市问的里程。在图中找一条经过所有结点一次的回路，并使里程的总和为最小。这同样还是货郎担问题。在解此题时，我们可以按这样一个想法去做： 首先在图中选一条代价最小的边。为了选择下一条边，先要检查一下候选边与已选入的边之间是否满足以下两点： 1)不会有三条边(候选边及已入选边)与同一顶点相关联。 2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数。 在满足以上两点的候选边中，挑选最短的边作为入选边。如此做下去，直到得到一个经过所有顶点的回路。 图1-1 最后求得的回路是1—2—5—3—4—1，代价是14。实际图1—1最小代价的回路是1—2—5—4—3一1，代价是10。 在这两个例子中，我们使用的方法就是贪心法。 （二）问题的定义 事实上，贪心法是我们经常自觉使用的一种方法。下面我们从一般意义上再来认识一下贪心法。在现实世界中，有这样的一类问题，它有n个输入，而它的解由这n个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。我们把那些必须满足的条件称为约束条件，而把满足约束条件的子集称为该问题的可行解。显然，满足约束条件的子集可能不止一个，因此，可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也给出了一定的标准。这些标准一般以函数形式给出，这些函数称为目标函数。那些使目标函数取极值(极大或极小)的可行解，称为最优解。对于这一类需求最优解的问题，又可以根据描述约束条件和目标函数的数学模型的特性或求解问题方法的不同进而细分为线性规划、整数规划、非线性规划和动态规划等问题。尽管各类规划问题都有求解本类问题的一些基本方法，但对于其中的某些问题，则可用一种更直接的方法来设计求解，这种方法就是贪心法。 （三）算法思想 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止实现该算法的过程( {将解向量solution 初始化为空} for i(1 to n do [x(select (A)； if feasible (solutioin ,x) then solution( union (solution,x)]; return (solution ) end;{Greedy} 函数select的功能是按某种量度标准从A中选择一个输入，把它的值赋给x并从A中消去它。feasible是一个布尔函数，它判定x是否可以包含在解向量中，union将x与解向量结合并修改目标函数。过程Greedy描述了用贪心法设计算法的主要工作和基本控制路线。一旦给出一个特定的问题，就可将select、feasible和union具体化并付诸实现。 （五）算法评价 优点：简单、快捷； 存在问题：保证求得的最后解是最佳的；能求满足某些约束条件的可行解的范围。 我们可以把路线费用最小这个目标落实在每前进一步的子目标上，这个子目标就是有一个城市通向所有其他未到过的城市通路中具有最小费用的弧。这条弧就是可行解的一个元素。 现在我们用以下几张图来解释这个算法： 我们假设从基地城市N=1出发的路线结构。图中：用过的节点用小方块表示，尚未到达的节点用圆圈表示