分枝定界說明

分枝定界說明分枝定界說明5/5分枝定界說明分支定界(branchandbound)算法是一種在問題的解空間樹上搜尋問題的解的方法。但與回溯算法不同樣樣，分支定界算法采納廣度優(yōu)先或最小耗費優(yōu)先的方法搜尋解空間樹，而且，在分支定界算法中，每一個活結點只有一次時機成為擴展結點。利用分支定界算法對問題的解空間樹進行搜尋，它的搜尋策略是：1．產生當前擴展結點的全部孩子結點；2．在產生的孩子結點中，扔掉那些不能夠能產生可行解（或最優(yōu)解）的結點；3．將其他的孩子結點加入活結點表；4．從活結點表中選擇下一個活結點作為新的擴展結點。這樣循環(huán)，直到找到問題的可行解（最優(yōu)解）或活結點表為空。從活結點表中選擇下一個活結點作為新的擴展結點，依據選擇方式的不同樣樣，分支定界算法平常能夠分為兩種形式：1．FIFO(FirstInFirstOut)分支定界算法：依據先進先出原則選擇下一個活結點作為擴展結點，即從活結點表中拿出結點的序次與加入結點的序次相同。2．最小耗費或最大收益分支定界算法：在這類狀況下，每個結點都有一個耗費或收益。若是要查找一個擁有最小耗費的解，那么要選擇的下一個擴展結點就是活結點表中擁有最小耗費的活結點；若是要查找一個擁有最大收益的解，那么要選擇的下一個擴展結點就是活結點表中擁有最大收益的活結點。又稱分支定界搜尋法。過程系統(tǒng)綜合的一類方法。該法是將原始問題分解，產生一組子問題。分支是將一組解分為幾組子解，定界是建立這些子組解的目標函數的界線。若是某一子組的解在這些界線以外，就將這一子組舍棄（剪枝）。1/5分支定界法原為運籌學中求解整數規(guī)劃(或混雜整數規(guī)劃)問題的一種方法。用該法追求整數最優(yōu)解的效率很高。將該法原理用于過程系統(tǒng)綜合可大大減少需要計算的方案多天。分支定界法的思想是：第一確立目標值的上下界，邊搜尋邊減掉搜尋樹的某些支，提升搜尋效率。在比賽中，我們有時會碰到一些題目，它們既不能夠夠經過建立數學模型解決，又沒有現(xiàn)成算法能夠套用，也許非遍歷全部狀況才能夠得出正確結果。這時，我們就必定采納搜尋算法來解決問題。搜尋算法按搜尋的方式分有兩類，一類是深度優(yōu)先搜尋，一類是廣度優(yōu)先搜尋。我們知道，深度搜尋編程簡單，程序簡潔易懂，空間需求也比較低，但是這類方法的時間復雜度經常是指數級的，若是不加優(yōu)化，其時間效率幾乎沒法忍耐；而廣度優(yōu)先搜尋固然時間復雜度比前者低一些，但其弘大的空間需求量又經常讓人望而止步。所以，對程序進行優(yōu)化，就成為搜尋算法編程中最重點的一環(huán)。本文所要議論的即是搜尋算法中優(yōu)化程序的一種基本方法棗“剪枝”。什么是剪枝相信剛開始接觸搜尋算法的人，都做過近似迷宮這樣的題目吧。我們在“走迷宮”的時候，一般回溯法思路是這樣的：1、這個方向有路可走，我沒走過2、往這個方向前進3、是死胡同，往回走，回到上一個路口4、重復第一步，直到找著出口2/5這樣的思路很好理解，編程起來也比較簡單。但是當迷宮的規(guī)模很大時，回溯法的缺點便裸露無遺：搜尋耗時極巨，沒法忍耐。我們可不能夠夠夠在向某個方向前進時，先一步判斷出這樣走會不會走到死胡同里呢？這樣一來，搜尋的時間不就可以減少了嗎？答案是：能夠的。剪枝的看法，其實就跟走迷宮避開死胡同差不多。若我們把搜尋的過程看成是對一棵樹的遍歷，那么剪枝顧名思義，就是將樹中的一些“死胡同”，不能夠夠到達我們需要的解的枝條“剪”掉，以減少搜尋的時間。搜尋算法，絕大部分需要用到剪枝。但是，不是全部的枝條都能夠剪掉，這就需要經過設計出合理的判斷方法，以決定某一分支的棄取。在設計判斷方法的時候，需要依據必定的原則。剪枝的原則1、正確性正如上文所述，枝條不是愛剪就能剪的。若是任意剪枝，把帶有最優(yōu)解的那一分支也剪掉了的話，剪枝也就失掉了意義。所以，剪枝的前提是必定要保證不扔掉正確的結果。2、正確性在保證了正確性的基礎上，我們應該依據詳盡問題詳盡剖析，采納適合的判斷手段，使不包括最優(yōu)解的枝條盡可能多的被剪去，以達到程序“最優(yōu)化”的目的。能夠說，剪枝的正確性，是權衡一個優(yōu)化算法利害的標準。3、高效性設計優(yōu)化程序的根本目的，是要減少搜尋的次數，使程序運轉的時間減少。但為了使搜尋次數盡可能的減少，我們又必定花時間設計出一個準3/5確性較高的優(yōu)化算法，而當算法的正確性高升，其判斷的次數必定增加，進而又致使耗時的增加，這便引出了矛盾。所以，怎樣在優(yōu)化與效率之間搜尋一個平衡點，使得程序的時間復雜度盡可能降低，相同是特別重要的。若是一個剪枝的判斷奏效特別好，但是它卻需要耗費大批的時間來判斷、比較，結果整個程序運轉起來也跟沒有優(yōu)化過的沒什么差別，這樣就太得失相當了。綜上所述，我們能夠把剪枝優(yōu)化的主要原則概括為六個字：正確、正確、高效。剪枝算法依據其判斷思路可大體分成兩類：可行性剪枝及最優(yōu)性剪枝。對于分支定界算法,上界是已求得的可行解的目標函數值中的最小者,分為初始上界和在探測過程中產生的動向上界.分支定界法在求最優(yōu)解的迭代過程中,若某結點預計的下界不小于已知的上界,則不用從該節(jié)點往下連續(xù)搜尋.所以若能產生一個較好的上界,能夠除掉好多不用要的列舉計算.分支定界算法的實現(xiàn)在描述分支定界算法步驟從前,先對算法涉及到的有關術語進行定義以下:p——分支層數;C*——當前最優(yōu)目標函數值;P*——相應于C*的工件序次;P1——當前節(jié)點(現(xiàn)在需要進行分支的節(jié)點)所對應的部分序列.分支定界算法的推行步驟以下:步驟1初始化:4/5設置p=0,P1=空á集(),C*=設∞當.前節(jié)點總是與P1相對應.此時,當前節(jié)點即根節(jié)點.步驟2計算從當前節(jié)點分支獲得的各個子節(jié)點的下界,并按下界值由小到大對各子節(jié)點排序.令p←p+1.步驟3若是當前節(jié)點被探測盡,令p←p-1,轉步驟6.不然,設當前層(第p層)各活動子節(jié)點中擁有最小下界值的節(jié)點為Q,則在P1尾端加入Q對應第p地址上的工件,此時的當前節(jié)點轉為Q,轉步驟4.步驟4由于當前節(jié)點是同層同父節(jié)點擁有最小下界值的節(jié)點,若是當前節(jié)點下界值大于或等于C*,則不用再搜尋當前節(jié)點及其同層同父的活動節(jié)點,這樣,當前節(jié)點的上一層節(jié)點(父節(jié)點)被探測盡,p←p-1,去掉P1中的最后一個工件,轉步驟6