應(yīng)用場景

分支限界法的求解目標(biāo)是找出滿足約束條件的一個解陵刹，或是在滿足約束條件的解中找出的在某種意義下的最優(yōu)解频敛。

裝載問題

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};      // 貨箱質(zhì)量數(shù)組
        float sumGoods = 0;  // s為所有貨箱的重量之和
        for (float g : goods) {
            sumGoods += g;
        }
        // 創(chuàng)建分支界限隊(duì)列搜索對象
        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;

    //求最優(yōu)裝載值
    public float maxLoading(float c, float[] goods) {
        Queue<Float> mq = new LinkedList<>(); // FIFO隊(duì)列
        mq.add((float) -1); // 初始化結(jié)點(diǎn)隊(duì)列银室，"-1"入隊(duì)標(biāo)記分層
        int n = goods.length; //貨箱個數(shù)
        int i = 0; // E-結(jié)點(diǎn)的層
        float ew = 0; // 當(dāng)前船的裝載量
        bestW = 0; // 目前的最優(yōu)值

        while (!mq.isEmpty()) { // 搜索子集空間樹
            if (ew + goods[i] <= c) { // 檢查E-結(jié)點(diǎn)的左孩子磺浙，貨箱i是否可以裝載
                addLiveNode(ew + goods[i], i, mq, n); // 貨箱i可以裝載
            }
            addLiveNode(ew, i, mq, n); // 右孩子總是可行的(不需要檢查)护盈，不裝載貨物i
            ew = mq.remove(); // 取下一個結(jié)點(diǎn)

            if (ew == -1) { // 到達(dá)層的尾部
                if (mq.isEmpty()) {
                    return bestW;
                }
                mq.add((float) -1);//每處理完一層讓"-1"入隊(duì)堂湖，以此來標(biāo)識"層"
                ew = mq.remove(); // 取下一個結(jié)點(diǎn)
                i++; // ew的層 （當(dāng)層次為n時闲先，搜索完全部葉結(jié)點(diǎn)，算法結(jié)束）
            }
        }
        return bestW;
    }

    //添加活結(jié)點(diǎn)(wt:當(dāng)前裝載量无蜂，i:當(dāng)前層數(shù))
    public void addLiveNode(float wt, int i, Queue<Float> mq, int n) {
        if (i == n - 1) { // 可行葉結(jié)點(diǎn)
            if (wt > bestW) {
                bestW = wt;  //當(dāng)前解由于當(dāng)前最優(yōu)解伺糠，更新最佳載重量
            }
        } else { // 非葉結(jié)點(diǎn)
            mq.add(wt);
        }
    }
}