分枝定界說明

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