分支限界法
一.分支限界法的思想:
1)在分支限界法中,每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点
中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入
活结点表中。
2)此后,从活结点表中取下一结点成为当前扩展结点,并重复上述扩展
过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
二.分支限界法与回溯法的异同
1)求解目标:回溯法求解的目标时找出解空间树中满足约束条件的所有解,
而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束
条件的解中找出在某种意义下的最优解。
2)搜索方式不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则
以广度优先或以最小耗费优先的方式搜索解空间树。
三.分支界限法的边界
用分支界限法解决问题的关键是找边界,上界或下界。
1)对于一颗状态空间树的每一个结点所代表的部分解,要提供一种方法,
计算出通过这个部分解繁衍出的任何解在目标函数上的最佳值边界。
2)对于最小化问题,找下界,对于最大化问题,找上界。
四.分支界限法的分支
1)在当前树的未中止(活的)叶子节点中,选择其中最有希望的结点,
并生产它的所有子女。
2)比较活叶子结点的上界/下界,把具有最佳上界/下界的结点作为最有
希望的结点。
五.查找路径的中止条件
1)该结点的边界值不能超过目前最佳解的值。
2) 该结点无法代表任何可行解,因为它已经违反了约束条件。
3)该结点代表的可行解的子集只包含一个单独的点
(因此无法给出更多的选择)。
六。 例子
求最小值,找下界。
那么,下界如何找呢?
我们可以按照行优先和列优先。 这里我们采用行优先,找出每一行最小值求和,那么最优解一定不会大于这个值,
因为这样选出的下界是可能违法约束条件的,这里的下界就是:
有一份工作派了两个人。
接着开始构树,start为开始的根节点,那么他会有几个分支呢?
看完第一张图再想想看,应该是4个分支,把接下来的分支都计算出
问题来了,为什么下面这张图改变了值呢?不是选3,1,4而是4,5,4
这里我们注意下不能选已经安排的工作,(这一层以前包括这一层都是已经安排的),其他行
选择最小值即可。
然后我们看,选哪一个继续扩展呢?是四个都扩展吗?
答案是否定的,因为其他三个是在未被安排的工作取最小值的情况下求的和,可能违反约束条件(每个工作派一个人),
在这种情况下都比别的小,没有必要扩展了,
接下来对第二个点扩展
重复构造的过程,
这个解即为最优解。
我们再看一个例子,
01背包问题
这个是求最大值,则求上界。
性价比最后一栏是第一个是10,不方便改啦(懒。。)
根据决策函数(这个不唯一,看个人怎么想),然后一样的每次选择当前最小(大)消耗
就是这样,嗯。