cumt算法设计与分析期末考速通笔记（6）｜分支限界法

1 搜索方式与基本概念 #

分支：对当前状态产生下一步选择，例如拿或不拿一件物品。限界：估计该分支可能达到的最好结果，排除不可能改进已知最优解的分支。

活节点是已生成、等待继续处理的候选方案；当前扩展节点是正在生成孩子的节点。一个节点生成孩子后，符合条件的非叶孩子进入候选集合。

队列式看起来按层展开，但每次只取一个节点，队列可能同时含有相邻两层的节点，不是预先列好整棵树再一批处理。

2 背包状态与两种剪枝 #

本专题假设物品重量为正、价值非负，允许不选物品，只求一种最优方案。

容量W=4，最优解B+C，重量4、价值6。取舍按A、B、C记录，1表示拿，0表示不拿；10表示拿A、不拿B，C尚未决定。

约束剪枝： 重量超过W，不可能得到可行方案。

限界剪枝： 价值上界≤best，不可能产生更好的方案。

best是已经实际找到的可行解价值；上界只是估计，不能直接更新best。这里的上界估计价值，不是用O符号描述运行时间。

只求一种最优方案时，上界≤best可剪。若要求全部最优方案，上界等于best时仍可能有其他最优解，必须保留并正确记录并列方案。

3 队列式分支限界 #

每次取队首，生成合法且有希望的孩子放到队尾。下面采用简单上界：当前价值加所有尚未决定物品的价值之和。

本例完整方案生成时即比较并更新best，候选队列只存非叶状态。表中的队列是本步处理之后的状态：

节点1展开时，11超重，只把10加入队尾；但队首还排着0，因此下一步先处理0。队列[0,10]里，0只决定了A，10已经决定A和B。

节点10生成完整方案100，得到价值5；节点01生成011，更新best=6。最后取出00时，只剩价值3的C，上界3≤6，剪枝后队列为空。

出队时要再检查上界。 某节点入队时有希望，但等待过程中其他分支可能提高best，导致它出队时已经没有改进可能。

4 优先队列的取出规则 #

优先级看界，不只看当前已经取得的值。若P当前价值9、上界10，Q当前价值6、上界14，背包问题优先处理Q；但不保证Q最终能达到14。

仍用简单上界：根生成的1上界为5+3+3=11，0上界为3+3=6，先取1。1生成可行节点10，其上界为5+3=8，此时：

先进先出队列：先处理0，再处理10。
优先队列：先处理上界8的10，再处理上界6的0。

处理10后找到100、best=5；再处理0，01的上界6可保留，00的上界3可以剪去；处理01后找到011、best=6。找到第一个完整可行方案时只更新best，不能在候选仍有改进可能时直接宣布结束。

5 用可分割背包计算更紧的上界 #

简单上界忽略容量，例如根节点将三件价值全相加得到11，但容量4装不下总重量7。

更紧的上界：当前价值，加上剩余容量在尚未决定物品中按可分割背包求得的最大价值。允许拆分放宽了0–1约束，因此这个最优值不会低于真实0–1最优值。

必须先按单位价值排序 #

将每件物品的原编号、重量、价值作为整体，按价值/重量从高到低排序一次；之后搜索与上界计算都使用该固定顺序。输出方案时依据保留的原编号还原。

若未经排序就从前往后装，可能低估真实最优值，造成错误剪枝。例如容量2，先放重2值2的物品会得到2，但重2值8的另一件本来可以提供8。

上界不是剩余物品的平均单价 #

按单位价值从高到低，能整件装入的加整件价值；最后一件装不下时，才加“剩余容量×这一件的单位价值”。已决定不拿的物品不能重新参加计算。

例：当前价值5、剩余容量3；尚未决定的P重2值8，Q重3值3。先整装P增加8，再用剩余容量1取Q的一部分增加1，上界=5+8+1=14。不能用两件物品的平均单价代替这个过程。

原例中的6.5怎样得到 #

原例单位价值依次为A的5/3、B的1.5、C的1.5。根节点剩余容量4：先装完整A，得到5，剩余容量1；再取B的一半，增加1.5，上界为6.5。

真实最优价值6 ≤ 分数背包上界6.5 ≤ 简单上界11

6.5只是估算值；半件物品不满足0–1限制，不能据此把best更新为6.5。

上界函数伪代码 #

前提：物品已按单位价值降序排列，当前节点未超重；i是下一件尚未决定的物品。

计算上界(i,当前重量,当前价值)：
    剩余容量=W-当前重量
    上界=当前价值

    对j=i到n：
        如果剩余容量=0：退出循环

        如果w[j]≤剩余容量：
            上界=上界+v[j]
            剩余容量=剩余容量-w[j]
        否则：
            上界=上界+剩余容量×v[j]/w[j]
            退出循环

    返回上界

除法保留小数，3/2取1.5，不做整数截断。剩余物品都已用完时，即使还有容量，也不能重复拿物品凑满。

函数中的剩余容量、上界都是临时变量，不修改真实取舍记录或best。

6 优先队列式分支限界完整伪代码 #

以下只求一种最优方案。Q按节点上界从大到小取出，完整叶子方案生成时直接更新best，不进入Q。

将物品按价值/重量降序排序
// 原编号、重量、价值一起移动

best=0；bestChoice=全0数组
Q=空优先队列

建立根节点：
    i=1，重量=0，价值=0，取舍记录=[]
    上界=计算上界(1,0,0)
将根节点加入Q

当Q不为空：
    u=从Q取出上界最大的节点

    如果u.上界≤best：
        继续取下一个节点

    i=u.i
    对take依次取1、0：
        建立独立的孩子节点child：
            child.i=i+1
            child.重量=u.重量+take×w[i]
            child.价值=u.价值+take×v[i]
            child.取舍记录=复制u.取舍记录
            在child.取舍记录末尾追加take

        如果child.重量>W：
            跳过此孩子，尝试下一种取舍

        如果child.i>n：
            如果child.价值>best：
                best=child.价值
                bestChoice=复制child.取舍记录
        否则：
            child.上界=计算上界(
                child.i,child.重量,child.价值)
            如果child.上界>best：
                将child加入Q

按保留的原编号还原bestChoice
返回best和bestChoice

take=1时增加当前物品的重量、价值；take=0时重量、价值不变。两个孩子必须独立，不能改了拿分支的状态后，又把修改后的值用于不拿分支。

例：节点i=3、重量2、价值3、记录01，表示不拿A、拿B，准备决定C。拿C生成i=4、重量4、价值6、记录011；因为4>n=3，方案完整，用6与best比较。这里仍然是在所有物品决定完之后更新best。

7 考场检查 #

• 明确使用先进先出队列还是优先队列；不能把“当前价值最高”写成背包的上界优先规则。
• 写清物品排序前提，不能只对重量或价值数组单独排序。
• 上界只估计尚未决定的物品，已选价值单独加一次，已拒绝物品不能加回来。
• 完整可行方案才更新本实现的best；不能用不可行或分数方案更新。
• 入队与出队都考虑界，因为等待期间best可能改变。
• 排序O(nlog n)只是前处理，整个搜索最坏仍可能达到指数级数量的节点。
• 只求一种与要求全部最优方案的等号处理不同。

回溯的深度优先搜索、递归终止与入口调用见回溯法专题。装载、最大团和旅行路线的具体分支限界实例仍待补充。