目錄
- 基本思想
- 分支界限法的要素 —— 限界函數(shù)/界限函數(shù)
- 分支界限法的要素 —— 活結(jié)點表
- 適用情況
- 基本步驟
- 程序設計
- 一般的算法設計模式
- 子集樹與排列樹
- 經(jīng)典運用
廣(寬)度優(yōu)先搜索 + 剪枝悄但。分支限界法的求解目標則是找出滿足約束條件的一個解沃饶，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解母廷。
# 基本思想：
與回溯法的異同：
相同點：與回溯法一樣，分支限界也是搜索一個解空間糊肤，而這個解空間通常組織成一棵樹(常見的樹結(jié)構：子集樹和排列樹)琴昆。
解題步驟都基本一樣的：定義解空間、確定解空間結(jié)構馆揉、深度/廣度優(yōu)先搜索 + 剪枝-
不同點：
- 搜索策略：回溯以深度優(yōu)先搜索樹业舍，而分支限界常常以廣度優(yōu)先或最小耗費(最大效益)優(yōu)先的方法搜索問題的解空間樹。
- 求解目標：回溯法的求解目標一般是找出解空間樹中滿足約束條件的所有解升酣。分支限界法的求解目標則是找出滿足約束條件的一個解舷暮，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。
充分利用限界函數(shù)和約束函數(shù)來剪去無效的枝并把搜索集中在可以得到解的分支上噩茄。
## 分支界限法的要素 —— 限界函數(shù)/界限函數(shù)
- 設立限界函數(shù)下面，其函數(shù)值是以該結(jié)點為根的搜索樹中的所有可行解的目標函數(shù)值的上/下界。
- 記錄已得的最優(yōu)可行解巢墅，其值是當時已經(jīng)得到的可行解的目標函數(shù)的最大/小值(初始值可以置為∞或用某種啟發(fā)式方法得到)诸狭。
- 搜索中停止分支的依據(jù)：如果某個結(jié)點不滿足約束條件或者其限界函數(shù)的得出的上/下界小/大于當時的最優(yōu)可行解券膀，則不再分支，向上回溯到父結(jié)點驯遇。
- 最優(yōu)可行解的更新：如果目標函數(shù)值為正數(shù)芹彬，初值可以設為0。在搜索中如得到一個可行解叉庐，計算可行解的目標函數(shù)值舒帮，如果這個值大于當時記錄的最優(yōu)可行解，就將這個值記錄作為新的解陡叠。
- 目標函數(shù)是求最大值:
設計上界限界函數(shù)ub玩郊，若是
的雙親結(jié)點，應滿足ub(
找到一個可行解ub()后枉阵，將所有小于ub(
- 目標函數(shù)是求最小值:
設計下界限界函數(shù)lb，若
當找到一個可行解lb(
## 分支界限法的要素 —— 活結(jié)點表
不同于回溯法，在分支限界法中拙徽，每一個活結(jié)點只有一次機會成為擴展結(jié)點刨沦。活結(jié)點一旦成為擴展結(jié)點膘怕，就一次性產(chǎn)生其所有兒子結(jié)點想诅。在這些兒子結(jié)點中，通過剪枝函數(shù)將導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點舍棄岛心，其余兒子結(jié)點被加入活結(jié)點表中来破。
此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點鹉梨，并重復上述結(jié)點擴展過程讳癌。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。
不同的活結(jié)點表形成不同的分枝限界法存皂，分為：FIFO分支限界法、LIFO分支限界法和LC(least cost)分支限界法逢艘。三種不同的活結(jié)點表旦袋，規(guī)定了從活結(jié)點表中選取下一個E-結(jié)點的不同次序。
-
FIFO分支限界法的活結(jié)點表是隊列它改，按照隊列先進先出（FIFO）原則選取下一個節(jié)點為擴展節(jié)點疤孕。 -
LIFO分支限界法的活結(jié)點表是堆棧，按照堆棧先進后出（LIFO）原則選取下一個節(jié)點為擴展節(jié)點央拖。 -
LC分支限界法的活結(jié)點表是優(yōu)先權隊列祭阀，按照優(yōu)先隊列中規(guī)定的優(yōu)先權選取具有最高優(yōu)先級的活結(jié)點成為新的E-結(jié)點鹉戚。- 最大優(yōu)先隊列（最大堆）：體現(xiàn)最大效益優(yōu)先
- 最小優(yōu)先隊列（最小堆）：體現(xiàn)最小費用優(yōu)先
在LIFO和FIFO分支限界法中专控，對下一個E-結(jié)點的選擇規(guī)則死板抹凳，在某種意義上是盲目的搜索伦腐。
LC分支限界法在選擇活結(jié)點時根據(jù)活結(jié)點的優(yōu)先權來選擇下一代活結(jié)點赢底。結(jié)點優(yōu)先權定義為：“在其分支下搜索一個答案狀態(tài)需要花費的代價柏蘑，代價越小幸冻，越優(yōu)先”
分枝限界法的特性：
- 時間性能：最壞的情況要搜索整個解空間，是復雜度是指數(shù)型咳焚。但如果啟發(fā)式信息強且剪枝處理得當洽损，平均性能往往很好革半。
- 空間性能：優(yōu)先隊列往往需要較大的空間開銷碑定。
# 基本步驟：
- 針對所給問題督惰，定義問題的解空間
- 對解空間進行組織不傅，確定易于搜索的解空間結(jié)構(樹或圖)
- 設計合適的限界函數(shù)
- 選定節(jié)點擴展策略，組織活結(jié)點表赏胚，使用限界函數(shù)來避免那些不能得到解的子空間访娶。
## 存在性問題/最優(yōu)化問題中的代價函數(shù)和限界函數(shù)
### 存在性問題的分支限界法 —— 代價函數(shù)
-
代價的函數(shù)：表示從根結(jié)點搜索到X，以及在X之下搜索到一個答案狀態(tài)所需的代價觉阅。
- 若
是答案結(jié)點崖疤，則
是從根結(jié)點到
- 若
割笙；
- 若
- 若
代價函數(shù)如同一個“有智力的”排序函數(shù)，基于其值選取下一個E-結(jié)點往往可以加快到達一答案結(jié)點的速度乱顾。
-
相對代價的函數(shù)：衡量子樹X下搜索到一個答案狀態(tài)所需的代價。
對任意結(jié)點
- ① 在生成一個答案結(jié)點之前券时，子樹
- ② 在子樹
- ① 在生成一個答案結(jié)點之前券时，子樹
代價是答案結(jié)點到根節(jié)點的搜索代價震檩，相對代價是子樹下的答案結(jié)點到子樹根X的搜索代價
由定義知，直接求c(.)和g(.)是十分困難
相對代價的估計函數(shù)：用于估計在
滿足如下特性：如果
是
沸毁。
-
代價的估計函數(shù)
是代價估計函數(shù)，它由兩部分組成：從根到
和從
。
一般而言：-
-
-
LC檢索(即最小成本檢索)：總是選取 值最小的活結(jié)點為下一個E結(jié)點搂誉。
- 若令
時， LC檢索退化為DFS搜索
- 若令
時炭懊，LC檢索退化為BFS搜索
### 求最優(yōu)解時的分支限界法 —— 代價函數(shù)、界函數(shù)
重新界定結(jié)點代價的含義：
選擇與目標函數(shù)有關的度量值
- 若
- 若
或
；
- 若
不直接求c(X)
限界函數(shù)：上界函數(shù) )
和下界函數(shù) )
分別是代價函數(shù) 的上界和下界函數(shù)
- 對任一結(jié)點X，總有
- 限界函數(shù)的意義對最優(yōu)解狀態(tài)的目標函數(shù)值的范圍進行界定荒椭，實現(xiàn)剪枝舰蟆。
## 回溯法和分支限界法的區(qū)別
| 對解空間樹的搜索方式 | 存儲結(jié)點的常用數(shù)據(jù)結(jié)構 | 結(jié)點存儲特性 | 求解目標 | |
|---|---|---|---|---|
| 回溯法 | 深度優(yōu)先搜索 | 遞歸趣惠；非遞歸時使用堆棧 | 活結(jié)點的所有可行子結(jié)點被遍歷后才被從棧中彈出（結(jié)點可能多次成為擴展結(jié)點） | 找出解空間樹中滿足約束條件的所有解 |
| 分支限界法 | 廣度優(yōu)先或最小消耗優(yōu)先搜索 | 三種：隊列、堆棧味悄、優(yōu)先隊列 | 每個活結(jié)點只有一次成為擴展結(jié)點的機會 | 找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解侍瑟。 |
# 程序設計
## 一般的算法設計模式如下：
存在性問題-分枝限界法算法框架（C++）
//樹結(jié)點的數(shù)據(jù)結(jié)構
//狀態(tài)空間樹采用樹的雙親表示法唐片，parent是指向其雙親的指針
template <class T>
struct Node{
T cost;
Node* parent;
};
/* 活結(jié)點表的類型記為LiveList ：FIFO/LIFO/優(yōu)選權隊列 */
template<class T> void BranchBound(Node<T>* t) // t是指向空間樹的根結(jié)點
{
LiveList<Node<T>* > lst(mSize); //lst為活結(jié)點表涨颜，元素指向樹結(jié)點
Node<T> *x,*E=t; //E為指向擴展結(jié)點的指針，初始指向t
do { //以下描述中不區(qū)分指針與其所指示的結(jié)點
for( 對結(jié)點E的每個不受限的孩子){
x=new Node; x->parent=E; //構造E的孩子結(jié)點x
if ( x是一個答案結(jié)點 ){
輸出從x到t的一條路徑庭瑰；
return; //輸出第一個解后算法終止
}
lst.Append(x); //孩子結(jié)點x進活結(jié)點表
}
if(lst.IsEmpty()){
cout << “沒有答案結(jié)點”；
return弹灭； //搜索失敗終止
}
lst.Serve(E); //從表中輸出一個活結(jié)點為E-結(jié)點
}while（1）督暂；
}
最優(yōu)解問題-分枝限界法算法框架（基于剪枝的FIFO穷吮、LC分枝限界求最小值 C++）
/*
* 提示：目標函數(shù)cost(X)逻翁、代價函數(shù)c(X)捡鱼、上界函數(shù)u(.)和下界函數(shù)?(.)
* U的值可以按下列原則修正：
如果X是答案結(jié)點八回，cost(X)是X所代表的可行解的目標函數(shù)值堰汉，u(X)是該子樹上最小代價答案結(jié)點代價的上界值辽社，則U=min{cost(X), u(X)+ε, U}翘鸭；
如果X代表部分向量滴铅，則U=min{u(X)+ε, U}就乓。
* 使用?(X)≥U 剪除多余分枝汉匙。
*/
template<class T>
Node<T>* LCBB(Node<T>* t, T& U) //t為根生蚁，U為上界變量
{
LiveList<Node<T>* > lst(mSize); //lst為優(yōu)先權隊列
Node<T> *ans=NULL, *x, E=*t;
do {
for( 對結(jié)點E的每個孩子){ //所有滿足約束條件的孩子
x=new Node; x->parent=E; //構造E的孩子結(jié)點x
if ( ?(x)<U){ //若x子樹未被限界函數(shù)剪枝
lst.Append(x);
//以下修正U
if ( x是答案結(jié)點 && cost(x)<U )
if ( u(x)+ε < cost(x) ) U = u(x)+ε;
else { U = cost(x); ans=x;}
else if(u(x)+ε<U) U=u(x)+ε;
}
}
//---------如果是FIFO分支限界法----------
do{
if(lst.IsEmpty()) return ans;
lst.Serve(E);
} while (?(E)≥U );
//---------如果是FIFO分支限界法----------
//---------如果是LC分支限界法----------
if(!lst.IsEmpty()){
lst.Serve(E); //從隊列中取擴展結(jié)點E
if (?(E)≥U) return ans; //若^c(E)≥U，則算法結(jié)束
}
else return ans; //若隊列為空邦投，則算法結(jié)束
//---------如果是LC分支限界法----------
}while（1）伤锚；
}
# 經(jīng)典運用：
- 單源最短路徑問題
- 裝載問題
- 布線問題
- 0-1背包問題
- 最大團問題
- TSP問題(旅行售貨員問題志衣、貨郎擔問題猛们、郵路問題)
- 電路板排列問題
- 批處理作業(yè)調(diào)度問題
舉例：優(yōu)先隊列式分支限界法解 —— 裝載問題
- 解裝載問題的優(yōu)先隊列式分支限界法用最大優(yōu)先隊列存儲活結(jié)點表∧螅活結(jié)點x在優(yōu)先隊列中的優(yōu)先級定義為從根結(jié)點到結(jié)點x的路徑所相應的載重量再加上剩余集裝箱的重量之和。
- 優(yōu)先隊列中優(yōu)先級最大的活結(jié)點成為下一個擴展結(jié)點吉懊。以結(jié)點x為根的子樹中所有結(jié)點相應的路徑的載重量不超過它的優(yōu)先級。子集樹中葉結(jié)點所相應的載重量與其優(yōu)先級相同借嗽。
- 在優(yōu)先隊列式分支限界法中，一旦有一個葉結(jié)點成為當前擴展結(jié)點淹魄，則可以斷言該葉結(jié)點所相應的解即為最優(yōu)解郁惜。此時可終止算法。
