第十章 分支限界法

本文格式为Word版，下载可任意编辑——第十章分支限界法

《计算机算法》胡金初—PPT

第十章分支限界法分支限界法的特点：分支限界法的特点：分支限界法在扩展节点处，先生成其所有的儿子结点(分支),点处，先生成其所有的儿子结点(分支),然后再从当前的活节点表中选择下一个扩展结点。为了有效地选择下一个扩展结点，结点。为了有效地选择下一个扩展结点，要在每一活结点处，计算一个函数值(限界),在每一活结点处，计算一个函数值(限界),根据计算出来的函数值选择下一个扩展结点，根据计算出来的函数值选择下一个扩展结点，使探寻朝着解空间树上最优先的分支推进，使探寻朝着解空间树上最优先的分支推进，以便尽快找到最优解。并且在分支限界法中，以便尽快找到最优解。并且在分支限界法中，每一个活结点只有一次机遇成为扩展结点，每一个活结点只有一次机遇成为扩展结点，而且成为扩展结点的活结点会一次性产生所有的儿子结点。有的儿子结点。2023-5-24上海师范大学计算机系胡金初1

《计算机算法》胡金初—PPT

第十章分支限界法

目录10.1分支限界的策略10.20-1背包问题背包问题10.2旅行商问题

2023-5-24

上海师范大学计算机系胡金初

《计算机算法》胡金初—PPT

10.1分支限界的策略分支限界(branchandbound)算法前面所陈述的回溯算法不同，法不同，回溯法在解空间树上探寻问题时是采用深度优先探寻的，探寻的，并且回溯法的求解目标时找出解空间树满足约束条件的所有解。条件的所有解。而分支限界算法采用广度优先或最小花费优先的方法探寻解空间树，优先的方法探寻解空间树，并且分支限界法的求解目标是尽快地找出满足约束条件的最优解。尽快地找出满足约束条件的最优解。利用分支限界算法对问题的解空间树进行探寻，利用分支限界算法对问题的解空间树进行探寻，它的探寻策略是：策略是：1产生当前扩展结点的所有孩子结点；产生当前扩展结点的所有孩子结点；在产生的孩子结点中，2在产生的孩子结点中，抛弃那些不可能产生可行解的结点；(或最优解)的结点；将其余的孩子结点参与活结点表；3将其余的孩子结点参与活结点表；从活结点表中选择下一个活结点作为新的扩展结点。4从活结点表中选择下一个活结点作为新的扩展结点。如此循环，直到找到问题的可行解(最优解)如此循环，直到找到问题的可行解(最优解)或活结点表为空。从活结点表中选择下一个活结点作为新的扩展结点.为空。从活结点表中选择下一个活结点作为新的扩展结点.2023-5-24上海师范大学计算机系胡金初3

《计算机算法》胡金初—PPT

10.1分支限界的策略根据选择方式的不同，根据选择方式的不同，分支限界

算法寻常可以分为两种形式：1FIFO(FirstInFirstOut)分支限界算法：依照先分支限界算法：进先出原则选择下一个活结点作为扩展结点，进先出原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与参与结点的顺序一致。表中取出结点的顺序与参与结点的顺序一致。优先队列(花费用小根堆,受益用大根堆)2优先队列(花费用小根堆,受益用大根堆):每个结点都有一个对应的花费或收益。点都有一个对应的花费或收益。假使查找一个具有最小花费的解，假使查找一个具有最小花费的解，则活结点表可用最小堆来建立，下一个扩展结点就是具有最小花费的活结点；来建立，下一个扩展结点就是具有最小花费的活结点；如果希望探寻一个具有最大收益的解，果希望探寻一个具有最大收益的解，则可用最大堆来构造活结点表，下一个扩展结点是具有最大收益的活结点。活结点表，下一个扩展结点是具有最大收益的活结点。分支限界法的思想是：首先确定目标值的上下界，分支限界法的思想是：首先确定目标值的上下界，边探寻边减掉探寻树的某些支，提高探寻效率。边减掉探寻树的某些支，提高探寻效率。也就是说分支限界法在解空间上探寻时都要用到一种基本方法叫“剪枝〞界法在解空间上探寻时都要用到一种基本方法叫“剪枝〞。

2023-5-24

上海师范大学计算机系胡金初

《计算机算法》胡金初—PPT

10.1分支限界的策略剪枝顾名思义，就是将树中的一些“死胡同〞剪枝顾名思义，就是将树中的一些“死胡同〞,不能到达我们需要的解的枝条“以减少探寻的时间。是所有的枝条都可以剪掉，的枝条“剪〞掉，以减少探寻的时间。是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。需要通过设计出合理的判断方法，以决定某一分支的取舍。在设计判断方法的时候，需要遵循一定的原则：方法的时候，需要遵循一定的原则：1、正确性2、确凿性3、高效性在描述分支限界算法步骤之前,在描述分支限界算法步骤之前先对算法涉及到的有关术语进行定义如下:p——分支层数分支层数;C*——当前最优目标函数值当前最优目标函数值;P*——相应于C*的工件顺序;相应于C*的工件顺序的工件顺序;P1——当前节点现在需要进行分支的节点所对应的部分序列当前节点(现在需要进行分支的节点所对应的部分序列.现在需要进行分支的节点)所对应的部分序列分支限界算法的实施步骤如下:分支限界算法的实施步骤如下步骤1初始化设置=0,P1=Aacute;(空集,C*=∞.设当初始化:

设置p空集)步骤空集设当前节点总是与P相对应.此时,当前节点即根节点。前节点总是与1相对应此时当前节点即根节点。步骤2计算从当前节点分支得到的各个子节点的下界并按下界计算从当前节点分支得到的各个子节点的下界,步骤值由小到大对各子节点排序.值由小到大对各子节点排序令p←p+1。。

2023-5-24

上海师范大学计算机系胡金初

《计算机算法》胡金初—PPT

步骤3假使当前节点被探测尽令p←p-1,转步骤否则假使当前节点被探测尽,转步骤6.否则,步骤设当前层(第p层)各活动子节点中具有最小下界值的节点为设当前层第Q,则在1末尾参与对应第位置上的工件此时的当前则在P末尾参与对应第p位置上的工件,末尾参与Q节点转为Q转步骤4节点转为,转步骤。步骤4由于当前节点是同层同父节点具有最小下界值的节点由于当前节点是同层同父节点具有最小下界值的节点,步骤假使当前节点下界值大于或等于C*假使当前节点下界值大于或等于,则不必再探寻当前节点及其同层同父的活动节点,这样,点及其同层同父的活动节点这样当前节点的上一层节点(父节点被探测尽,p←p-1,去掉P1中的最终一个工件,转父节点)被探测尽去掉中的最终一个工件转父节点被探测尽步骤6.否则,转步骤5。步骤否则转步骤。步骤5假使p=n,则得到一个较优顺序.令P*=P1,C*是当步骤假使则得到一个较优顺序令前节点的下界值,去掉P中最终一个工件,前节点的下界值p←p-1,去掉1中最终一个工件转步去掉否转步骤2骤6;否转步骤。步骤6若p≠0,去掉1中最终一个工件转步骤否则算去掉P中最终一个工件,转步骤否则,转步骤3;步骤法中止.法中止C*是最优的目标函数值P*是最优顺序。是最优的目标函数值,是最优顺序。返回目录2023-5-24上海师范大学计算机系胡金初6

10.1分支限界的策略

《计算机算法》胡金初—PPT

10.20-1背包问题背包问题假设有三个不同重量和不同价值的物品，假设有三个不同重量和不同价值的物品，而存放的容量却有所以我们要根据实际状况，将物品放入，限，所以我们要根据实际状况，将物品放入，从而让这个背包中物品的价值量最大。包中物品的价值量最大。0-1背包问题的解空间树(问题的所有解构成的一棵树)如背包问题的解空间树(背包问题的解空间树问题的所有解构成的一棵树)下图：1〞表示放入物品表示放入物品，0〞表示不放入物品下图：“1〞表示放入物品，“0〞表示不放入物品所有解为(所有解为(0,0,0)、(0,1,0)、(0,0,1)、(1,0,0)、(0,1,1)、(1,0,1)、(1,

1,0)、(1,1,1)

1

1

0

0

1

2023-5-2410.10-1背包问题的解空间树上海师范大学计算机系胡金初图背包问题的解空间树

1

1

1

0

0

0

0

《计算机算法》胡金初—PPT

10.20-1背包问题背包问题设物品包的重量为数组w[16,15,15],价值为p[45,25,25],设物品包的重量为数组w[16,15,15],价值为p[45,25,25],w[16],价值为p[45总容量为c=30。c=30总容量为c=30。用队列式(FIFO)1、用队列式(FIFO)分支界限法求背包问题仍以图1为例，我们求的基本步骤如下：仍以图1为例，我们求的基本步骤如下：根结点A首先进入列表；如图1010.1)根结点A首先进入列表；如图10.2A图10.2根结点首先进入列表根结点A首先进入列表根结点

依照广度遍历，将其左右儿子B结点放入队列。2)依照广度遍历，将其左右儿子B、C结点放入队列。其结点表示第一个物品放入背包内，中B结点表示第一个物品放入背包内，这时背包内的容量16,还剩余的容量为3016=14,价值为453045。为16,还剩余的容量为30-16=14,价值为45。C结点表示第一个物品不妨入背包内。如图1010.第一个物品不妨入背包内。如图10.3BC2023-5-24左右孩子B、结点放入队列图10.3左右孩子、C结点放入队列上海师范大学计算机系胡金初8

《计算机算法》胡金初—PPT

10.20-1背包问题背包问题3)取出结点查找其儿子结点D、。结点表示将第3)取出B结点，查找其儿子结点、E。D结点表示将第取出结点，二个物品放入背包内，然后发现当结点D放入背包后容量二个物品放入背包内，然后发现当结点放入背包后容量大于背包可以承受的容量，所以D结点是不可行的结点是不可行的，大于背包可以承受的容量，所以结点是不可行的，就抛结点表示不把其次个物品放入背包内，弃，E结点表示不把其次个物品放入背包内，这时背包内结点表示不把其次个物品放入背包内的容量还是16,价值为45是可行的放入队列。是可行的，的容量还是，价值为是可行的，放入队列。如图10.4CE图10.4取出结点，查找其孩子结点、E取出B结点查找其孩子结点D、结点，

4)然后作为扩展结点遍历其儿子F、,结点F表示4)然后C作为扩展结点，遍历其儿子、G,结点表示然后作为扩展结点，第一个物品不放入背包内，而其次个物品放入背包内，第一个物品不放入背包内，而其次个物品放入背包内，则这时的背包内的容量为15,还剩余的容量为30-15=15,则这时的背包内的容量为，还剩余的容量为价值为25,结点是可行的显然G结点也是可行的结点是可行的，结点也是可行的，价值为，F结点是可行的，显然结点也是可行的，所以两个儿子结点都入队，如图10.5

以两个儿子结点都入队，如图EFG2023-5-24

作为扩展结点，图10.5C作为扩展结点，遍历其孩子、G作为扩展结点遍历其孩子F、上海师范大学计算机系胡金初9

《计算机算法》胡金初—PPT

10.20-1背包问题背包问题扩展E,得到儿子和。不可行不可行，可行可行。扩展，得到儿子J和K。J不可行，K可行。由于K是叶结点得到一个可行解，是叶结点，由于是叶结点，得到一个可行解，其价值为45。扩展F得到儿子L扩展F,得到儿子L、M。L结点表示将第三个物品放入背包内，这时背包内的容量为3030,个物品放入背包内，这时背包内的容量为30,价值为50到达M结点时背包内的容量为1550。15,价值为50。到达M结点时背包内的容量为15,价值为2525。都可行。价值为25。则L、M都可行。扩展G发现不是最优解。扩展G,发现不是最优解。最终得到最优值50。最终得到最优值。2023-5-24上海师范大学计算机系胡金初10

《计算机算法》胡金初—PPT

10.20-1背包问题背包问题表10.1两种方法的比较回溯法以深度优先在探寻过程中即使找到了最优解也不能马上确定它就是最优的，也不能马上确定它就是最优的，只有把它所有的可行解全都求出来以后才能确定最优解。来以后才能确定最优解。解决难以归纳一般规律解法的问其适用范围广，灵活性大，题，其适用范围广，灵活性大，在解一些列举方法的问题时特别可用。但是，其缺点也是明显的，可用。但是，其缺点也是明显的，即时间繁杂度较大；即时间繁杂度较大；因此在采用时还需要提防。时还需要提防。分支界限法以广度或最小花费优先通过最大堆可以确定下次要取的扩展结点，迅速向最优解靠拢。扩展结点，迅速向最优解靠拢。

可以求得最优解、平均速度快。可以求得最优解、平均速度快。支定界法可应用于大量组合优化问题。问题。其关键技术在于各结点权值如何估计，值如何估计，可以说一个分支限界求