分支界限法及常见例子

  分支界限法作为一种常见的算法思想，其概念为：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

1、基本策略

  分支界限法的策略是：在当前节点（扩展节点）处，先生成其所有的子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。

2、适用场景

  分支限界法适用于求解最优化问题，并且是小型问题。

3、使用步骤

  使用分支界限法的基本步骤：
   1>如果问题的目标为最小化，则设定最优解的值Z=∞
   2>根据分枝法则，从尚未被洞悉节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点。
   3>计算每一个新分枝出来的节点的下限值。
   4>对每一节点进行洞悉条件测试，若节点满足以下任意一个条件，则此节点可洞悉而不再被考虑：
此节点的下限值大于等于Z值。已找到在此节点中，具最小下限值的可行解；若此条件成立，则需比较此可行解与Z值，若前者较小，则需更新Z值，以此为可行解的值。
   5>判断是否仍有尚未被洞悉的节点，如果有，则进行步骤二，如果已无尚未被洞悉的节点，则演算停止，并得到最优解。

4、常见例子

  分支界限法在实际运用中，用到的不多，因为实现过程较为复杂，本篇文章用0-1背包问题来探究回溯法的使用方法。

5、0-1背包问题

  在该问题中，需要一个背包实体类，该实例类需要包含三个属性：重量、价值和单位价值，单位价值的存在主要为了给不同物品排序。实例代码如下：

public class Knapsack implements Comparable<Knapsack> {
    /*物品重量*/
    private int weight;
    /*物品价值*/
    private int value;
    /*单位重量价值*/
    private int unitValue;

    public Knapsack(int weight, int value){
        this.weight = weight;
        this.value = value;
        this.unitValue = (weight == 0) ? 0 : value/weight;
    }

    public int getWeight(){
        return weight;
    }

    public void setWeight(int weight){
        this.weight = weight;
    }

    public int getValue(){
        return value;
    }

    public void setValue(int value){
        this.value = value;
    }

    public int getUnitValue(){
        return unitValue;
    }

    @Override
    public int compareTo(Knapsack snapsack) {
        int value = snapsack.unitValue;
        if (unitValue > value)
            return 1;
        if (unitValue < value)
            return -1;
        return 0;
    }
}

  接下来看一下具体实现过程中用到的变量：

    /*物品数组*/
    private Knapsack[] knapsacks;
    /*背包承重量*/
    private int totalWeight;
    /*物品数*/
    private int num;
    /*可以获得的最大价值*/
    private int bestValue;

  分支界限法特殊的地方在于创建了一个节点类，该类可以表示将某物品放入或不放入背包。实例代码如下：

    /*当前操作的节点，放入物品或不放入物品*/
    class Node {
        /*当前放入物品的重量*/
        private int currWeight;
        /*当前放入物品的价值*/
        private int currValue;
        /*不放入当前物品可能得到的价值上限*/
        private int noPutValue;
        /*当前操作物品的索引*/
        private int index;
        public Node(int currWeight, int currValue, int index) {
            this.currWeight = currWeight;
            this.currValue = currValue;
            this.index = index;
        }
    }

  当处理一个物品n时，存在；两种选择：物品放入背包中或物品不放入背包中（在该方法中用两个节点表示），根据约束条件舍去无效情况。当前物品n放入背包中时，获取当前最大总价值，下一个物品n+1也存在放入背包和不放入背包中两个节点。当物品n不放入背包时，上个节点的最总价值为当前节点的最总价值，下一个物品n+1仍然存在放入背包和不放入背包两个节点。持续以此类推，最终根据不同的放入情况选择一个最优解作为可以放入背包物品的最大总价值。 示例代码如下：

public class ZeroAndOnePackage {

    /*物品数组*/
    private Knapsack[] knapsacks;
    /*背包承重量*/
    private int totalWeight;
    /*物品数*/
    private int num;
    /*可以获得的最大价值*/
    private int bestValue;
    
    public static void main(String[] args) {
        Knapsack[] knapsack = new Knapsack[] { 
        		new Knapsack(2, 13),new Knapsack(1, 10), new Knapsack(3, 24), new Knapsack(2, 15),
                new Knapsack(4, 28), new Knapsack(5, 33), new Knapsack(3, 20),new Knapsack(1, 8)};
        int totalWeight = 12;
        ZeroAndOnePackage zeroAndOnePackage = new ZeroAndOnePackage(knapsack, totalWeight);

        zeroAndOnePackage.findMaxValue();
        System.out.println("最大价值为："+zeroAndOnePackage.getBestValue());
    }

    public ZeroAndOnePackage(Knapsack[] knapsacks, int totalWeight) {
        super();
        this.knapsacks = knapsacks;
        this.totalWeight = totalWeight;
        this.num = knapsacks.length;
        /*物品依据单位重量价值进行排序*/
        Arrays.sort(knapsacks, Collections.reverseOrder());
    }

    public void findMaxValue() {
        LinkedList<Node> nodeList = new LinkedList<Node>();

        /*起始节点当前重量和当前价值均为0*/
        nodeList.add(new Node(0, 0, 0));
        while (!nodeList.isEmpty()) {
            /*取出放入队列中的第一个节点*/
            Node node = nodeList.pop();

            if (node.noPutValue >= bestValue && node.index < num) {
                /*左节点：该节点代表物品放入背包中，上个节点的价值+本次物品的价值为当前价值*/
                int leftWeight = node.currWeight + knapsacks[node.index].getWeight();
                int leftValue = node.currValue + knapsacks[node.index].getValue();
                Node left = new Node(leftWeight, leftValue, node.index + 1);
                /*放入当前物品后可以获得的价值上限*/
                left.noPutValue = getPutValue(left);
                /*当物品放入背包中左节点的判断条件为保证不超过背包的总承重*/
                if (left.currWeight <= totalWeight && left.noPutValue > bestValue) {
                    /*将左节点添加到队列中*/
                    nodeList.add(left);
                    if (left.currValue > bestValue) {
                        /*物品放入背包不超重，且当前价值更大，则当前价值为最大价值*/
                        bestValue = left.currValue;
                    }
                }
                /*右节点：该节点表示物品不放入背包中，上个节点的价值为当前价值*/
                Node right = new Node(node.currWeight, node.currValue,node.index + 1);
                /*不放入当前物品后可以获得的价值上限*/
                right.noPutValue = getPutValue(right);
                if (right.noPutValue >= bestValue) {
                    /*将右节点添加到队列中*/
                    nodeList.add(right);
                }
            }
        }
    }

    /*当前操作的节点，放入物品或不放入物品*/
    class Node {
        /*当前放入物品的重量*/
        private int currWeight;
        /*当前放入物品的价值*/
        private int currValue;
        /*不放入当前物品可能得到的价值上限*/
        private int noPutValue;
        /*当前操作物品的索引*/
        private int index;
        public Node(int currWeight, int currValue, int index) {
            this.currWeight = currWeight;
            this.currValue = currValue;
            this.index = index;
        }
    }

    /*价值上限=节点现有价值+背包剩余容量*剩余物品的最大单位重量价值
     *当物品由单位重量的价值从大到小排列时，计算出的价值上限大于所有物
     *品的总重量，否则小于物品的总重量当放入背包的物品越来越来越多时，
     *价值上限也越来越接近物品的真实总价值
     */
    private int getPutValue(Node node) {
        /*获取背包剩余容量*/
        int surplusWeight = totalWeight - node.currWeight;
        int value = node.currValue;
        int i = node.index;

        while (i < this.num && knapsacks[i].getWeight() <= surplusWeight) {
            surplusWeight -= knapsacks[i].getWeight();
            value += knapsacks[i].getValue();
            i++;
        }
        /*当物品超重无法放入背包中时，可以通过背包剩余容量*下个物品单位重量的价值计算出物品的价值上限*/
        if (i < this.num) {
            value += knapsacks[i].getUnitValue() * surplusWeight;
        }
        return value;
    }

    public int getBestValue() {
        return bestValue;
    }
}

  测试结果为：

最大价值为：90

本文地址：https://blog.csdn.net/m0_37741420/article/details/107594452