分支界限法(BFS)

应用场景

分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出的在某种意义下的最优解。

装载问题

import java.util.LinkedList;
import java.util.Queue;

public class BestLoading {

    public static void main(String[] args) {
        float c1 = 12;  // 第一艘船的载重量
        float c2 = 10;  // 第二艘船的载重量
        float[] goods = {8, 6, 2, 3};      // 货箱质量数组
        float sumGoods = 0;  // s为所有货箱的重量之和
        for (float g : goods) {
            sumGoods += g;
        }
        // 创建分支界限队列搜索对象
        BranchLimitFIFOSearch bFis = new BranchLimitFIFOSearch();
        float bestW = bFis.maxLoading(c1, goods);
        if (sumGoods - bestW <= c2) {
            System.out.println("第一艘船装载" + bestW);
            System.out.println("第二艘船装载 " + (sumGoods - bestW));
        } else {
            System.out.println("无解!");
        }
    }
}

class BranchLimitFIFOSearch {
    float bestW;

    //求最优装载值
    public float maxLoading(float c, float[] goods) {
        Queue<Float> mq = new LinkedList<>(); // FIFO队列
        mq.add((float) -1); // 初始化结点队列，"-1"入队标记分层
        int n = goods.length; //货箱个数
        int i = 0; // E-结点的层
        float ew = 0; // 当前船的装载量
        bestW = 0; // 目前的最优值

        while (!mq.isEmpty()) { // 搜索子集空间树
            if (ew + goods[i] <= c) { // 检查E-结点的左孩子，货箱i是否可以装载
                addLiveNode(ew + goods[i], i, mq, n); // 货箱i可以装载
            }
            addLiveNode(ew, i, mq, n); // 右孩子总是可行的(不需要检查)，不装载货物i
            ew = mq.remove(); // 取下一个结点

            if (ew == -1) { // 到达层的尾部
                if (mq.isEmpty()) {
                    return bestW;
                }
                mq.add((float) -1);//每处理完一层让"-1"入队，以此来标识"层"
                ew = mq.remove(); // 取下一个结点
                i++; // ew的层 （当层次为n时，搜索完全部叶结点，算法结束）
            }
        }
        return bestW;
    }

    //添加活结点(wt:当前装载量，i:当前层数)
    public void addLiveNode(float wt, int i, Queue<Float> mq, int n) {
        if (i == n - 1) { // 可行叶结点
            if (wt > bestW) {
                bestW = wt;  //当前解由于当前最优解，更新最佳载重量
            }
        } else { // 非叶结点
            mq.add(wt);
        }
    }
}