以下均轉載于：五大常用算法-分支界限,加入了一些我自己的想法
1.基本描述
類似于回溯法拳昌，也是一種在問題的解空間樹T上搜索問題解的算法竞滓。但在一般情況下纤壁，分支限界法與回溯法的求解目標不同叁丧。回溯法的求解目標是找出T中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解冈止，或是在滿足約束條件的解中找出使某一目標函數(shù)值達到極大或極小的解狂票，即在某種意義下的最優(yōu)解。
分支搜索算法
所謂“分支”就是采用廣度優(yōu)先的策略熙暴，依次搜索E-結點的所有分支闺属，也就是所有相鄰結點慌盯，拋棄不滿足約束條件的結點，其余結點加入活結點表掂器。然后從表中選擇一個結點作為下一個E-結點亚皂，繼續(xù)搜索。
選擇下一個E-結點的方式不同唉匾，則會有幾種不同的分支搜索方式孕讳。
1.FIFO搜索
2.LIFO搜索
3.優(yōu)先隊列式搜索
2.分支限界法的一般過程
由于求解目標不同，導致分支限界法與回溯法在解空間樹T上的搜索方式也不相同巍膘。回溯法以深度優(yōu)先的方式搜索解空間樹T，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹T芋簿。
1.分支限界法的搜索策略是：
在擴展結點處峡懈，先生成其所有的兒子結點（分支），然后再從當前的活結點表中選擇下一個擴展對點与斤。為了有效地選擇下一擴展結點肪康，以加速搜索的進程，在每一活結點處撩穿，計算一個函數(shù)值（限界）磷支，并根據(jù)這些已計算出的函數(shù)值，從當前活結點表中選擇一個最有利的結點作為擴展結點食寡，使搜索朝著解空間樹上有最優(yōu)解的分支推進雾狈，以便盡快地找出一個最優(yōu)解
2.分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。
問題的解空間樹是表示問題解空間的一棵有序樹抵皱，常見的有子集樹和排列樹善榛。在搜索問題的解空間樹時，分支限界法與回溯法對當前擴展結點所使用的擴展方式不同呻畸。在分支限界法中移盆，每一個活結點只有一次機會成為擴展結點∩宋活結點一旦成為擴展結點咒循，就一次性產(chǎn)生其所有兒子結點。在這些兒子結點中绞愚，那些導致不可行解或導致非最優(yōu)解的兒子結點被舍棄叙甸，其余兒子結點被子加入活結點表中。此后爽醋，從活結點表中取下一結點成為當前擴展結點蚁署，并重復上述結點擴展過程。這個過程一直持續(xù)到找到所求的解或活結點表為空時為止蚂四。
3.回溯法和分支界限法的一些區(qū)別
回溯法和分支限界法的一些區(qū)別：
- 方法對解空間樹的搜索方式
- 存儲結點的常用數(shù)據(jù)結構
- 結點存儲特性常用應用
- 回溯法深度優(yōu)先搜索堆椆飧辏活結點的所有可行子結點被遍歷后才被從棧中彈出找出滿足約束條件的所有解
- 分支限界法廣度優(yōu)先或最小消耗優(yōu)先搜索隊列哪痰、優(yōu)先隊列每個結點只有一次成為活結點的機會找出滿足約束條件的一個解或特定意義下的最優(yōu)解
4.舉個例子
還是上文回溯算法中的例子，給定一組數(shù)組nums久妆，再給定一個目標值target,找出集合nums的所有子集使其之和剛好為目標值晌杰，nums中的數(shù)只能使用一次。不過我們稍作修改筷弦，現(xiàn)在只需要找到一個子集即可肋演。雖然這個例子不算優(yōu)化問題，但是卻很好的展示了只要滿足條件即可烂琴。
下面按照思路進行求解爹殊。
4.1構造解空間樹
這里和回溯算法中解空間樹其實相同，我們采用子集樹
4.2確定搜索方式
這里我使用的FIFO的隊列形式奸绷，使用該隊列維護一張活節(jié)點表梗夸，隊首為擴展節(jié)點。
4.3利用剪枝函數(shù)進行界限分割
假定我們給出的數(shù)組為
nums = {1,1,2,3,4,5,6},target=9,那么現(xiàn)在有一種情況是1+1+2=4,當前節(jié)點為第3層（從第0層開始）号醉，那么其左子樹則為1+1+2+3=7滿足條件反症，那么需不需要進入其右子樹呢？其右子樹表示為1+1+2+0+xxx,即不加入第3層畔派，下面還有3層為4,5,6铅碍。計算上界為1+1+2+4+5+6>9的，這樣說明第3層的右子樹可能存在解线椰，我們需要遍歷胞谈，但是考慮另一種情況，如果我把nums改為{1,1,2,3,1,1,1},則右子樹上界為1+1+2+0+1+1+1=7<9,顯然就算下面所有都加完士嚎，都不能達到9呜魄，不需要搜索右子樹。
以圖的形式再次說明
下面是整體代碼
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
/**
* 分支限界法
*/
static int[] nums = {1,1,2,3,4,5,6};
static int target = 9;
static int n = nums.length;
public static void main(String[] args) {
solve();
}
private static void solve() {
boolean[] currentX = new boolean[n];
//這里采用FIFO隊列存儲活節(jié)點
Queue<Node> queue = new LinkedList<Node>();
int i = 0;
int currentValue = 0;
int up;
do {
//檢查左子樹可行性
if(currentValue+nums[i] < target) {
//進入左子樹
currentX[i] = true;
queue.add(new Node(currentX.clone(),currentValue+nums[i] ,i+1));
}else if (currentValue+nums[i] == target) {
//如果產(chǎn)生可行解
currentX[i] = true;
System.out.println(Arrays.toString(currentX));
break;
}
up = bound(i);
if(currentValue+up >= target) {
//進入右子樹
currentX[i] = false;
queue.add(new Node(currentX.clone(),currentValue,i+1));
}
//取得擴展節(jié)點
Node currentNode = queue.poll();
currentX = currentNode.x;
currentValue = currentNode.vlaue;
i = currentNode.level;
}while(!queue.isEmpty());
}
private static class Node{
boolean[] x;//用于恢復現(xiàn)場莱衩，記錄其父節(jié)點及其以上加入情況
int vlaue;//當前累加值
int level;//當前是第幾層
public Node(boolean x[],int vlaue, int level) {
super();
this.x = x;
this.vlaue = vlaue;
this.level = level;
}
}
//剪枝函數(shù)
private static int bound(int i) {
int sum = 0;
i++;
for(;i<n;i++) {
sum+=nums[i];
}
return sum;
}
}
運行結果如下：
[true, true, false, true, true, false, false]
即：1+1+3+4=9
下面在給出0-1背包問題的分支限界解法爵嗅。
0-1背包問題：給定一些物品，每個物品均有其價格和重量笨蚁，現(xiàn)有一個有限容量的背包睹晒，問如何選擇物品才能使得所獲價值最大，物品不能分塊裝括细。
物品:
weight = {2, 2, 6, 5, 4};
value = {6, 3, 5, 4, 6};
容量:
c = 10;
代碼如下：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
/**
* 分支界限法伪很，解決0-1背包問題
*/
static int bestValue = 0;
static int[] weight = {2, 2, 6, 5, 4};
static int[] value = {6, 3, 5, 4, 6};
static int c = 10;
static int n = weight.length;
static boolean[] bestX = new boolean[n];
public static void main(String[] args) {
//對物品進行按照性價比預排序，因為總是期望性價比高的先存放（當然也可以自定義規(guī)則）
int[] oldIndex = selSort();
solve();
//恢復原序列
boolean[] realX = new boolean[n];
int valueS =0;
for (int i = 0; i < bestX.length; i++) {
realX[oldIndex[i]] = bestX[i];
if(bestX[i]){
valueS+=value[i];
}
}
System.out.println(Arrays.toString(realX));
System.out.println("vlaue:"+valueS);
}
/*
* 使用簡單選擇排序奋单，數(shù)據(jù)量大時可選擇快速排序锉试，堆排，歸并排序等高效排序算法
*/
private static int[] selSort() {
float[] p = new float[weight.length];
int[] oldeIndex = new int[p.length];
for (int i = 0; i < p.length; i++) {
p[i] = (float) value[i] / weight[i];
oldeIndex[i] = i;
}
//用來存儲排序后览濒，元素在原來數(shù)組中的位置呆盖，方便后續(xù)恢復信息,不要求按原數(shù)組輸出可不用這一步
for (int i = 0; i < p.length - 1; i++) {
for (int j = i + 1; j < p.length; j++) {
if (p[i] < p[j]) {
float tempP = p[i];
p[i] = p[j];
p[j] = tempP;
int tempW = weight[i];
weight[i] = weight[j];
weight[j] = tempW;
int tempV = value[i];
value[i] = value[j];
value[j] = tempV;
int tempI = oldeIndex[i];
oldeIndex[i] = oldeIndex[j];
oldeIndex[j] = tempI;
}
}
}
return oldeIndex;
}
private static void solve() {
int i = 0;
int currentValue = 0;
int currentWeight = 0;
boolean[] currentX = new boolean[weight.length];
//申請活節(jié)點FIFO隊列
Queue<Node> queue = new LinkedList<Node>();
do {
//判定左子樹可行性
if (currentWeight + weight[i] <= c) {
currentX[i] = true;
queue.add(new Node(currentX.clone(), currentValue + value[i], currentWeight + weight[i], i + 1));
//判斷是否需要更新最優(yōu)解
if (currentValue + value[i] > bestValue) {
bestValue = currentValue + value[i];
bestX = currentX.clone();
}
}
//計算上界
if (currentValue + bound(i, currentWeight) >= bestValue) {
//可以進入右子樹
currentX[i] = false;
queue.add(new Node(currentX.clone(), currentValue, currentWeight, i + 1));
}
//更新擴展節(jié)點
Node currrentNode = queue.poll();
currentValue = currrentNode.currentValue;
currentWeight = currrentNode.currentWeight;
currentX = currrentNode.x;
i = currrentNode.level;
} while (!queue.isEmpty() && i != n);
}
private static float bound(int i, int currentWeight) {
i++;
float p = 0;
while (currentWeight <= c && i < n) {
p += value[i];
currentWeight += weight[i];
}
if (i < n) {
//刪除多裝的一個
p -= value[i];
currentWeight -= weight[i];
p += (c - currentWeight) * ((float) (value[i]) / (weight[i]));
}
return p;
}
private static class Node {
boolean[] x;//保存背包中以存放的物品信息
int currentValue;
int currentWeight;
int level;
public Node(boolean[] x, int currentValue, int currentWeight, int level) {
this.x = x;
this.currentValue = currentValue;
this.currentWeight = currentWeight;
this.level = level;
}
}
}
執(zhí)行結果:
[true, true, false, false, true]
vlaue:15
即：第1,2,5個物品拖云，價值6+3+6=15，重量2+2+4 = 8
