分支限界法與回溯法

（1）求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。 （2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。

分支限界法的基本思想

分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。 此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。

常見的兩種分支限界法

（1）隊列式(FIFO)分支限界法 按照隊列先進先出（FIFO）原則選取下一個結(jié)點為擴展結(jié)點。 （2）優(yōu)先隊列式分支限界法 按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的結(jié)點成為當(dāng)前擴展結(jié)點。

一、單源最短路徑問題

1、問題描述

在下圖所給的有向圖G中，每一邊都有一個非負邊權(quán)。要求圖G的從源頂點s到目標頂點t之間的最短路徑。

下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點旁邊的數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長。

找到一條路徑：

目前的最短路徑是8，一旦發(fā)現(xiàn)某個結(jié)點的下界不小于這個最短路進，則剪枝：

同一個結(jié)點選擇最短的到達路徑：

2.剪枝策略

在算法擴展結(jié)點的過程中，一旦發(fā)現(xiàn)一個結(jié)點的下界不小于當(dāng)前找到的最短路長，則算法剪去以該結(jié)點為根的子樹。

在算法中，利用結(jié)點間的控制關(guān)系進行剪枝。從源頂點s出發(fā)，2條不同路徑到達圖G的同一頂點。由于兩條路徑的路長不同，因此可以將路長長的路徑所對應(yīng)的樹中的結(jié)點為根的子樹剪去。

3.算法思想

解單源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結(jié)點表。其優(yōu)先級是結(jié)點所對應(yīng)的當(dāng)前路長。

算法從圖G的源頂點s和空優(yōu)先隊列開始。結(jié)點s被擴展后，它的兒子結(jié)點被依次插入堆中。此后，算法從堆中取出具有最小當(dāng)前路長的結(jié)點作為當(dāng)前擴展結(jié)點，并依次檢查與當(dāng)前擴展結(jié)點相鄰的所有頂點。如果從當(dāng)前擴展結(jié)點i到頂點j有邊可達，且從源出發(fā)，途經(jīng)頂點i再到頂點j的所相應(yīng)的路徑的長度小于當(dāng)前最優(yōu)路徑長度，則將該頂點作為活結(jié)點插入到活結(jié)點優(yōu)先隊列中。這個結(jié)點的擴展過程一直繼續(xù)到活結(jié)點優(yōu)先隊列為空時為止。

實現(xiàn)

* 作者：chinazhangjie

* 郵箱：chinajiezhang@gmail.com

* 開發(fā)語言：C++

* 開發(fā)環(huán)境：Mircosoft Virsual Studio 2008

* 時間: 2010.11.01

*/

#include

#include

#include

#include

using namespacestd;

structnode_info

{

public:

node_info(inti,intw)

: index(i),weight(w){}

node_info()

: index(0),weight(0){}

node_info(constnode_info & ni)

: index(ni.index),weight(ni.weight){}

friend

booloperator < (constnode_info& lth,constnode_info& rth){

returnlth.weight > rth.weight;// 為了實現(xiàn)從小到大的順序

}

public:

intindex;// 結(jié)點位置

intweight;// 權(quán)值

};

structpath_info

{

public:

path_info()

: front_index(0),weight(numeric_limits::max()){}

public:

intfront_index;

intweight;

};

// single source shortest paths

classss_shortest_paths

{

public:

ss_shortest_paths(constvector >& g,intend_location)

:no_edge(-1),end_node(end_location),node_count(g.size()),graph(g)

{}

// 打印最短路徑

voidprint_spaths()const{

cout << "min weight : " << shortest_path << endl;

cout << "path: ";

copy(s_path_index.rbegin(),s_path_index.rend(),

ostream_iterator (cout," "));

cout << endl;

}

// 求最短路徑

voidshortest_paths(){

vector path(node_count);

priority_queue > min_heap;

min_heap.push(node_info(0,0));// 將起始結(jié)點入隊

while(true){

node_info top = min_heap.top();// 取出最大值

min_heap.pop();

// 已到達目的結(jié)點

if(top.index == end_node){

break;

}

// 未到達則遍歷

for(inti = 0;i < node_count; ++ i){

// 頂點top.index和i間有邊，且此路徑長小于原先從原點到i的路徑長

if(graph[top.index][i] != no_edge &&

(top.weight + graph[top.index][i]) < path[i].weight){

min_heap.push(node_info(i,top.weight + graph[top.index][i]));

path[i].front_index = top.index;

path[i].weight = top.weight + graph[top.index][i];

}

}

if(min_heap.empty()){

break;

}

}

shortest_path = path[end_node].weight;

intindex = end_node;

s_path_index.push_back(index);

while(true){

index = path[index].front_index;

s_path_index.push_back(index);

if(index == 0){

break;

}

}

}

private:

vector >graph;// 圖的數(shù)組表示

intnode_count;// 結(jié)點個數(shù)

constintno_edge;// 無通路

constintend_node;// 目的結(jié)點

vectors_path_index;// 最短路徑

intshortest_path;// 最短路徑

};

intmain()

{

constintsize = 11;

vector > graph(size);

for(inti = 0;i < size; ++ i){

graph[i].resize(size);

}

for(inti = 0;i < size; ++ i){

for(intj = 0;j < size; ++ j){

graph[i][j] = -1;

}

}

graph[0][1] = 2;

graph[0][2] = 3;

graph[0][3] = 4;

graph[1][2] = 3;

graph[1][5] = 2;

graph[1][4] = 7;

graph[2][5] = 9;

graph[2][6] = 2;

graph[3][6] = 2;

graph[4][7] = 3;

graph[4][8] = 3;

graph[5][6] = 1;

graph[5][8] = 3;

graph[6][9] = 1;

graph[6][8] = 5;

graph[7][10] = 3;

graph[8][10] = 2;

graph[9][8] = 2;

graph[9][10] = 2;

ss_shortest_paths ssp(graph,10);

ssp.shortest_paths();

ssp.print_spaths();

return0;

}

測試數(shù)據(jù)（圖）

測試結(jié)果