複製鏈接
請複製以下鏈接發送給好友

分枝定界

鎖定
分枝界限法是由三棲學者查理德·卡普(Richard M.Karp)在20世紀60年代發明,成功求解含有65個城市旅行商問題,創當時的記錄。“分枝界限法”把問題的可行解展開如樹的分枝,再經由各個分枝中尋找最佳解。
中文名
分枝定界/分支定界
外文名
branch and bound
類    型
搜索解空間的方法
類似方法
回溯法

分枝定界簡介

分枝界限法也能夠使用在混合整數規劃問題上,其為一種系統化的解法,以一般線性規劃之單形法解得最佳解後,將非整數值之決策變量分割成為最接近的兩個整數,分列條件,加入原問題中,形成兩個子問題(或分枝)分別求解,如此便可求得目標函數值的上限(上界)或下限(下界),從其中尋得最佳解。 [1] 

分枝定界基本思想

分枝定界1、基本思想

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

分枝定界2、分枝節點的選擇

對搜索樹上的某些點必須作出分枝決策,即凡是界限小於迄今為止所有可行解最小下界的任何子集(節點),都有可能作為分枝的選擇對象(對求最小值問題而言)。怎樣選擇搜索樹上的節點作為下次分枝的節點呢?有兩個原則:
1)從最小下界分枝(隊列式FIFO分枝限界法):每次算完界限後,把搜索樹上當前所有葉節點的界限進行比較。找出限界最小的節點,此結點即為下次分枝的結點。
  • 優點:檢查子問題較少,能較快地求得最佳解;
  • 缺點:要存儲很多葉節點的界限及對應的耗費矩陣,花費很多內存空間。
2)從最新產生的最小下界分枝(優先隊列式分枝限界法):從最新產生的各子集中選擇具有最小的下界的結點進行分枝。
優點:節省了空間; 缺點:需要較多的分枝運算,耗費的時間較多。這兩個原則更進一步説明了,在算法設計中的時空轉換概念。分枝定界法已經成功地應用於求解整數規劃問題、生產進度表問題、貨郎擔問題、選址問題、揹包問題以及可行解的數目為有限的許多其它問題。對於不同的問題,分枝與界限的步驟和內容可能不同,但基本原理是一樣的。 [1] 

分枝定界步驟

分枝界限法是組合優化問題的有效求解方法,其步驟如下所述:
步驟一:如果問題的目標為最小化,則設定目前最優解的值Z=∞。
步驟二:根據分枝法則(Branching rule),從尚未被洞悉(Fathomed)節點(局部解)中選擇一個節點,並在此節點的下一階層中分為幾個新的節點。
步驟三:計算每一個新分枝出來的節點的下限值(Lower bound,LB)。
步驟四:對每一節點進行洞悉條件測試,若節點滿足以下任意一個條件,則此節點可洞悉而不再被考慮:
  • 此節點的下限值大於等於Z值。
  • 已找到在此節點中,具最小下限值的可行解;若此條件成立,則需比較此可行解與Z值,若前者較小,則需更新Z值,以此為可行解的值。
  • 此節點不可能包含可行解。
步驟五:判斷是否仍有尚未被洞悉的節點,如果有,則進行步驟二,如果已無尚未被洞悉的節點,則演算停止,並得到最優解。
Kolen等曾利用此方法求解含時間窗約束的車輛巡迴問題,其實驗的節點數範圍為6-15。當節點數為6時,計算機演算所花費的時間大約1分鐘(計算機型為VAZ11/785),當節點數擴大至12時,計算機有內存不足的現象產生,所以分枝定界法比較適用於求解小型問題。Held和Karp指出分枝定界法的求解效率,與其界限設定的寬緊有極大的關係。 [1] 
參考資料
  • 1.    汪祖柱, 程家興. 求解組合優化問題的一種方法-分枝定界法[J]. 安徽大學學報(自科版), 2004, 28(1):10-14.