数据结构与算法｜分支限界法

2022-04-25 305

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 类似回溯算法，也是一种在问题的解空间树 T 上搜索问题解的算法，但在一般情况下，分支节点界定算法与回溯算法的求解目标不同。回溯法的求解是找出 T 中满足条件约束的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是满足约束条件的解中找出达到某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

类似回溯算法，也是一种在问题的解空间树 T 上搜索问题解的算法，但在一般情况下，分支节点界定算法与回溯算法的求解目标不同。回溯法的求解是找出 T 中满足条件约束的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是满足约束条件的解中找出达到某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

所谓“分支”就是采用广度优先的策略，一次搜索 E-节点的所有分支，也就是相邻节点，抛弃不满足约束条件的节点，其余节点加入活节点表。然后从表中选择节点作为下一个 E-节点，继续搜索。

选择一个节点的方式不同，则回有几种不同的分支搜索方式：

FIFO 搜索

LIFO 搜索

优先队列式搜索

基本思想

由于求解的目标不同，导致分支界限法与回溯法在解空间树 T 上的搜索方式也不同。回溯法以深度优先的方式搜索空间树 T ，而分支界限法则以广度预先或最小消耗优先的方式搜索解空间树 T。

分支界限法以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的空间树是表示问题解空间的一颗语序树，常见的有子集树和排序树。在搜索问题的解空间树时，分支限界法与回溯法对当前拓展节点所使用的方式不同。在分支限界法中，每一个活节点只有一次机会成为拓展节点。活动节点一旦成为拓展节点，就一次性产生其所有子节点。这些子节点中，哪些导致步可行解或导致非最优解的子节点被舍弃，其余子节点加入活节点中，此后，从活动节点中取下一个下一个节点成为当前节点的拓展节点，并且重复上述节点拓展过程。这个过程一致持续到找到所求得解或活节点表为空时为止。

对某个节点进行搜索时，先估算出目标得解，在确定是否可以向下搜索（选择最小损耗节点进行搜索）在分支节点上，预先分别估算沿着它的各个儿子节点向下搜索的路径中，目标函数可能取得得界限，然后再把它得这些儿子节点和他们可能取得界限保存到一张节点表中，再从表中选择最小或者最大得节点向下搜索，一般采用优先队列维护这张表。

案例分析

有5个商品，重量分别为8,16,21,17,12，价值分别为8,14,16,11,7，背包的载重量为37，求装入背包的商品及其价值。如下表格所示：

物品	重量（w）	价值（v）	价值/重量（v/w）
1	8	8	1
2	16	14	0.875
3	21	16	0.762
4	17	11	0.64
5	12	7	0.583

问题分析

首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。

算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。

代码实现

package cn.zhengsh.t;
import java.util.PriorityQueue;
//定义节点中的参数以及优先级设置的对象
class ThingNode implements Comparable<ThingNode> {
    int weight;//该节点目前背包中的重量
    double value;//该节点目前背包中的总价值
    double upProfit;//该节点能够达到的价值上界
    int left;    //该节点是否属于左节点（用于最终构造最优解）
    int level;  //该节点是第几个物品的选择
    ThingNode father; //该节点的父节点
    public int compareTo(ThingNode node) {
        return Double.compare(node.upProfit, this.upProfit);
    }
    public ThingNode() {
    }
    public ThingNode(int weight, double value, double upProfit, int left, int level, ThingNode father) {
        this.weight = weight;
        this.value = value;
        this.upProfit = upProfit;
        this.left = left;
        this.level = level;
        this.father = father;
    }
}
public class Bag01 {
    int n = 5;
    int capacity = 37;
    // 已经按照价值排序排序
    int[] weight = {8, 16, 21, 17, 12};
    double[] value = {8, 14, 16, 11, 7};
    int maxValue = 0;
    int[] bestWay = new int[n];
    public void getMaxValue() {
        PriorityQueue<ThingNode> pq = new PriorityQueue<>();
        //构造一个初始化节点，属于-1层
        ThingNode initial = new ThingNode();
        initial.level = -1;
        initial.upProfit = 26;
        pq.add(initial);
        while (!pq.isEmpty()) {
            ThingNode fatherNode = pq.poll();
            //当已经搜索到叶子节点时
            if (fatherNode.level == n - 1) {
                if (fatherNode.value > maxValue) {
                    maxValue = (int) fatherNode.value;
                    for (int i = n - 1; i >= 0; i--) {
                        bestWay[i] = fatherNode.left;
                        fatherNode = fatherNode.father;
                    }
                }
            } else {
                //先统计其左节点信息，判断是否加入队列。
                if (weight[fatherNode.level + 1] + fatherNode.weight <= capacity) {
                    ThingNode newNode = new ThingNode();
                    newNode.level = fatherNode.level + 1;
                    newNode.value = fatherNode.value + value[fatherNode.level + 1];
                    newNode.weight = weight[fatherNode.level + 1] + fatherNode.weight;
                    newNode.upProfit = bound(newNode);
                    newNode.father = fatherNode;
                    newNode.left = 1;
                    if (newNode.upProfit > maxValue)
                        pq.add(newNode);
                }
                //向右节点搜索，其能够取到的价值上界通过父亲节点的上界减去本层物品的价值。
                if ((fatherNode.upProfit - value[fatherNode.level + 1]) > maxValue) {
                    ThingNode newNode2 = new ThingNode();
                    newNode2.level = fatherNode.level + 1;
                    newNode2.value = fatherNode.value;
                    newNode2.weight = fatherNode.weight;
                    newNode2.father = fatherNode;
                    newNode2.upProfit = fatherNode.upProfit - value[fatherNode.level + 1];
                    newNode2.left = 0;
                    pq.add(newNode2);
                }
            }
        }
    }
    //用于计算该节点的最高价值上界
    public double bound(ThingNode node) {
        double maxLeft = node.value;
        int leftWeight = capacity - node.weight;
        int templevel = node.level;
        //尽力依照单位重量价值次序装剩余的物品
        while (templevel <= n - 1 && leftWeight > weight[templevel]) {
            leftWeight -= weight[templevel];
            maxLeft += value[templevel];
            templevel++;
        }
        //不能装时，用下一个物品的单位重量价值折算到剩余空间。
        if (templevel <= n - 1) {
            maxLeft += value[templevel] / weight[templevel] * leftWeight;
        }
        return maxLeft;
    }
    public static void main(String[] args) {
        Bag01 b = new Bag01();
        b.getMaxValue();
        System.out.println("该背包能够取到的最大价值为:" + b.maxValue);
        System.out.println("取出的方法为:");
        for (int i : b.bestWay)
            System.out.print(i + "  ");
    }
}