分支限界算法

2024-07-21 02:51:18

字體：大中小

來源：轉載

供稿：網友

分支限界算法 branch and bound

▼分支定界 (branch and bound) 算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同，分支定界算法采用廣度優先或最小耗費優先的方法搜索解空間樹，并且，在分支定界算法中，每一個活結點只有一次機會成為擴展結點。　　利用分支定界算法對問題的解空間樹進行搜索，它的搜索策略是：　　1 ．產生當前擴展結點的所有孩子結點；　　2 ．在產生的孩子結點中，拋棄那些不可能產生可行解（或最優解）的結點；　　3 ．將其余的孩子結點加入活結點表；　　4 ．從活結點表中選擇下一個活結點作為新的擴展結點。　　如此循環，直到找到問題的可行解（最優解）或活結點表為空。　　從活結點表中選擇下一個活結點作為新的擴展結點，根據選擇方式的不同，分支定界算法通常可以分為兩種形式：　　1 ． FIFO(First In First Out) 分支定界算法：按照先進先出原則選擇下一個活結點作為擴展結點，即從活結點表中取出結點的順序與加入結點的順序相同。　　2 ．最小耗費或最大收益分支定界算法：在這種情況下，每個結點都有一個耗費或收益。如果要查找一個具有最小耗費的解，那么要選擇的下一個擴展結點就是活結點表中具有最小耗費的活結點；如果要查找一個具有最大收益的解，那么要選擇的下一個擴展結點就是活結點表中具有最大收益的活結點。　　又稱分支定界搜索法。過程系統綜合的一類方法。該法是將原始問題分解，產生一組子問題。分支是將一組解分為幾組子解，定界是建立這些子組解的目標函數的邊界。如果某一子組的解在這些邊界之外，就將這一子組舍棄（剪枝）。分支定界法原為運籌學中求解整數規劃(或混合整數規劃)問題的一種方法。用該法尋求整數最優解的效率很高。將該法原理用于過程系統綜合可大大減少需要計算的方案數日。　　分支定界法的思想是：首先確定目標值的上下界，邊搜索邊減掉搜索樹的某些支，提高搜索效率。　　在競賽中，我們有時會碰到一些題目，它們既不能通過建立數學模型解決，又沒有現成算法可以套用，或者非遍歷所有狀況才可以得出正確結果。這時，我們就必須采用搜索算法來解決問題。　　搜索算法按搜索的方式分有兩類，一類是深度優先搜索，一類是廣度優先搜索。我們知道，深度搜索編程簡單，程序簡潔易懂，空間需求也比較低，但是這種方法的時間復雜度往往是指數級的，倘若不加優化，其時間效率簡直無法忍受；而廣度優先搜索雖然時間復雜度比前者低一些，但其龐大的空間需求量又往往讓人望而卻步。　　所以，對程序進行優化，就成為搜索算法編程中最關鍵的一環。　　本文所要討論的便是搜索算法中優化程序的一種基本方法棗“剪枝”。　　什么是剪枝　　相信剛開始接觸搜索算法的人，都做過類似迷宮這樣的題目吧。我們在“走迷宮”的時候，一般回溯法思路是這樣的：　　1、這個方向有路可走，我沒走過　　2、往這個方向前進　　3、是死胡同，往回走，回到上一個路口　　4、重復第一步，直到找著出口　　這樣的思路很好理解，編程起來也比較容易。但是當迷宮的規模很大時，回溯法的缺點便暴露無遺：搜索耗時極巨，無法忍受。　　我們可不可以在向某個方向前進時，先一步判斷出這樣走會不會走到死胡同里呢？這樣一來，搜索的時間不就可以減少了嗎？　　答案是：可以的。　　剪枝的概念，其實就跟走迷宮避開死胡同差不多。若我們把搜索的過程看成是對一棵樹的遍歷，那么剪枝顧名思義，就是將樹中的一些“死胡同”，不能到達我們需要的解的枝條“剪”掉，以減少搜索的時間。　　搜索算法，絕大部分需要用到剪枝。然而，不是所有的枝條都可以剪掉，這就需要通過設計出合理的判斷方法，以決定某一分支的取舍。在設計判斷方法的時候，需要遵循一定的原則。　　剪枝的原則　　1、正確性　　正如上文所述，枝條不是愛剪就能剪的。如果隨便剪枝，把帶有最優解的那一分支也剪掉了的話，剪枝也就失去了意義。所以，剪枝的前提是一定要保證不丟失正確的結果。　　2、準確性　　在保證了正確性的基礎上，我們應該根據具體問題具體分析，采用合適的判斷手段，使不包含最優解的枝條盡可能多的被剪去，以達到程序“最優化”的目的。可以說，剪枝的準確性，是衡量一個優化算法好壞的標準。　　3、高效性設計優化程序的根本目的，是要減少搜索的次數，使程序運行的時間減少。但為了使搜索次數盡可能的減少，我們又必須花工夫設計出一個準確性較高的優化算法，而當算法的準確性升高，其判斷的次數必定增多，從而又導致耗時的增多，這便引出了矛盾。　　因此，如何在優化與效率之間尋找一個平衡點，使得程序的時間復雜度盡可能降低，同樣是非常重要的。倘若一個剪枝的判斷效果非常好，但是它卻需要耗費大量的時間來判斷、比較，結果整個程序運行起來也跟沒有優化過的沒什么區別，這樣就太得不償失了。　　綜上所述，我們可以把剪枝優化的主要原則歸結為六個字：正確、準確、高效。　　剪枝算法按照其判斷思路可大致分成兩類：可行性剪枝及最優性剪枝。　　對于分支定界算法,上界是已求得的可行解的目標函數值中的最小者,分為初始上界和在探測過程中產生的動態上界.分支定界法在求最優解的迭代過程中, 若某結點估計的下界不小于已知的上界, 則不必從該節點往下繼續搜索. 因此若能產生一個較好的上界, 可以消除許多不必要的列舉計算.　　分支定界算法的實現　　在描述分支定界算法步驟之前, 先對算法涉及到的有關術語進行定義如下:　　p —— 分支層數;　　C*—— 當前最優目標函數值;　　P*—— 相應于C*的工件順序;　　P1—— 當前節點(現在需要進行分支的節點)所對應的部分序列.　　分支定界算法的實施步驟如下:　　步驟1　初始化: 設置p = 0, P 1 = Á (空集) , C* = ∞.設當前節點總是與P 1 相對應. 此時, 當前節點即根節點.　　步驟2　計算從當前節點分支得到的各個子節點的下界, 并按下界值由小到大對各子節點排序. 令p ←p + 1.　　步驟3　如果當前節點被探測盡, 令p ←p - 1, 轉步驟6. 否則, 設當前層(第p 層) 各活動子節點中具有最小下界值的節點為Q , 則在P 1末尾加入Q 對應第p 位置上的工件, 此時的當前節點轉為Q , 轉步驟4.　　步驟4　因為當前節點是同層同父節點具有最小下界值的節點, 如果當前節點下界值大于或等于C* , 則不必再搜索當前節點及其同層同父的活動節點, 這樣, 當前節點的上一層節點(父節點)被探測盡, p ←p - 1, 去掉P 1 中的最后一個工件,轉步驟6. 否則, 轉步驟5.　　步驟5　如果p = n, 則得到一個較優順序.令P* = P 1, C* 是當前節點的下界值, p ←p - 1,去掉P 1 中最后一個工件, 轉步驟6; 否則轉步驟2.

　　步驟6　若p ≠ 0, 去掉P 1 中最后一個工件,轉步驟3; 否則, 算法停止. C* 是最優的目標函數值, P* 是最優順序.

分枝限界法

　　branch and bound method 　一種求解離散最優化問題的計算分析方法，又稱分枝定界法。它是由R.J.達金和蘭德－多伊格在20世紀60年代初提出的。這種方法通常僅需計算和分析部分允許解，即可求得最優解。因此在求解分派問題和整數規劃問題時常用此法。　　基本方法求解一個約束條件較多的問題A,可以暫緩考慮部分條件，變換成問題B,先求B的最優解。B的最優解一定比 A的好（或相當）。再將原來暫緩考慮的部分條件逐步插入問題B中，得到B的若干子問題，稱為分枝。求解這些子問題，淘汰較差的解，直到所有暫緩考慮的部分條件全部插入為止。這時求得的最優解就是問題A的最優解。　　分派問題設生產任務Ⅰ、Ⅱ、Ⅲ和Ⅳ,皆可在4臺不同設備A、B、C和D上去完成。由于設備性能和技術要求等不同，在不同設備上完成各項任務所需的費用（或時間）均不相同，下表列出某一具體問題的任務、設備和費用的數量關系。規定每臺設備只能安排一項生產任務。要求分派這4項生產任務，使總費用為最少。　　首先分析在所有分派方案中，以何種分派方案的費用為最低。由表可知，當分派方案是(I-D)（即任務I交由D設備去完成時，下同）,(Ⅱ-A)，(Ⅲ-C)，(Ⅳ-D)時，即得總費用為最小。它稱為下界。但這樣的分派方案要由 D設備去完成Ⅰ、Ⅳ兩項任務，不符合題意要求。所以稱這個解為非允許解。為此必須加以改進。接著，規定任務Ⅰ交由A去完成，其他任務則選擇費用最小的設備去完成,則由表可知，其總費用為該方案恰好滿足一臺設備完成一項任務的規定，因此總費用193的解稱為允許解。依次計算(I-B),(I-C),(I-D)各分派方案的解,如圖1所示。分析1～4的分派方案后可知,要求的最優解一定在164和148之間，即上界是164，下界是148。這時,只要在方案4這個分枝上繼續進行組合即可。由分派方案5～7可知，方案5的總費用為156，但是非允許解，方案6的總費用是157，是允許解。所以方案6是最優解。其具體分派組合是:(I-D),(Ⅱ-B),(Ⅲ-C)，(Ⅳ-A)。

上一篇：sql 行轉列

下一篇：178. Rank Scores#1