分支限界法與回溯法

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

分支限界法的基本思想

分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中。 此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所需的解或活結點表為空時為止。

常見的兩種分支限界法

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

一、單源最短路徑問題

1、問題描述

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

下圖是用優先隊列式分支限界法解有向圖G的單源最短路徑問題產生的解空間樹。其中，每一個結點旁邊的數字表示該結點所對應的當前路長。

找到一條路徑：

目前的最短路徑是8，一旦發現某個結點的下界不小于這個最短路進，則剪枝：

同一個結點選擇最短的到達路徑：

2.剪枝策略

在算法擴展結點的過程中，一旦發現一個結點的下界不小于當前找到的最短路長，則算法剪去以該結點為根的子樹。

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

3.算法思想

解單源最短路徑問題的優先隊列式分支限界法用一極小堆來存儲活結點表。其優先級是結點所對應的當前路長。

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

實現

* 作者：chinazhangjie

* 郵箱：chinajiezhang@gmail.com

* 開發語言：C++

* 開發環境：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;// 為了實現從小到大的順序

}

public:

intindex;// 結點位置

intweight;// 權值

};

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));// 將起始結點入隊

while(true){

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

min_heap.pop();

// 已到達目的結點

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;// 圖的數組表示

intnode_count;// 結點個數

constintno_edge;// 無通路

constintend_node;// 目的結點

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;

}

測試數據（圖）

測試結果