一、基本描述

類似于回溯法，也是一種在問(wèn)題的解空間樹T上搜索問(wèn)題解的算法。但在一般情況下，分支限界法與回溯法的求解目標(biāo)不同。 回溯法 的求解目標(biāo)是找出T中滿足約束條件的 所有解 ，而 分支限界法 的求解目標(biāo)則是找出 滿足約束條件的一個(gè)解 ，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到 極大或極小的解 ，即在某種意義下的 最優(yōu)解 。

（1）分支搜索算法

所謂“分支”就是采用廣度優(yōu)先的策略，依次搜索E-結(jié)點(diǎn)的所有分支，也就是所有相鄰結(jié)點(diǎn)，拋棄不滿足約束條件的結(jié)點(diǎn)，其余結(jié)點(diǎn)加入活結(jié)點(diǎn)表。然后從表中選擇一個(gè)結(jié)點(diǎn)作為下一個(gè)E-結(jié)點(diǎn)，繼續(xù)搜索。

選擇下一個(gè)E-結(jié)點(diǎn)的方式不同，則會(huì)有幾種不同的分支搜索方式。

1）FIFO搜索

2）LIFO搜索

3）優(yōu)先隊(duì)列式搜索

（2）分支限界搜索算法

二、分支限界法的一般過(guò)程

由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法在解空間樹T上的搜索方式也不相同。 回溯法以深度優(yōu)先的方式搜索解空間樹T ，而 分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹T 。

分支限界法的 搜索策略是 ：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支），然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展對(duì)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，以加速搜索的進(jìn)程，在每一活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界），并根據(jù)這些已計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。

分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹。問(wèn)題的 解空間樹是表示問(wèn)題解空間的一棵有序樹，常見(jiàn)的有子集樹和排列樹 。在搜索問(wèn)題的解空間樹時(shí)，分支限界法與回溯法對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)所使用的擴(kuò)展方式不同。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被子加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時(shí)為止。

三、回溯法和分支限界法的一些區(qū)別

有一些問(wèn)題其實(shí)無(wú)論用回溯法還是分支限界法都可以得到很好的解決，但是另外一些則不然。也許我們需要具體一些的分析——到底何時(shí)使用分支限界而何時(shí)使用回溯呢？

回溯法和分支限界法的一些區(qū)別：

方法對(duì)解空間樹的搜索方式 存儲(chǔ) 結(jié)點(diǎn)的常用數(shù)據(jù)結(jié)構(gòu) 結(jié)點(diǎn) 存儲(chǔ) 特性常用應(yīng)用

回溯法深度優(yōu)先搜索堆棧活結(jié)點(diǎn)的所有可行子結(jié)點(diǎn)被遍歷后才被從棧中彈出找出滿足約束條件的所有解

分支限界法廣度優(yōu)先或最小消耗優(yōu)先搜索隊(duì)列、優(yōu)先隊(duì)列每個(gè)結(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)的機(jī)會(huì)找出滿足約束條件的一個(gè)解或特定意義下的最優(yōu)解

旅行售貨員問(wèn)題用回溯法貌似更容易實(shí)現(xiàn)一些，網(wǎng)上代碼很多。這里給出用分支限界法的java實(shí)現(xiàn)。

四、應(yīng)用示例

問(wèn)題描述：
某售貨員要到若干城市去推銷商品，已知各城市之間的路程（或旅費(fèi)）。他要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一遍，最后回到駐地的路線，使總的路程（或旅費(fèi)）最小。各個(gè)城市之間可能是有向連通的、無(wú)向連通的、以及存在某個(gè)城市不連通的情況，你的程序應(yīng)該能夠處理所有可能的情況。如下圖表示各個(gè)城市間無(wú)向連通。










輸入：

第一行為一個(gè)整數(shù) n(n<=10) ，表示城市的總個(gè)數(shù)。接下來(lái)是一個(gè) n*n 的矩陣，用來(lái)表示城市間的連通情況以及花費(fèi)，例如 path[i][j]=len ， len=-1 表示從城市 i 到城市 j 沒(méi)有通路， len>0 表示從 i 到 j 的路程長(zhǎng)度為 len 。對(duì)于上面圖示的問(wèn)題我們可以 按照下面方式 輸入：

4
-13064
30-1510
65-120
41020-1

輸出：

輸出占一行，對(duì)于給定的問(wèn)題，如果找到了最小路程（花費(fèi)），輸出該最小花費(fèi)，如果沒(méi)有通路可以到達(dá)每個(gè)城市，則輸出 -1 。

輸入樣例：

4
-13064
30-1510
65-120
41020-1

輸出樣例：

25

代碼：

//旅行售貨員問(wèn)題，用分支限界法實(shí)現(xiàn) 2010-10-28

import java.util.Scanner;

public class Main
{

//Main
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
int n=0;//結(jié)點(diǎn)的個(gè)數(shù)
String line=s.nextLine();//讀入n
n=Integer.parseInt(line);
a=new float[n][n];
int []vv=new int[n];

for(int i=0;i<n;i++)
{
line=s.nextLine();
String []sArray=line.split(" ");
for(int j=0;j<sArray.length;j++)
{
a[i][j]=Integer.parseInt(sArray[j]);
}
}
System.out.println(bbTsp(vv));
}//Main


static float [][]a;//圖的鄰接矩陣
//static float a[][]={{-1,-1,-1,2},{2,-1,-1,-1},{1,3,-1,-1},{-1,-1,1,-1}};
//static float a[][]={{-1,30,6,4},{30,-1,5,10},{6,5,-1,20},{4,10,20,-1}};
//static float a[][]={{5,5,5,5},{5,5,5,5},{5,5,5,5},{5,5,5,5}};

private static class HeapNode implements Comparable
{
float lcost,//子樹費(fèi)用下界
cc,//當(dāng)前費(fèi)用
rcost;//X[s:n-1]中頂點(diǎn)最小出邊費(fèi)用和
int s;//根節(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑為X[0:s]
int []x;//需要進(jìn)一步搜索的結(jié)點(diǎn)是x[s+1:n-1]

//HeapNode的構(gòu)造函數(shù)
HeapNode(float lc,float ccc,float rc,int ss,int []xx)
{
lcost=lc;
cc=ccc;
s=ss;
x=xx;
}//HeapNode 構(gòu)造函數(shù)

public int compareTo(Object x)
{
float xlc=((HeapNode)x).lcost;
if(lcost<xlc)
return -1;
if(lcost==xlc)
return 0;
return 1;
}

}//class HeapNode

public static int bbTsp(int []v)
{
int n=v.length;
MinHeap heap=new MinHeap(100);
float []minOut=new float[n];//minOut[i]是頂點(diǎn)i的最小出邊費(fèi)用
float minSum=0;//最小出邊費(fèi)用和

//計(jì)算最小出邊費(fèi)用和
for(int i=0;i<n;i++)
{
float min=Float.MAX_VALUE;
for(int j=0;j<n;j++)
{
if(a[i][j]!=-1&&a[i][j]<min)
min=a[i][j];//有回路
}//for j

if(min==Float.MAX_VALUE)
{
return -1;//無(wú)回路
}//if

minOut[i]=min;
minSum+=min;
}//for i

//初始化
int []x=new int[n];
for(int i=0;i<n;i++)
{
x[i]=i;
}
HeapNode enode=new HeapNode(0,0,minSum,0,x);
float bestc=Float.MAX_VALUE;

//搜索排列空間樹
while(enode!=null&&enode.s<n-1)
{
//System.out.println(bestc);
x=enode.x;
if(enode.s==n-2)//葉子結(jié)點(diǎn)
{
if(a[x[n-2]][x[n-1]]!=-1&&
a[x[n-1]][1]!=-1||
bestc==Float.MAX_VALUE)//當(dāng)前最優(yōu)解還不存在的情況
{
bestc=enode.cc+a[x[n-2]][x[n-1]]+a[x[n-1]][0];
enode.cc=bestc;
enode.lcost=bestc;
enode.s++;
heap.put(enode);
}
}//if(enode.s==n-2)

//if(enode.s!=n-2)
else
{
for(int i=enode.s+1;i<n;i++)
{
if(a[x[enode.s]][x[i]]!=-1)
{
float cc=enode.cc+a[x[enode.s]][x[i]];
float rcost=enode.rcost-minOut[x[enode.s]];
float b=cc+rcost;
if(b<bestc)
{
int []xx=new int[n];
for(int j=0;j<n;j++)
xx[j]=x[j];
xx[enode.s+1]=x[i];
xx[i]=x[enode.s+1];
HeapNode node=new HeapNode(b,cc,rcost,enode.s+1,xx);
heap.put(node);
}//if(b<bestc)
}//if 可行兒子結(jié)點(diǎn)
}//for
}//else,if(enode.s!=n-2)

enode=(HeapNode)heap.removeMin();
}//while
for(int i=0;i<n;i++)
v[i]=x[i];
return (int)bestc;
}//Class bbTsp



//構(gòu)造最小堆
public static class MinHeap
{
private HeapNode[] heapArray; // 堆容器
private int maxSize; // 堆的最大大小
private int currentSize=0; // 堆大小

//構(gòu)造函數(shù)
public MinHeap(int _maxSize)
{
maxSize = _maxSize;
heapArray = new HeapNode[maxSize];
currentSize = 0;
}

//自上而下調(diào)整
public void filterDown(int start, int endOfHeap)
{
int i = start;
int j = 2 * i + 1; // j是i的左子女位置
HeapNode temp = heapArray[i];

while (j <= endOfHeap)
{ // 檢查是否到最后位置
if (j < endOfHeap // 讓j指向兩子女中的小者
&& heapArray[j].cc > heapArray[j + 1].cc)
{
j++;
}
if (temp.cc <= heapArray[j].cc)
{ // 小則不做調(diào)整
break;
} else
{ // 否則小者上移，i，j下降
heapArray[i] = heapArray[j];
i = j;
j = 2 * j + 1;
}
}
heapArray[i] = temp;
}//filterDown

//自下而上的調(diào)整:從結(jié)點(diǎn)start開(kāi)始到0為止，自下向上比較，如果子女的值小于雙親結(jié)點(diǎn)的值則互相交換
public void filterUp(int start)
{
int j = start;
int i = (j - 1) / 2;
HeapNode temp = heapArray[j];

while (j > 0)
{ // 沿雙親結(jié)點(diǎn)路徑向上直達(dá)根節(jié)點(diǎn)
if (heapArray[i].cc <= temp.cc)
{// 雙親結(jié)點(diǎn)值小，不調(diào)整
break;
} else {// 雙親結(jié)點(diǎn)值大，調(diào)整
heapArray[j] = heapArray[i];
j = i;
i = (i - 1) / 2;
}
heapArray[j] = temp; // 回送
}
}//filterUp

//插入結(jié)點(diǎn)
public void put(HeapNode node)
{
HeapNode newNode = node;
heapArray[currentSize] = newNode;
filterUp(currentSize);
currentSize++;

}//put

//刪除堆中的最小值
public HeapNode removeMin()
{
HeapNode root = heapArray[0];
heapArray[0] = heapArray[currentSize - 1];
currentSize--;
filterDown(0, currentSize - 1);
return root;
}
}//class MinHeap
}//class Main

常用算法五（分支限界法）