(原创精品分支 限界法.doc

文档介绍：分支限界法
概述:
分支定界(branch and bound) s搜索法是一种在问题的解空间树上搜索问题的解的方法。分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树,并且,在分支定界算法中,每一个活结点只有一次机会成为扩展结点。
搜索策略
1 产生当前扩展结点的所有孩子结点;
2 在产生的孩子结点中,抛弃那些不可能产生可行解(或最优解)的结点;
3 将其余的孩子结点加入活结点表;
4 从活结点表中选择下一个活结点作为新的扩展结点。
5 如此循环,直到找到问题的可行解(最优解)或活结点表为空。
从活结点表中选择下一个活结点作为新的扩展结点
根据选择方式的不同
分支定界算法通常可以分为两种形式:
队列式(FIFO)分支限界法
队列式分支限界法将活结点表组织成一个队列,并按队列的先进先出原则选取下一个结点为当前扩展结点
②优先队列式的分支限界法将活结点表组织成一个队列,并按优先队列中规定的优先级选取优先级最高的下一个节点成为当前扩展节点
最大优先队列:使用最大堆,体现最大效益优先
最小优先队列:使用最小堆,体现最小费用优先
分支限界法和回溯法的区别
求解目标不同:
回溯法的求解目标是找出解空间树中满足约束条件的所有解
分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解
搜索方式不同:
回溯法以深度优先的方式搜索解空间树
分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树
搜索问题的解空间树方面:
在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。
此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
什么是剪枝(以走迷宫举例)
我们在“走迷宫”的时候,一般回溯法思路是这样