分支定界法總結

                         分支定界法總結

分支定界法介紹：

         分支限界法是一個用途十分廣泛的算法，運用這種算法的技巧性很強，不同類型的問題解法也各不相同。分支限界法的基本思想是對有限制條件的最優化問題的所有可行解（數目有限）空間進行搜尋。該算法在具體執行時，把全部可行的解空間不斷分割為越來越小的子集（稱為分支），并為每個子集内的解的值計算一個下界或上界（稱為限界）。在每次分支後，對凡是界限超出已知可行解值那些子集不再做進一步分支。這樣，解的許多子集（即搜尋樹上的許多結點）就可以不予考慮，進而縮小了搜尋範圍。這一過程一直進行到找出可行解為止，該可行解的值不大于任何子集的界限。這種算法一般可以求得最優解。

1.基本理論：

       1.1 分支限界算法政策

              在分支限界法中，每一個活結點隻有一次機會成為擴充結點。活結點一旦成為擴充結點，就一次性産生其所      有 兒子結點。在這些兒子結點中，導緻不可行解或導緻非最優解的兒子結點被舍棄，其餘兒子結點被加入活結點        中。從活結點表中取下一結點成為目前擴充結點，并重複上述結點擴充過程。這個過程一直持續到找到所需的解或      活結點表為空時為止。

        1.2 從活結點表中選擇下一個活結點作為新的擴充結點，分支限界算法通常可以分為兩種形式：

1.2.1 FIFO（First In First Out）分支限界算法

        按照先進先出（FIFO）原則選擇下一個活結點作為擴充結點，即從活結點表中取出結點的順序與加入結點的順序相同。

1.2.2 最小耗費或最大收益分支限界算法

在這種情況下，每個結點都有一個耗費或收益。

根據問題的需要，可能是要查找一個具有最小耗費的解，或者是查找一個具有最大收益的解。

        1.3 提高分支定界法的效率

               實作分支限界算法時，首先确定目标值的上下界，邊搜尋邊減掉搜尋樹的某些分支，提高搜尋效率。

     在搜尋時，絕大部分需要用到剪枝。“剪枝”是搜尋算法中優化程式的一種基本方法，需要通過設計出合理的判斷         方 法，以決定某一分支的取舍。

              若我們把搜尋的過程看成是對一棵樹的周遊，那麼剪枝就是将樹中的一些“死結點”，不能到達最優解的枝           條“剪”掉，以減少搜尋的時間。 

2.下面通過例題來具體的說明一下分支定界法的具體過程

       2.1 單源最短路徑的問題

            給定帶權有向圖G＝(V，E)，其中每條邊的權是非負實數。 給定V中的一個頂點，稱為源。現在要計算從源        到所有其他各頂點的最短路長度，這裡路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。（每      條邊上标注有字母和數字，在字母旁邊的數字為路長。）

     輸入

第一行是頂點個數n，第二行是邊數edge；接下來edge行是邊的描述：from，to，d，表示從頂點from到頂點 to的邊權是d。後面是若幹查詢，從頂點s到頂點t。

輸出

給出所有查詢，從頂點s到頂點t的最短距離。

如果從頂點s不可達到頂點t，則輸出“No path!”。

輸出樣例：       

解題思路：

   解單源最短路徑問題的優先隊列式分支限界法，使用C++标準模闆庫的優先隊列存儲活結點表，其優先級是結點所對應的目前路長。

算法從圖G的源頂點s和空優先隊列開始。結點s被擴充後，它的兒子結點a，b，c被依次插入優先隊列中。

算法從優先隊列中取出具有最小目前路長的結點作為目前擴充結點，并依次檢查與目前擴充結點相鄰的所有頂點。

如果從目前擴充結點i到頂點j有邊可達，且從源出發，途經頂點i再到頂點j相應的路徑的長度小于目前最優路徑長度，則将該頂點作為活結點插入到活結點優先隊列中。

這個結點的擴充過程一直繼續到活結點優先隊列為空。

            單源最短路徑問題分支限界算法的資料結構

        #define inf 1000000 //∞

#define NUM 100

int n; //圖G的頂點數

int edge; //圖G的邊數

int c[NUM][NUM]; //圖G的鄰接矩陣

int prev[NUM]; //前驅頂點數組

int dist[NUM]; //從源頂點到各個頂點最短距離數組     

       //優先隊列的元素

struct MinHeapNode {

　　//排序算法，升序

　　friend bool operator < (const MinHeapNode& a,

　　　　　　　　　　　　　　const MinHeapNode& b)

　 　{

　　　　if(a.length > b.length)　　return true;

　　　　else return false;

　 　}

　 　int i;　　　　　　　　　//結點編号

　 　int length;　　　　　　//結點路徑的長度

};

   ZOJ1136-Multiple

給出一個自然數N（0～4999，包括0和4999）和M個不同的十進制數字X1，X2，…，XM（至少一個數）。

找出由數字X1，X2，…，XM構成的正整數，是N的最小倍數。

每組資料之間有一個空行，資料格式如下：

第一行：數字N

第二行：數字M

接下來M行：數字X1，X2，…，XM。

對每組測試資料，假如存在此數，則直接輸出該數，占一行；否則輸出0。

由數字X1, X2, …, XM構成的正整數，而且這些數字是可以重複使用的，屬于可重複的全排列問題。

樣例資料1：X1＝7，X2＝0，X3＝1，構成正整數110是22的倍數，而且是22的最小倍數。其中X3使用了2次，X2使用了1次。

假設構成的數字有num位，則問題解空間是：mnum。

雖然沒有給定m和num的大小，顯然這兩個數不會太大，且N的最小倍數是正整數，結合線上測試得知，m和num不超過11。

本題隻要一個最優解，最适合的方法是分支限界算法，使用廣度優先搜尋（BFS）來實作

資料結構

設要計算的數字是n，用于構造的數字個數是m。

使用數組存放用于構造的數字（即m個正整數）：

int a[20];

隊列結點資料結構：

struct node { 

int num; //該結點構造的數字除以n的餘數

string digit; //該結點構造的數字

};

隊列的定義：

queue <node> q;

輔助數組r，表示下标為x的值是否在隊列中：

bool r[5000] = {false};

在隊列式分支限界算法中，不斷從活結點隊列中取出目前擴充結點cur，并産生目前結點cur的所有兒子結點。在擴充結點時，先将數字a[i]（即Xi）擴充到目前結點餘 數的尾部：

如果x＝0， 0%n是無效的，該子結點不放進隊列。如果x%n還沒有計算過，将該子結點放入隊列中，否則其計算結果儲存在r[x%n]中。

對目前結點E，如果r[0]=true，表示找到了n的倍數，直接輸出E.digit。

      //定義隊列

queue <node> q;

//構造隊列的頭元素

node cur;

cur.num = 0;

cur.digit = "";

q.push(cur);

//定義輔助數組

bool r[5000] = {false};

//是否已經找到答案

bool find = false;

while ( !q.empty() )　 //搜尋問題的解空間

{

　　 cur = q.front();　 //取出隊列的頭元素

　　q.pop();

　　//産生目前擴充結點的兒子結點

　　for(int i = 0; i < m; i++)

　　{

　　　　int x = cur.num * 10 + a[i];

　　　　if (x == 0) continue;

　　　　node E; 　 //定義一個結點

　　　　if ( !r[x%n] ) 　 //如果x%n還沒有計算過

　　　　{

　　　　　　r[x%n] = true;

　　　　　　E.num = x%n;

　　 　　　　E.digit = cur.digit + char(a[i]+'0');

　　 　　 　　q.push(E);

　 　　　}

　　 　　if (r[0]) 　 //已經找到答案

　　 　　{

　　 　　　　cout << E.digit << endl; 

　　 　　　　find = true;　break;

　　　　}

　 　}

　 　if (find) break;

}

if ( !find ) cout<<0<<endl; //沒有找到答案

return;

實作N的最小倍數

為了確定找到的就是N的最小倍數，我們每次從數字X1，X2，…，XM中，首先取出最小的數字構造，然後是次小的等等，這樣第一個滿足條件的數字就是最小的倍數。通過對 這些數字按升序排序，就可以實作。

使用C++标準模闆庫函數，對一維數組可以直接升序排序：

sort(a, a+m);

3.總結

         分支限界法類似于回溯法，是一種在問題的解空間樹T上搜尋問題解的算法。

一般情況下，分支限界法與回溯法的求解目标不同。回溯法的求解目标是找出T中滿足限制條件的所有解，而分支限界法的求解目标則是找出滿足限制條件的一個解，或是在滿足限制條件的解中找出使某一目标函數值達到極大或極小的解，即在某種意義下的最優解。