分枝限界法概述

分枝限界法和回溯法一樣，也是一種在問題的解空間樹上搜可行解的窮舉算法。

其中“分枝”指的是“分枝限界法”搜索可行解采用的策略為廣度優(yōu)先搜索或?qū)崿F(xiàn)方法和思路類似的代價優(yōu)先搜索。

廣度優(yōu)先搜索的概念和實現(xiàn)前面已經(jīng)介紹過很多次了，這里不再做贅述；代價優(yōu)先搜索的目的是以某種定義下的優(yōu)先級，按照優(yōu)先級從高到低的順序處理所有的結(jié)點。

(從低到高和從高到低本質(zhì)上是一樣的，這里以從高到低為例)。

如果狀態(tài)結(jié)點能夠按照優(yōu)先級不嚴格(可以相等)降低的順序，在解空間樹上按照結(jié)點高度從高到低，同高度結(jié)點從左到右或從右到左的排列，那我們可以用廣度優(yōu)先搜索來達到代價優(yōu)先搜索的目的(廣度優(yōu)先搜索的搜索順序和代價優(yōu)先搜索的搜素順序相同)。

但是狀態(tài)空間樹上的狀態(tài)結(jié)點是通過決策聯(lián)系起來的，決策對于狀態(tài)優(yōu)先級相關(guān)的屬性的變化多樣(可能增大，可能減小，可能線性，可能非線性)，狀態(tài)結(jié)點按照優(yōu)先級從高到低的順序在狀態(tài)空間樹上的出現(xiàn)往往會是跳躍式的，與解空間樹的結(jié)構(gòu)無關(guān)。

如果策略能夠始終保持狀態(tài)結(jié)點到子節(jié)點優(yōu)先級相關(guān)的屬性遞增或遞減(即樹上的結(jié)點從屬性數(shù)值的角度來看符合堆的性質(zhì))，我們可以在代價優(yōu)先搜索中用堆數(shù)據(jù)結(jié)構(gòu)來存儲狀態(tài)空間中未處理過的結(jié)點，處理節(jié)點過程中根據(jù)可選策略擴展結(jié)點加入容器的方法和廣度優(yōu)先搜索相同。

根據(jù)堆數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，我們每次取堆頂(隊首)結(jié)點進行處理，即是剩余未處理結(jié)點中優(yōu)先級最高的結(jié)點(未加入容器的子孫節(jié)點，容器中一定存在一個結(jié)點的優(yōu)先級高于該子孫節(jié)點的優(yōu)先級，所以是未處理中結(jié)點中優(yōu)先級最高的結(jié)點)，這樣一直處理即是按照優(yōu)先級最高到低的順序處理所有的狀態(tài)節(jié)點。

(具體原因和用反證法證明，不做贅述)。

“限界”指的是限界函數(shù)，和回溯法中的限界函數(shù)一樣，在廣度(代價)優(yōu)先搜索將被擴展的結(jié)點加入到(優(yōu)先)隊列中時，刪除掉一些不必要的子節(jié)點，從而將選擇變得更有效以加速搜索的進程。

個人歸納認為：回溯法=(狀態(tài)空間樹上的)一般深度優(yōu)先搜索+限界函數(shù)，分枝限界法=(狀態(tài)空間樹上的)一般廣度(代價)優(yōu)先搜索+限界函數(shù)。

作為兩種在狀態(tài)空間書上搜索可行解的算法，我們一般考慮狀態(tài)空間樹的寬度和深度來選擇使用回溯法還是分枝限界法：存在根節(jié)點到部分葉子結(jié)點的路徑過長時，選擇分枝限界法避免進入某條過長路徑的搜索；如果可選擇的決策過多，即樹的寬度過大時，選擇回溯法來避免擴展狀態(tài)空間樹同一高度過多的狀態(tài)節(jié)點。

如果兩種情況同時存在，可以采取限定單次回溯法搜素最大深度的方法來避免回溯法搜素進入過深的分支，不斷擴大單次回溯法搜素的最大深度直到某次的回溯法尋找到可行解為止，這種策略稱為迭代加深。

如果狀態(tài)節(jié)點的屬性滿足代價優(yōu)先搜索的要求，即子節(jié)點的優(yōu)先級都高于父節(jié)點的優(yōu)先級，我們也可以用分枝限界法去尋找特定意義上的最優(yōu)解。

如果屬性值(優(yōu)先級)按照層次從上到下遞減且最優(yōu)解的“優(yōu)”指的就是按照層次從上到下遞減的優(yōu)先級，那么以代價優(yōu)先搜索為模板搜素到的第一個可行解即為我們的最優(yōu)解，在這種問題背景下不需要進行與當前最優(yōu)解比較判斷能否得到更優(yōu)解的剪枝函數(shù)。

確定可行解(最優(yōu)解)所進行的決策

即在圖(樹)的搜索問題中，求解根結(jié)點到當前結(jié)點的路徑，一般有兩種通用的策略：

第一種是對每個節(jié)點保存根節(jié)點到該節(jié)點的路徑，在擴展時通過根結(jié)點到父節(jié)點的路徑獲得根結(jié)點到子節(jié)點的路徑。

這種方法實現(xiàn)起來簡單，但是往往會浪費空間和時間。

第二種是在擴展子節(jié)點時對每個結(jié)點保存它在狀態(tài)空間上的前驅(qū)節(jié)點，即父節(jié)點，然后通過對父節(jié)點的回溯得到該節(jié)點到根節(jié)點的路徑，逆序即是根節(jié)點到該節(jié)點的路徑。

分枝限界法的時間性能

分枝限界法和回溯法本質(zhì)上都屬于窮舉法(廣度優(yōu)先搜索和深度優(yōu)先搜索)，在最壞情況下與窮舉法的復(fù)雜度相同(甚至更糟，因為需要進行限界值的計算和限界函數(shù)的判斷)，實際求解效率基本上由限界函數(shù)決定。

求解0/1背包問題

即前面介紹過很多遍的0/1背包問題。

重量小于規(guī)定重量的結(jié)點通過決策構(gòu)成解空間樹，由于0/1背包問題的決策保證子節(jié)點中的價值屬性一定大于等于父節(jié)點的價值屬性，結(jié)點的價值屬性用于確定結(jié)點的優(yōu)先級，我們可以通過優(yōu)先隊列式分枝限界法，即以代價優(yōu)先搜索為模板的分枝限界法求解0/1背包問題的最優(yōu)解。

代價預(yù)先搜索求解0/1背包問題，就是在解空間樹上以狀態(tài)節(jié)點的價值屬性作為優(yōu)先級高度的標準進行上的代價優(yōu)先搜索。

限界函數(shù)中的左孩子剪枝策略與回溯法中的左孩子剪枝策略一致；上一章節(jié)中提到0/1背包的右孩子剪枝相當于固定右子節(jié)點后續(xù)的策略向左，即將所有還沒有選擇的物品加入背包來得到一個價值的上界。

實際上這種價值上界的估計是比較粗糙的，因為剩余的物品我們往往無法全部加入到當前的背包中。這種上界估計的方式就相當于固定策略跳躍到右子樹最左邊的狀態(tài)節(jié)點，沒有進行真正的搜索，實際上這個擴展得到的“最左邊的狀態(tài)節(jié)點”可能并不滿足問題規(guī)范的條件，即不是一個滿足要求的可行解(實際不存在于解空間樹上)，上界被估計得過高了。

那如果我們是通過實際搜索，搜索到右子樹滿足問題條件的最左狀態(tài)節(jié)點呢？即課件上的原做法：

這種價值上界的估計方法在重量小價值高的物品出現(xiàn)在解空間樹下層的決策時會出現(xiàn)反例。解決的方案也很簡單，就是避免重量小價值高的物品出現(xiàn)在解空間樹的下層，或者說避免重量小價值高的物品在物品序列中出現(xiàn)在重量大價值小的物品之后，即對物品序列進行一個預(yù)處理：在進行分枝限界法之前，先按照“價值/重量”的值對物品序列進行從大到小的排序。

對應(yīng)的隊列式分枝限界法求解如下(只介紹一個框架，在能夠使用代價優(yōu)先搜索的情況下一般還是使用代價優(yōu)先搜索)：文章來源地址http://www.zghlxwxcb.cn/news/detail-486977.html

//隊列中的狀態(tài)結(jié)點類型
struct NodeType{
   	
	int no;//結(jié)點編號
	int i;//當前結(jié)點在搜索空間中的層次
	int w;//搜素到當前結(jié)點的總重量
	int v;//搜素到當前結(jié)點的總價值
	int x[MAXN];//搜素到當前狀態(tài)結(jié)點進行過的決策 
	double ub;//限界函數(shù)bound預(yù)估的價值上界
};
//計算狀態(tài)結(jié)點e的價值上界
//需要對物品價值/重量的值進行一個排序
void bound(NodeType &e){
   
	//固定后續(xù)的決策向左,搜索右子樹滿足問題條件的最左狀態(tài)節(jié)點
	int i=e.i+1;
	int sumw=e.w;
	double sumv=e.v;
	while ((sumw+w[i]<=W)&&i<=n){
   	
		sumw+=w[i];	sumv+=v[i];	i++;
	}
	//如果所有剩余的物品不能全部裝入背包,對于不能完全裝入背包的物品,采用分塊極限的方式估計價值上界 
	if (i<=n) e.ub=sumv+(W-sumw)*v[i]/w[i];
	//如果所有剩余的物品都能裝入背包 
	else e.ub=sumv;
}
//將結(jié)點加入容器并通過結(jié)點的層次判斷可行解,通過比較得到最優(yōu)解 
void EnQueue(NodeType e,queue<NodeType> &qu){
   
	//通過結(jié)點的層次判斷可行解
	if (e.i==n){
   
		if (e.v>maxv){
   
			//保存最優(yōu)解的信息 
			maxv=e.v;
			for (int j=1;j<=n;j++) bestx[j]=e.x[j];
		}
	}
	else qu.push(e);//非葉子結(jié)點進隊
}
//隊列式分枝限界法求0/1背包的最優(yōu)解
void bfs(<

到了這里，關(guān)于第六章——分枝限界法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！