穷举法、贪心法、分枝限界法.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 如图11，其中，顶点可解释为城市，边上的代价可解释为两城市问的里程。在图中找一条经过所有结点一次的回路，并使里程的总和为最小。这同样还是货郎担问题。在解此题时，我们可以按这样一个想法去做： 首先在图中选一条代价最小的边。为了选择下一条边，先要检查一下候选边与已选入的边之间是否满足以下两点： 1)不会有三条边(候选边及已入选边)与同一顶点相关联。 2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数。在满足以上两点的候选边中，挑选最短的边作为入选边。如此做下去，直到得到一个经过所有顶点的回路。图1-1最后求得的回路是125341，代价是14。实际图11最小代价的回路是12543一1，代价是10。在这两个例子中，我们使用的方法就是贪心法。（二）问题的定义事实上，贪心法是我们经常自觉使用的一种方法。下面我们从一般意义上再来认识一下贪心法。在现实世界中，有这样的一类问题，它有n个输入，而它的解由这n个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。我们把那些必须满足的条件称为约束条件，而把满足约束条件的子集称为该问题的可行解。显然，满足约束条件的子集可能不止一个，因此，可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也给出了一定的标准。这些标准一般以函数形式给出，这些函数称为目标函数。那些使目标函数取极值(极大或极小)的可行解，称为最优解。对于这一类需求最优解的问题，又可以根据描述约束条件和目标函数的数学模型的特性或求解问题方法的不同进而细分为线性规划、整数规划、非线性规划和动态规划等问题。尽管各类规划问题都有求解本类问题的一些基本方法，但对于其中的某些问题，则可用一种更直接的方法来设计求解，这种方法就是贪心法。（三）算法思想从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止，得到问题的一个解。（四）实现该算法的过程贪心法是一种改进了的分级处理方法。它首先根据题意，选取一种量度标淮。然后将这n个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。要注意的是，对于一个给定的问题。往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的。但实际上，用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。尤其值得指出的是，把目标函数作为量度标准所得到的解也不一定是问题的最优解。因此，选择能产生问题最优解的最优量度标准是使用贪心法的核心问题。在一般情况下，要选出最优量度标准并不是一件容易的事，不过，一旦对某问题能选择出最优量度标准。用贪心法求解则特别有效。贪心法可以用下面的抽象过程来描述。Procedure Greedy (A，n)； A1n包含n个输入begin solution 将解向量solution 初始化为空 for i1 to n do xselect (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具体化并付诸实现。（五）算法评价优点：简单、快捷；存在问题：1）不能保证求得的最后解是最佳的；在第一个例子中，解是最优的。在第二个例子中，解不是最优的。这一点也是我们要强调的。即贪心法并不保证求得全局最优解。在例2中，我们可以看到，在产生回路的过程中，总是从已入选的顶点中寻求连向未入选的顶点，以得代价最小的边，这样就使一些代价较小的边可能并不能入选，从而造成结果不是最优。可以看出，具体到每一步，贪心法做出的选择只是某种意义上的“局部最优选择”、最终结果一般不一定是最优的。例1找钱的贪心算法结果之所以是最优的，是由于硬币面值的特殊性。如果现在硬币的面值分别是1角1分、7分、5分和1分，按贪心法拿出的硬币是3个1角1分和4个1分，共7枚。这比2个1角1分和3个5分至多2枚。这是由于我们总是从局部的最优出发，没有看到全局的情况，致使目光短浅，欲速不达。也正是由于它不再去看全局，使得这一方法成为简单、快捷的方法。对于某些问题，我们并不知道是否能用贪心法得出最优解。但一般使用贪心法会很快得到问题的“满意”解(即次优解)。如果一个问题的最优解只能用穷举法得到，那么用贪心法(或其它启发式方法)去寻找问题的次优解就是唯一可行的方法了。2）只能求满足某些约束条件的可行解的范围。（六）具体实例例1：五个城市的售货员问题。费用矩阵和无向网络如下： 1 2 3 4 512751443241274135323 我们可以把路线费用最小这个目标落实在每前进一步的子目标上，这个子目标就是有一个城市通向所有其他未到过的城市通路中具有最小费用的弧。这条弧就是可行解的一个元素。 现在我们用以下几张图来解释这个算法： 我们假设从基地城市N=1出发的路线结构。图中：用过的节点用小方块表示，尚未到达的节点用圆圈表示。 11 1 5 3 2 1 5 3 24 4 4 3 2 3 4 3 1 1 5 3 2 1 3 2 2 4 1 3 1 7 1 3 2 1 从图中不难发现，最后返回基地城市1时，费用为7，这个费用时最昂贵的。这条路线的总费用为14，路线为 1 2 5 3 4 1 很明显这条路线不是最佳路线。最佳路线时： 1 2 5 4 3 1总费用为10。所以登山法没有求得最佳解。我们可以看出虽然每步它都去最佳值，但没考虑后面几个点得费用，有可能后面得费用较高。根据这种情况我们对此做一些改进：从选择p(n)个不同得城市出发，分别调用函数，得到p个结果。比较这些结果，从中找出最小花费路线。例2：登山法求解背包问题背包问题，给定一个装载量为M得背包及分别重量为wi得n个物体得序列I。Xi 表示物体I的一部分，0Xi1。Xi =1表示第i 个物体整个放进背包。Pi为第i个物体的价值/问应怎样选择物品的种类及数量，使背包装满且价值达到最大值。即给定M0，Pi0, 0in,求n元向量(X1 ，X2 ，, Xn ),使 maxPiXi ( 0in )而且Xi满足： wi Xi =M ( 0in )可以采用登山法来选取物体的序列：每次从剩下的物体序列中选取Pi 为最大的物体放进背包。这样作，虽然上式增长最快，但是背包的装载量下降的很快，加入背包的Pi 的个数少了，不一定能使这个目标函数达到最大值。因此考虑目标函数的增量之外，还应考虑背包装载量的消耗的速度。根据这个想法可根据每次选取的Pi / wi 最大的物体放进背包。从这个例子中不难发现在用登山法求解问题时选取什么作为最优化量度来求解显的非常的重用。如果有多个约束条件的话一定要在最优化量度当中有所体现。从以上两个例子可以领会贪心法的基本思想，对于最小化问题来说，总是先消耗最小的元素加入集合；而对于最大化问题，则反之。这种方法的优点时求解速度快，时间复杂性具有较低的阶。它的缺点时一般找不到最优解，因为它有一个致命的弱点：后进入解向量的元素一般都有较大的消费。 三、分支定界法（分支与限界）（一）算法的基本思想 分支定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。下面首先介绍它的基本思想。分支定界法是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的植计算一个下界或上界（称为定界）。再每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索的范围。这一过程一直进行到找出可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。（二）算法实现过程（通过推销员问题来说明分支定界法的思想）1型推销员问题设有5个城,从某一城市出发，遍历各城市一次且仅一次，最后返回原地，求最短路径。其费用矩阵如下：D=将矩阵D对角线以上的元素从小到大排列为：去最小的5个求和得： 用 表示要构成一个回路，所以每个顶点的下标在回路的所有边中各出现两次。（1）中显然5出现了3次，若用代替则即搜索过程可以表示如下图：图（2）的下界为21，图（3）的下界为20，都大于19故没有进一步搜索的价值，因此（5）为最佳路径： 。2 型推销员问题 即。不妨把D看成旅费，即从 到的旅费与到不一样。对D的每行减去该行的最小元素，或每列减去该列的最小元素，得一新矩阵，使得每行每列至少都有一个0元素。 第一列和第三列没有为0的元素，所以第一列和第三列分别减去其最小元素1和3得：由于从任一出发一次，进入也是一次，所以问题等价于求的最佳路径，下标45是估计的界，即旅费起码为45单位（每个点出发都去最小值）。由于矩阵D第一行第四列元素为0，故从出发的路径应选择，为了排除出发进入其他点和从其他点进入的可能，并封锁到的路径，在矩阵中除去第一行和第四列，并将第四列第一行元素15改为。得：类似的从出的路径应选，消第行和第列，并将第行第列元素改为得： 这时第二行没有0元素，减去最小元素3得：搜索过程如下图：最后得到最佳路径为： （三）算法分析算法优点：可以求得最优解、平均速度快。因为从最小下界分支，每次算完限界后，把搜索树上当前所有的叶子结点的限界进行比较，找出限界最小的结点，此结点即为下次分支的结点。这种决策的优点是检查子问题较少，能较快的求得最佳解。缺点：要存储很多叶子结点的限界和对应的耗费矩阵。花费很多内存空间。存在的问题：分支定界法可应用于大量组合优化问题。其关键技术在于各结点权值如何估计，可以说一个分支定界求解方法的效率基本上由值界方法决定，若界估计不好，在极端情况下将与穷举搜索没多大区别。（四）具体实例 分枝定界一般用宽度优先或最小耗费方法来搜索解空间.在分枝定界方法中,每个活节点有且仅有一次机会变成E-节点.当一个节点变为E节点时,则生成从该节点移动一步就可到达的所有新节点.在生成的节点中抛弃那些不可能导出可行解的节点,其余节点加入活动表,然后从表中选择一个节点作为下一个e-节点.例1.迷宫问题 0 0 0 0 1 1 0 0 0 其中(1,1)为进口,(3,3)为出口;1表示障碍物.使用FIFO分枝定界,初试时取(1,1)为E-节点并且活动队列为空.迷宫的位置(1,1)被置为1,以免再次返回到这个位置.(1,1)被扩充,他的相邻节点(1,2)和(2,1)加入到队列中.为避免再次回到这两个位置,将位置(1,2)和(2,1)置为本1.此时迷宫如: 1 1 0 1 1 1 0 0 0(1,1)点将被删除.节点(1,2)从队列中移出并被扩充.检查它的三个相邻节点,只有(1,3)是可以的,加入队列,并把相应的迷宫位置置为1,所得的迷宫状态如下: 1 1 1 1 1 1 0 0 0(1,2)被删除,(2,1)被取出,当此节点被展开时,节点(3,1)被加入到队列中,(3,1)位置被置为1,节点(2,1)被删除,所得图: 1 1 1 1 1 1 1 0 0 此时队列中包含(1,3)和(3,1)两个节点.随后节点(1,3)变成下一个E-节点.由于此节点不能到达任何新的节点,所以此节点被删除.节点(3,1)成为新的E-节点,将队列清空.节点(3,1)展开,(3,2)被加入到队列中,而(3,1)被删除.(3,2)变为新的E节点,展开此节点后,到达(3,3),迷宫的出口.例2.0/1背包问题 下面比较分别利用FIFO分枝定界和最大收益分枝定界方法来解决如下背包问题:n=3,w=20,15,15,p=40,25,25,c=30; FIFO分枝定界利用一个队列来记录活节点节点将按照FIFO顺序从队列中取出. 三个对象的背包问题的解空间i)使用FIFO分枝定界法收缩初始时以根节点A作为E-节点,此时队列为空.当节点A展开时,生成了节点B和C,由于这两个节点都是可行的,因此都被加入到活动队列中去了,A被删除.下一个节点B成为E-节点,它展开后生成了节点D和E,D是不可行的,所以要把它删除.而E加入队列中去.下一节点C成为E-节点,它展开后生成节点出F和G,两者都是可行点,加入队列中.下一个节点E生成节点J和K,J是不可行的被删除,K是一个可行的节点,并产生到目前为止的一个可行解,它的收益值为方便40.下一个节点是F,它产生两个孩子L,M,L代表一个可行的解并且收益值为50,M代表另外一个解收益值为15.G是最后一个E节点,它的孩子N和O都是可行的.由于活动节点队列变为空,因此搜索过程停止,最佳的收益值为50.可以看到,工作在解空间树上的FIFO分枝定界方法非常象从根节点出发的宽度优先搜索.他们的主要区别是在FIFO分枝定界中不可行的节点不会被搜索.ii)此方法的弊端:每个有可行解的子树都要去搜索.iii)改进:更有