【教学课件】第6章分支限界法.ppt

,第6章 分支限界法,6.1 概述 6.2 分支限界法 6.3 应用举例本章小结,6.1 概述,搜索法在动态产生问题的解空间，并搜索问题的可行解或最优解。在生成的结点中，抛弃那些不满足约束条件（或者说不可能导出最优可行解）的结点。搜索方式深度优先搜索广度优先搜索,6.1 概述,方法1：深度优先搜索通常深度优先搜索法不全部保留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解空间树的深度，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。,6.1 概述,方法2：广度优先搜索广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。,6.2 分支限界法,什么是分支限界法采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率,分枝限界法的搜索策略,6.2 分支限界法,搜索策略按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。然后，从活结点表中取出一个结点作为当前扩展结点。重复上述结点扩展过程，直至找到问题的解或判定无解为止。,6.2常见的两种分支限界法,6.2 分支限界法,几种常见的分支限界法不同的活结点表形成不同的分枝限界法，分为：1.FIFO分支限界法（队列式分支限界法）活结点表是先进先出队列 LIFO分支限界法活结点表是堆栈2.LC（least cost）分支限界法（优先队列式分支限界法）活结点表是优先权队列，LC分支限界法将选取具有最高优先级的活结点出队列，成为新的E-结点。,6.2常见的两种分支限界法,1.队列式(FIFO)分支限界法,基本思想：按照队列先进先出（FIFO）原则选取下一个活结点为扩展结点。搜索策略一开始，根结点是唯一的活结点，根结点入队。从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，直到找到一个解或活结点队列为空为止。,优先队列式分支限界法,2.优先队列式分支限界法,基本思想：为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。基本策略对每一活结点计算一个优先级（某些信息的函数值），并根据这些优先级；从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。再从活结点表中下一个优先级别最高的结点为当前扩展结点，直到找到一个解或活结点队列为空为止。,6.3 应用举例,例1：01背包问题例2：TSP问题例3：装载问题例4：8数码难题 例5：15迷问题,例1：01背包问题,问题描述,例1：01背包问题,分析问题的解向量：n元向量x1,x2,.,xn,xi0,1，问题的解空间：子集树搜索方式1.队列式搜索（1）队列式分支法（2）队列式分支限界法 2.优先队列式搜索（1）优先队列式分支法（2）优先队列式分支限界法,0-1 背包问题,1.队列式,（1）队列式分支法：n=3,c=30,w=(16,15,15),p=(45,25,25),0-1 背包问题,1.队列式,注意：队列式分支法的搜索过程是对子集树进行盲目搜索，我们虽然不能将搜索算法改进为多项式复杂度，但若在在算法中加入了“限界”技巧，还是能降低算法的复杂度。一个简单的现象：若当前分支的“装载的价值上界”，比现有的最大装载的价值小，则该分支就无需继续搜索。,6.3 0-1 背包问题,（2）队列式分支限界法：n=3,c=30,w=(16,15,15),p=(45,25,25),1.队列式,6.3 0-1 背包问题,（1）优先队列式分支法：n=3,c=30,w=(16,15,15),p=(45,25,25),2.优先队列式,0-1 背包问题,优先队列式分支法：优先队列式扩展方式，若不加入限界策略其实是无意义的。因为要说明解的最优性，不搜索完所有问题空间是不能下结论的，而要对问题空间进行完全搜索，考虑优先级也就没有意义了。事实上：优先队列式搜索通过结点的优先级，可以使搜索尽快朝着解空间树上有最优解的分支推进，这样当前最优解一定较接近真正的最优解。优先队列式分支限界法我们将优先队列搜索得到当前最优解作为一个“界”，对上界（或下界）不可能达到（大于）这个界的分支则不去进行搜索，这样就缩小搜索范围，提高了搜索效率。这种搜索策略称为优先队列式分支限界法。,2.优先队列式,0-1 背包问题,（2）优先队列式分支限界法n=3,c=30,w=(16,15,15),p=(45,25,25),2.优先队列式,0-1 背包问题,例1：01背包问题,注意：看了上面的例子大家会发现优先队列法扩展结点的过程，一开始实际是在进行类似“深度优先”的搜索。,TSP问题,问题提出：分析解空间：排列树,例：TSP问题,6.4 旅行售货商问题,1.队列式分支限界,例：TSP问题,6.4 旅行售货商问题,2.优先队列式分支限界法,例：TSP问题,装载问题,问题描述有两艘船，n 个货箱。第一艘船的载重量是c1，第二艘船的载重量是c2，wi 是货箱i 的重量，且w1+w2+wnc1+c2。我们希望确定是否有一种可将所有n 个货箱全部装船的方法。若有的话，找出该方法。分析解空间：子集树空间,例：装载问题,例：装载问题,例：W=10，30，50，C1=60，,例：装载问题,队列式分支限界法的搜索过程为：初始队列中只有结点A；结点A变为扩展结点扩充B入队，bestw=10；结点C的装载上界为30+50=80 bestw，也入队；结点B变为扩展结点扩充D入队，bestw=40；结点E的装载上界为60 bestw，入队；结点C变为扩展结点扩充F入队，bestw仍为40；结点G的装载上界为50 bestw，也入队；结点D变为扩展结点，叶结点H超过容量，叶结点I的装载为40，bestw仍为40；结点E变为扩展结点，叶结点J装载量为60，bestw为60；叶结点K被剪掉；结点F变为扩展结点，叶结点L超过容量，bestw为60，叶结点M被剪掉。结点G变为扩展结点，叶结点N、O都被剪掉；此时队列空算法结束。,例：装载问题,优先级队列式分支限界法的搜索的过程：初始队列中只有结点A；结点A变为E-结点扩充B入堆，bestw=10；结点C的装载上界为30+50=80 bestw，也入堆；堆中B上界为90在优先队列首。结点B变为E-结点扩充D入堆，bestw=40；结点E的装载上界为60 bestw，也入堆；此时堆中D上界为90为优先队列首。结点D变为E-结点，叶结点H超过容量，叶结点I的装载为40入堆，bestw仍为40；此时堆中C上界为80为优先队列首。,例：装载问题,结点C变为E-结点扩充F入堆，bestw仍为40；结点G的装载上界为50 bestw，也入堆；此时堆中E上界为60为优先队列首。结点E变为E-结点，叶结点J装载量为60入队，bestw变为60；叶结点K上界为10bestw被剪掉；此时堆中J上界为60为优先队列首。结点J变为E-结点，扩展的层次为4算法结束。虽然此时堆并不空，但可以确定已找到了最优解。,6.5 八数码难题,问题描述：求解过程示意图：程序实现：,例4：八数码难题,6.5 八数码难题,思考：缺点如何改进？,例4：八数码难题,6.5 八数码难题,启发式搜索设置启发函数：f(n)d(n)w(n)若w(n)0不体现启发信息，f(n)d(n)，反映广度优先搜索过程。现设置：d(n):搜索树中节点的深度（根在第0层）w(n):计算当前节点n的状态描述中错放位的棋子数（与目标状态相比）。,例4：八数码难题,例5：15迷问题,问题描述在一个分成44的棋盘上排列15块号牌，其中会出现一个空格。棋盘上号牌的一次合法移动是指将位于空格上、下、左、右的一块号牌移入空格。要求通过一系列合法移动，将号牌的初始排列转换成自然排列。例如：,例5：15迷问题,分析：初始状态和目标状态，从任意初始状态，经一系列的空格移动，到达目标状态。空格可以最多有上、下、左、右四种移动方式。共有16！种不同的排列。这个状态空间树是相当大的。有必要判定当前到达的状态是否属于该状态空间树。,定理对给定的初始状态，当且仅当为偶数时，可以由此初始状态到达目标状态。其中：less(k)就是数字比 k小，但是位置在 k后的牌的总和。i和j分别是空格在棋盘上的行和列下标。,例5：15迷问题,15谜问题的部分状态空间树(FIFO),15谜问题的部分状态空间树(LC),回溯法与分支限界法问题的解空间树的搜索方式求解目标适合问题相对而言，分支限界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。,本章小结,本章小结,下表列出了回溯法和分支限界法的一些区别：,最优化问题的求解策略比较,回溯法：因为层次的划分，可以在上界（下界）函数值小于（大于）当前最优解时，剪去以该结点为根的子树，也就是节省了搜索范围；分支限界法除了可以做到回溯法能做到的之外，同时若采用优先队列的分支限界法，用上界函数作为活结点的优先级，一旦有叶结点成为当前扩展结点，就意味着该叶结点所对应的解即为最优解，可以立即终止其余的过程。仅就对限界剪枝的效率而言，优先队列的分支限界法显然要更充分一些。优先队列的分支限界法更象是有选择、有目的地进行深度优先搜索，时间效率、空间效率都是比较高的。,动态规划与搜索算法(1)撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索可以说是“万能”的，所以动态规划可以解决的问题，搜索也一定可以解决。(2)动态规划要求阶段决策具有无后向性，而搜索算法没有此限制。(3)动态规划通常是自底向上的递推求解；而无论深度优先搜索或广度优先搜索都是自顶向下求解。,最优化问题的求解策略比较,最优化问题的求解策略比较,动态规划与搜索算法(4)问题解空间的构造利用动态规划法进行算法设计时，设计者在进行算法设计前已经用大脑自己构造好了问题的解空间，因此可以自底向上的递推求解；而搜索算法是在搜索过程中根据一定规则自动构造，并搜索解空间树。由于在很多情况下，问题的解空间太复杂用大脑构造有一定困难，仍然需要采用搜索算法。(5)动态规划在递推求解过程中，需要用数组存储有关信息，而数组的下标只能是整数，所以要求问题中相关的数据必须为整数。,最优化问题的求解策略比较,动态规划与搜索算法一般说来，动态规划算法在时间效率上的优势是搜索法无法比拟的，但动态规划总要遍历所有的状态，而搜索可以排除一些无效状态，更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。思考如何协调好高效率与高消费之间的矛盾呢？一种折衷的办法记忆化搜索算法,最优化问题的求解策略比较,记忆化搜索算法记忆化搜索算法在求解时，还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。记忆化搜索算法以搜索算法为核心，只不过使用“记录求过的状态”的办法，来避免重复搜索，这样，记忆化搜索的每一步，也可以对应到动态规划算法中去。,