[科普中國]-分枝限界法

簡介

分枝限界法是由三棲學(xué)者查理德·卡普（Richard M.Karp）在20世紀(jì)60年代發(fā)明，成功求解含有65個城市的旅行商問題，創(chuàng)當(dāng)時的記錄?！胺种缦薹ā卑褑栴}的可行解展開如樹的分枝，再經(jīng)由各個分枝中尋找最佳解。

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

分枝限界法的基本思想在每次分支后，對凡是界限超出已知可行解值那些子集不再做進(jìn)一步分支。這樣，解的許多子集（即搜索樹上的許多結(jié)點）就可以不予考慮了，從而縮小了搜索范圍。這一過程一直進(jìn)行到找出可行解為止，該可行解的值不大于任何子集的界限。因此這種算法一般可以求得最優(yōu)解。

將問題分枝為子問題并對這些子問題定界的步驟稱為分枝限界法。1

分枝節(jié)點的選擇對搜索樹上的某些點必須作出分枝決策，即凡是界限小于迄今為止所有可行解最小下界的任何子集（節(jié)點），都有可能作為分枝的選擇對象（對求最小值問題而言）。怎樣選擇搜索樹上的節(jié)點作為下次分枝的節(jié)點呢？有兩個原則：

1）從最小下界分枝（優(yōu)先隊列式分枝限界法）：每次算完界限后，把搜索樹上當(dāng)前所有葉節(jié)點的界限進(jìn)行比較。找出限界最小的節(jié)點，此結(jié)點即為下次分枝的結(jié)點。

·優(yōu)點：檢查子問題較少，能較快地求得最佳解；

·缺點：要存儲很多葉節(jié)點的界限及對應(yīng)的耗費矩陣，花費很多內(nèi)存空間。

2）從最新產(chǎn)生的最小下界分枝（隊列式（FIFO）分枝限界法）：從最新產(chǎn)生的各子集中按順序選擇各結(jié)點進(jìn)行分枝，對于下屆比上屆還大的節(jié)點不進(jìn)行分枝。

優(yōu)點：節(jié)省了空間；缺點：需要較多的分枝運(yùn)算，耗費的時間較多。

這兩個原則更進(jìn)一步說明了，在算法設(shè)計中的時空轉(zhuǎn)換概念。

分枝限界法已經(jīng)成功地應(yīng)用于求解整數(shù)規(guī)劃問題、生產(chǎn)進(jìn)度表問題、貨郎擔(dān)問題、選址問題、背包問題以及可行解的數(shù)目為有限的許多其它問題。對于不同的問題，分枝與界限的步驟和內(nèi)容可能不同，但基本原理是一樣的。

分枝限界法的步驟分枝限界法是組合優(yōu)化問題的有效求解方法，其步驟如下所述：

步驟一：如果問題的目標(biāo)為最小化，則設(shè)定目前最優(yōu)解的值 。

步驟二：根據(jù)分枝法則（Branching rule），從尚未被洞悉（Fathomed）節(jié)點（局部解）中選擇一個節(jié)點，并在此節(jié)點的下一階層中分為幾個新的節(jié)點。

步驟三：計算每一個新分枝出來的節(jié)點的下限值（Lower bound，LB）

步驟四：對每一節(jié)點進(jìn)行洞悉條件測試，若節(jié)點滿足以下任意一個條件，則此節(jié)點可洞悉而不再被考慮：

（1）此節(jié)點的下限值大于等于Z值。

（2）已找到在此節(jié)點中，具最小下限值的可行解；若此條件成立，則需比較此可行解與Z值，若前者較小，則需更新Z值，燕以此為可行解的值。

（3）此節(jié)點不可能包含可行解。

步驟五：判斷是否仍有尚未被洞悉的節(jié)點，如果有，則進(jìn)行步驟二，如果已無尚未被洞悉的節(jié)點，則演算停止，并得到最優(yōu)解。

Kolen等曾利用此方法求解含時間窗約束的車輛巡回問題，其實驗的節(jié)點數(shù)范圍為6-15。當(dāng)節(jié)點數(shù)為6時，計算機(jī)演算所花費的時間大約1分鐘（計算機(jī)型為VAZ11/785），當(dāng)節(jié)點數(shù)擴(kuò)大至12時，計算機(jī)有內(nèi)存不足的現(xiàn)象產(chǎn)生，所以分枝定界法比較適用于求解小型問題。Held和Karp指出分枝定界法的求解效率，與其界限設(shè)定的寬緊有極大的關(guān)系。2

算法分析優(yōu)點可以求得最優(yōu)解、平均速度快。

因為從最小下界分支，每次算完限界后，把搜索樹上當(dāng)前所有的葉子結(jié)點的限界進(jìn)行比較，找出限界最小的結(jié)點，此結(jié)點即為下次分支的結(jié)點。這種決策的優(yōu)點是檢查子問題較少，能較快的求得最佳解。

缺點要存儲很多葉子結(jié)點的限界和對應(yīng)的耗費矩陣?；ㄙM很多內(nèi)存空間。

存在的問題：分枝限界法可應(yīng)用于大量組合優(yōu)化問題。其關(guān)鍵技術(shù)在于各結(jié)點權(quán)值如何估計，可以說一個分支定界求解方法的效率基本上由值界方法決定，若界估計不好，在極端情況下將與窮舉搜索沒多大區(qū)別。3