基本介紹
- 中文名：分枝限界法
- 外文名：branch and bound method
- 領域：運籌學
- 別稱：分枝定界法
- 屬性：一種求解離散最最佳化問題的方法
- 相關名詞：分支界限法
定義,基本思想,節點的選擇,步驟,算法分析,優點,缺點,
定義
分枝限界法是由三棲學者查理德·卡普（Richard M.Karp）在20世紀60年代發明，成功求解含有65個城市的旅行商問題，創當時的記錄。“分枝界限法”把問題的可行解展開如樹的分枝，再經由各個分枝中尋找最佳解。
分枝限界法也能夠使用在混合整數規劃問題上，其為一種系統化的解法，以一般線性規劃之單形法解得最佳解後，將非整數值之決策變數分割成為最接近的兩個整數，分列條件，加入原問題中，形成兩個子問題(或分枝)分別求解，如此便可求得目標函式值的上限（上界）或下限（下界），從其中尋得最佳解。
基本思想
在每次分支後，對凡是界限超出已知可行解值那些子集不再做進一步分支。這樣，解的許多子集（即搜尋樹上的許多結點）就可以不予考慮了，從而縮小了搜尋範圍。這一過程一直進行到找出可行解為止，該可行解的值不大於任何子集的界限。因此這種算法一般可以求得最優解。
將問題分枝為子問題並對這些子問題定界的步驟稱為分枝限界法。
節點的選擇
對搜尋樹上的某些點必須作出分枝決策，即凡是界限小於迄今為止所有可行解最小下界的任何子集（節點），都有可能作為分枝的選擇對象（對求最小值問題而言）。怎樣選擇搜尋樹上的節點作為下次分枝的節點呢？有兩個原則：
1）從最小下界分枝（優先佇列式分枝限界法）：每次算完界限後，把搜尋樹上當前所有葉節點的界限進行比較。找出限界最小的節點，此結點即為下次分枝的結點。
·優點：檢查子問題較少，能較快地求得最佳解；
·缺點：要存儲很多葉節點的界限及對應的耗費矩陣，花費很多記憶體空間。
2）從最新產生的最小下界分枝（佇列式（FIFO）分枝限界法）：從最新產生的各子集中按順序選擇各結點進行分枝，對於下屆比上屆還大的節點不進行分枝。
優點：節省了空間；缺點：需要較多的分枝運算，耗費的時間較多。
這兩個原則更進一步說明了，在算法設計中的時空轉換概念。
步驟
分枝限界法是組合最佳化問題的有效求解方法，其步驟如下所述：
步驟一：如果問題的目標為最小化，則設定目前最優解的值
。
步驟二：根據分枝法則（Branching rule），從尚未被洞悉（Fathomed）節點（局部解）中選擇一個節點，並在此節點的下一階層中分為幾個新的節點。
步驟三：計算每一個新分枝出來的節點的下限值（Lower bound，LB）
步驟四：對每一節點進行洞悉條件測試，若節點滿足以下任意一個條件，則此節點可洞悉而不再被考慮：
（1）此節點的下限值大於等於Z值。
（2）已找到在此節點中，具最小下限值的可行解；若此條件成立，則需比較此可行解與Z值，若前者較小，則需更新Z值，燕以此為可行解的值。
（3）此節點不可能包含可行解。
步驟五：判斷是否仍有尚未被洞悉的節點，如果有，則進行步驟二，如果已無尚未被洞悉的節點，則演算停止，並得到最優解。
Kolen等曾利用此方法求解含時間窗約束的車輛巡迴問題，其實驗的節點數範圍為6-15。當節點數為6時，計算機演算所花費的時間大約1分鐘（計算機型為VAZ11/785），當節點數擴大至12時，計算機有記憶體不足的現象產生，所以分枝定界法比較適用於求解小型問題。Held和Karp指出分枝定界法的求解效率，與其界限設定的寬緊有極大的關係。
算法分析
優點
可以求得最優解、平均速度快。
因為從最小下界分支，每次算完限界後，把搜尋樹上當前所有的葉子結點的限界進行比較，找出限界最小的結點，此結點即為下次分支的結點。這種決策的優點是檢查子問題較少，能較快的求得最佳解。
缺點
要存儲很多葉子結點的限界和對應的耗費矩陣。花費很多記憶體空間。
