基本介紹
- 中文名：分支限界搜尋
- 外文名：branch and bound search
- 求解目標：最優解
- 性質：搜尋算法
- 領域：人工智慧
- 學科：計算機
定義,搜尋策略,分類,佇列式(FIFO)分支限界法,優先佇列式(LC)分支限界法,與回溯法,相同點,不同點,套用舉例,
定義
“分支”是採用廣度優先的策略，依次生成擴展結點的所有分支（兒子結點）
“限界”是在結點擴展過程中，計算結點的上界（或下界），邊搜尋邊減掉搜尋樹的某些分支，從而提高搜尋效率。
搜尋策略
在當前節點（擴展節點）處，首先，生成當前節點的所有的兒子節點（分支），然後，從當前的活節點（當前節點的子節點）表中選擇下一個擴展節點。
為了有效地選擇下一個擴展節點，加速搜尋的進程，在每一個活節點處，計算一個函式值（限界），根據函式值的大小，從當前活節點表中選擇一個最有利的節點作為擴展節點，使搜尋朝著解空間上有最優解的分支推進，以便儘快地找出一個最優解。
分類
從活結點表中選擇下一擴展結點的不同方式導致了不同的分支限界法， 最常見的有佇列式分支限界法和優先佇列式分支限界法兩種。
佇列式(FIFO)分支限界法
按照佇列先進先出(FIFO)原則選取下一個活結點為擴展結點。
起初，根結點是唯一的活結點，根結點入隊。從活結點隊中取出根結點後，作為當前擴展結點。對當前擴展結點，先從左到右地產生它的所有兒子，用約束條件檢查，把所有滿足約束函式的兒子加入活結點佇列中。再從活結點表中取出隊首結點（隊中最先進來的結點）為當前擴展結點，……，直到找到一個解或活結點佇列為空為止。
優先佇列式(LC)分支限界法
按照優先佇列中規定的優先權選取優先權最高的結點成為當前擴展結點。
對每一活結點計算一個優先權（某些信息的函式值）。根據這些優先權，從當前活結點表中優先選擇一個優先權最高（最有利）的結點作為擴展結點，再從活結點表中下一個優先權別最高的結點為當前擴展結點，......，直到找到一個解或活結點佇列為空為止。
與回溯法
相同點
都是一種在問題的解空間樹
上搜尋問題解的算法
不同點
回溯法：以深度優先的方式搜尋解空間，其求解目標是找出解空間中滿足約束條件的所有解
分支限界法：以廣度優先的方式或以最小耗費優先的方式搜尋解空間，其求解目標則是找出滿足約束條件的一個解，或是滿足約束條件的解中找出使某一目標函式值達到極大或極小的解，即在某種意義下的最優解。
套用舉例
已知：有一批共
個貨櫃要裝上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]; //剩餘貨櫃重量 } }}