-
分支限界搜索
鎖定
分支限界法是以廣度優先或以最小耗費 (最大效益) 優先的方式在問題的解空間樹T上搜索問題解的一種搜索方法。其求解目標是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出某種意義下的最優解。
分支限界法在人工智能組合問題求解中佔據了很重要的地位,，有效地解決了揹包問題、旅行商問題等經典問題。
[1]
- 中文名
- 分支限界搜索
- 外文名
- branch and boundsearch
- 求解目標
- 最優解
- 性 質
- 搜索算法
- 領 域
- 人工智能
- 學 科
- 計算機
目錄
分支限界搜索定義
“分支”是採用廣度優先的策略，依次生成擴展結點的所有分支（兒子結點）
分支限界搜索搜索策略
在當前節點（擴展節點）處，首先，生成當前節點的所有的兒子節點（分支），然後，從當前的活節點（當前節點的子節點）表中選擇下一個擴展節點。
為了有效地選擇下一個擴展節點，加速搜索的進程，在每一個活節點處，計算一個函數值（限界），根據函數值的大小，從當前活節點表中選擇一個最有利的節點作為擴展節點，使搜索朝着解空間上有最優解的分支推進，以便儘快地找出一個最優解。
[1]
分支限界搜索分類
分支限界搜索隊列式(FIFO)分支限界法
按照隊列先進先出(FIFO)原則選取下一個活結點為擴展結點。
起初，根結點是唯一的活結點，根結點入隊。從活結點隊中取出根結點後，作為當前擴展結點。對當前擴展結點，先從左到右地產生它的所有兒子，用約束條件檢查，把所有滿足約束函數的兒子加入活結點隊列中。再從活結點表中取出隊首結點（隊中最先進來的結點）為當前擴展結點，……，直到找到一個解或活結點隊列為空為止。
[2]
分支限界搜索優先隊列式(LC)分支限界法
按照優先隊列中規定的優先級選取優先級最高的結點成為當前擴展結點。
對每一活結點計算一個優先級（某些信息的函數值）。根據這些優先級，從當前活結點表中優先選擇一個優先級最高（最有利）的結點作為擴展結點，再從活結點表中下一個優先級別最高的結點為當前擴展結點，......，直到找到一個解或活結點隊列為空為止。
[2]
分支限界搜索與回溯法
分支限界搜索相同點
分支限界搜索不同點
回溯法：以深度優先的方式搜索解空間，其求解目標是找出解空間中滿足約束條件的所有解
分支限界搜索應用舉例
已知：有一批共
個集裝箱要裝上2艘載重量分別為
，
的輪船，其中集裝箱i的重量為
。問題：是否有一個合理的裝載方案可將這
個集裝箱裝上這2艘輪船？
解：
可證明，採用如下策略可以得到一個最優裝載方案：先儘可能的將第一艘船裝滿，其次將剩餘的集裝箱裝到第二艘船上。
//分支限界法解裝載問題
//裝載問題先儘量將第一艘船裝滿
//隊列式分支限界法，返回最優載重量
template<class Type>
Type MaxLoading(Type w[],Type c,int n)
{
//初始化數據
Queue<Type> Q; //保存活節點的隊列10
Q.Add(-1); //-1的標誌是標識分層11
int i=1; //i表示當前擴展節點所在的層數
Type Ew=0; //Ew表示當前擴展節點的重量
Type bestw=0; //bestw表示當前最優載重量
//搜索子集空間樹
while(true)
{
//檢查左兒子
Type wt=Ew+w[i]; //wt為左兒子節點的重量
if(wt<=c) //若裝載之後不超過船體可承受範圍
if(wt>bestw) //更新最優裝載重量
{
bestw=wt;24
if(i<n) Q.Add(wt); //將左兒子添加到隊列
}
//將右兒子添加到隊列
if(Ew+r>bestw&&i<n)
Q.Add(Ew);
Q.Delete(Ew); //取下一個節點為擴展節點並將重量保存在Ew
if(Ew==-1) //檢查是否到了同層結束
{
if(Q.IsEmpty())
return bestw; //遍歷完畢，返回最優值
Q.Add(-1); //添加分層標誌
Q.Delete(Ew); //刪除分層標誌，進入下一層
i++;
r-=w[i]; //剩餘集裝箱重量
}
}
}
- 參考資料
-
- 1. 邢穎, 宮雲戰, 王雅文,等. 基於分支限界搜索框架的測試用例自動生成[J]. 中國科學:信息科學, 2014, 44(10):1345-1360.
- 2. 0033算法筆記——【分支限界法】分支限界法與單源最短路徑問題 ．CSDN博客．2013-05-08[引用日期2017-05-07]
- 3. 算法——分支限界法 ．博客園[引用日期2017-05-07]
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：6次歷史版本
- 最近更新： 仇冬琴