第6章分支界限法

2023/2/1計算機(jī)算法設(shè)計與分析1第六章

分支限界法2023/2/1計算機(jī)算法設(shè)計與分析2分支限界法的求解目標(biāo)分支限界法與回溯法的求解目標(biāo)不同。回溯法的求解目標(biāo)是找出解空間樹T中滿足約束條件的所有解。分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。2023/2/1計算機(jī)算法設(shè)計與分析3分支限界法與回溯法的不同由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法有兩點(diǎn)不同：①回溯法只通過約束條件剪去非可行解，而分支限界法不僅通過約束條件，而且通過目標(biāo)函數(shù)的限界來減少無效搜索，也就是剪掉了某些不包含最優(yōu)解的可行解。②在解空間樹上的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。2023/2/1計算機(jī)算法設(shè)計與分析4分支限界法是最佳優(yōu)先搜索法分支限界法就是最佳優(yōu)先(包括廣度優(yōu)先在內(nèi))的搜索法。分支限界法將要搜索的結(jié)點(diǎn)按評價函數(shù)的優(yōu)劣排序，讓好的結(jié)點(diǎn)優(yōu)先搜索，將壞的結(jié)點(diǎn)剪去。所以準(zhǔn)確說，此方法應(yīng)稱為界限剪支法。分支限界法中有兩個要點(diǎn)：(1)評價函數(shù)的構(gòu)造；(2)搜索路徑的構(gòu)造。2023/2/1計算機(jī)算法設(shè)計與分析5評價函數(shù)的構(gòu)造評價函數(shù)要能夠提供一個評定候選擴(kuò)展結(jié)點(diǎn)的方法，以便確定哪個結(jié)點(diǎn)最有可能在通往目標(biāo)的最佳路徑上。一個評價函數(shù)f(d)通?？梢杂蓛蓚€部分構(gòu)成：⑴從開始結(jié)點(diǎn)到結(jié)點(diǎn)d的已有耗損值g(d)，和⑵再從結(jié)點(diǎn)d到達(dá)目標(biāo)的期望耗損值h(d)。即：f(d)=g(d)+h(d)通常g(d)的構(gòu)造較易，h(d)的構(gòu)造較難。2023/2/1計算機(jī)算法設(shè)計與分析6搜索路徑的構(gòu)造在回溯法中，每次僅考察一條路徑，因而只需要構(gòu)造這一條路徑即可：前進(jìn)時記下相應(yīng)結(jié)點(diǎn)，回溯時刪去最末尾結(jié)點(diǎn)的記錄。這比較容易實(shí)現(xiàn)。在分支限界法中，是同時考察若干條路徑，那么又該如何構(gòu)造搜索的路徑呢？對每一個擴(kuò)展的結(jié)點(diǎn)，建立三個信息：(1)該結(jié)點(diǎn)的名稱；(2)它的評價函數(shù)值；(3)指向其前驅(qū)的指針；這樣一旦找到目標(biāo)，即可逆向構(gòu)造其路徑。用一個表保存準(zhǔn)備擴(kuò)展的結(jié)點(diǎn)，稱為Open表。用一個表保存已搜索過的結(jié)點(diǎn)，稱為Closed表。2023/2/1計算機(jī)算法設(shè)計與分析7分支限界法的一般算法⑴計算初始結(jié)點(diǎn)s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠Φ){⑶從Open中取出[p,f(p),x](f(p)為最小);⑷將[p,f(p),x]放入Closed;⑸若p是目標(biāo)，則成功返回；否則⑹{產(chǎn)生p的后繼d并計算f(d)；對每個后繼d有二種情況：①dClosed||dOpen；②dOpen&&dClosed。⑺{(lán)若([d,f’(d),p]Closed||[d,f’(d),p]Open)&&f(d)＜f’(d)，則刪去舊結(jié)點(diǎn)并將[d,f(d),p]重新插入到Open中;否則⑻將[d,f(d),p]插入到Open中}}}。2023/2/1計算機(jī)算法設(shè)計與分析8分支限界法求單源最短路徑單源最短路徑問題的評價函數(shù)的構(gòu)造：g(d)定義為從源s到結(jié)點(diǎn)d所走的路徑長度：g(d)=g(p)+C[p][d]這里p為d的前驅(qū)結(jié)點(diǎn)，C[p][d]為p到d的距離。h(d)定義為0。于是f(d)=g(d)。源s的評價函數(shù)f(s)=0。

評價函數(shù)的下界為0；上界初始時為∞，以后不斷用取得的更短路徑的長度來替代。2023/2/1計算機(jī)算法設(shè)計與分析9分支限界法求最短路徑舉例12543102050100301060賦權(quán)圖G初始時，將源[1,0,0]放入Open，Closed為空。Open表Closed表取出[1,0,0]放入Closed；生成其后繼[2,10,1]、[4,30,1]和[5,100,1]，并依序放入Open。取出[2,10,1]放入Closed；生成其后繼[3,60,2]，并依序插入Open。取出[4,30,1]放入Closed；生成其后繼[3,50,4]和[5,90,4]，修訂Open中已有的兩個結(jié)點(diǎn)并依序排列。取出[3,50,4]放入Closed；生成其后繼[2,100,3]和[5,60,3]，前者因劣于Closed中的[2,10,1]而被拋棄，后者修訂了Open中的[5,90,4]。取出[5,60,3]，因其已經(jīng)是目標(biāo)結(jié)點(diǎn)，算法成功并終止。依據(jù)逆向指針可得最短路徑為1→4→3→5。2023/2/1計算機(jī)算法設(shè)計與分析1015迷問題在一個4×4的方格棋盤上，放著15個數(shù)字1,2,…,15，每個數(shù)字占一格，空出一格，要求通過盡量少次移動格中的數(shù)字，將一個給定的初態(tài)變成目標(biāo)狀態(tài)。移動的規(guī)則是：每次只能在空格的上下左右4個位置任選一個移入空格。2023/2/1計算機(jī)算法設(shè)計與分析11問題分析對任意給定的初態(tài)，狀態(tài)不再現(xiàn)的各種可能的移動，將產(chǎn)生多達(dá)16！種不同的狀態(tài)，而且其中只有一個狀態(tài)是目標(biāo)狀態(tài)。在狀態(tài)空間樹中，用空格的移動來代表數(shù)字的相應(yīng)的移動。結(jié)點(diǎn)d的一個兒子結(jié)點(diǎn)代表了從狀態(tài)d經(jīng)過一次合法的移動所到達(dá)的狀態(tài)。用回溯法肯定可以找到所求的最優(yōu)解，但比較盲目。2023/2/1計算機(jī)算法設(shè)計與分析12構(gòu)造15迷問題的評價函數(shù)評價函數(shù)f(d)=g(d)+h(d)，其中：⑴從開始結(jié)點(diǎn)到結(jié)點(diǎn)d的已有耗損值g(d)，在此就設(shè)為從根到結(jié)點(diǎn)d的路徑長。⑵從結(jié)點(diǎn)d到達(dá)目標(biāo)的期望耗損值h(d)。在此可設(shè)為15個數(shù)字中還沒有到達(dá)相應(yīng)目標(biāo)位置的數(shù)字的個數(shù)。搜索過程見圖6.22023/2/1計算機(jī)算法設(shè)計與分析131+41+41+21+42+12+32+33+23+02023/2/1計算機(jī)算法設(shè)計與分析14界限(Bounding)評價函數(shù)f(d)關(guān)系著算法的效率乃至成敗。因為在大多數(shù)問題中f(d)只是個估計值，所以單靠f(d)是不夠的。通常還要設(shè)計它的上下界函數(shù)U(d)和L(d)。L(d)≤f(d)≤U(d)。所謂分支限界法就是通過評價函數(shù)及其上下界函數(shù)的計算，將狀態(tài)空間中不可能產(chǎn)生最佳解的子樹剪去，減少搜索的范圍，提高效率。因而更準(zhǔn)確的稱呼應(yīng)是“界限剪支法”2023/2/1計算機(jī)算法設(shè)計與分析15界限剪枝法求0-1背包問題在回溯法中的“剪枝”：通過“物品總重量不能大于背包容量”這一約束條件將非可行解剪去。界限剪枝法中的“剪枝”：通過構(gòu)造更加嚴(yán)格的約束條件（即限界函數(shù)）將一些非最優(yōu)解的可行解分支也剪去，從而大大減少搜索空間。限界函數(shù)如何構(gòu)造呢？2023/2/1計算機(jī)算法設(shè)計與分析160-1背包問題的限界函數(shù)評價函數(shù)f(d)=背包中已經(jīng)裝載的物品價值限界函數(shù)u(d)=當(dāng)前已經(jīng)找到的最好的可行解的值-（背包中已經(jīng)裝載的物品價值+剩余可選擇物品的總價值）若u(d)>0，則說明即使把剩余的所有物品都裝入背包也不可能得到更優(yōu)的可行解，所以無須擴(kuò)展該結(jié)點(diǎn)，可以剪枝。算法請自行完成2023年2月1日17分支限界法的基本思想分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時為止。2023年2月1日18常見的兩種分支限界法從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式導(dǎo)致不同的分支限界法：隊列式(FIFO)分支限界法：將活結(jié)點(diǎn)表組織成一個隊列，按照隊列先進(jìn)先出（FIFO）原則選取下一個節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。優(yōu)先隊列式分支限界法：將活結(jié)點(diǎn)表組織成一個優(yōu)先隊列，按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。最大優(yōu)先隊列：使用最大堆，體現(xiàn)最大效益優(yōu)先最小優(yōu)先隊列：使用最小堆，體現(xiàn)最小費(fèi)用優(yōu)先2023年2月1日19

隊列式分支限界法的搜索解空間樹的方式類似于解空間樹的寬度優(yōu)先搜索，不同的是隊列式分支限界法不搜索以不可行結(jié)點(diǎn)（已經(jīng)被判定不能導(dǎo)致可行解或不能導(dǎo)致最優(yōu)解的結(jié)點(diǎn)）為根的子樹。這是因為，按照規(guī)則，這樣的結(jié)點(diǎn)未被列入活結(jié)點(diǎn)表。2023年2月1日20優(yōu)先隊列式分支限界法的搜索方式是根據(jù)活結(jié)點(diǎn)的優(yōu)先級確定下一個擴(kuò)展結(jié)點(diǎn)。結(jié)點(diǎn)的優(yōu)先級常用一個與該結(jié)點(diǎn)有關(guān)的評價函數(shù)值f(d)來表示。最大優(yōu)先隊列規(guī)定f(d)值較大的結(jié)點(diǎn)的優(yōu)先級較高。在算法實(shí)現(xiàn)時通常用一個最大堆來實(shí)現(xiàn)最大優(yōu)先隊列，用最大堆的Deletemax運(yùn)算抽取堆中的下一個結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，體現(xiàn)最大效益優(yōu)先的原則。類似地，最小優(yōu)先隊列規(guī)定f(d)值較小的結(jié)點(diǎn)的優(yōu)先級較高。在算法實(shí)現(xiàn)時，常用一個最小堆來實(shí)現(xiàn)，用最小堆的Deletemin運(yùn)算抽取堆中下一個結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，體現(xiàn)最小耗費(fèi)優(yōu)先的原則。如何確定合適的評價函數(shù)好的評價函數(shù)不僅計算簡單，還要保證最優(yōu)解在搜索空間中，更重要的是能在搜索的早期對超出目標(biāo)函數(shù)界的結(jié)點(diǎn)進(jìn)行丟棄，減少搜索空間，從而盡快找到問題的最優(yōu)解。2023年2月1日212023/2/1計算機(jī)算法設(shè)計與分析22用分支限界法求TSPTSP是求排列的問題，不是僅找一條路徑而已。因而需要對分支限界法的一般算法作些修改：(1)待擴(kuò)展的結(jié)點(diǎn)如果在本路徑上已經(jīng)出現(xiàn)，則不再擴(kuò)展，但若是在其他路徑上出現(xiàn)過，則仍需要擴(kuò)展。(2)新結(jié)點(diǎn)，無論其優(yōu)劣，既不影響其它路徑上的結(jié)點(diǎn)，也不受其它路徑上的結(jié)點(diǎn)的影響。(3)依據(jù)上界函數(shù)決定結(jié)點(diǎn)是否可以剪去。2023/2/1計算機(jī)算法設(shè)計與分析23分支限界法求排列⑴計算初始結(jié)點(diǎn)s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠Φ){⑶從Open中取出[p,f(p),L];//L是路徑已有結(jié)點(diǎn)⑷若f(p)≥U，則拋棄該路徑；⑸若p是目標(biāo)，則考慮修改上界函數(shù)值；否則⑹{將[p,f(p),L]放入Closed;⑺在該路徑上擴(kuò)展結(jié)點(diǎn)p；對每個后繼d⑻{計算f(d)；⑼若f(d)＜U,則{L=L{p};將[d,f(d),L]依序放入Open。}}}}2023/2/1計算機(jī)算法設(shè)計與分析24分支限界法求TSP舉例設(shè)有向圖G=(V,E)的邊的代價矩陣為C=[cij]。若不存在有向邊<i,j>∈E，則定義cij=∞且規(guī)定cii=∞。不失一般性，設(shè)周游路線均以頂點(diǎn)1為起點(diǎn)。左下為一個有向圖G的代價矩陣C?！?54031275∞1730251915∞6195024∞6228710∞評價函數(shù)f(d)為1到d的代價減去已經(jīng)走過的邊數(shù)。初始時f(1)=0;f(d)=f(p)+cpd–1，這里p是d的前驅(qū)。2023/2/1計算機(jī)算法設(shè)計與分析25分支限界法求TSP的搜索∞254031275∞1730251915∞6195024∞6228710∞102243394305262340453548523333243542793535453246437234946242843584286找到了第一條周游路線1→5→3→4→2→1，其長度為95。這不是最短周游路線，需要修改上界后繼續(xù)搜索。2023/2/1計算機(jī)算法設(shè)計與分析26歸約矩陣以及約數(shù)前面的搜索的效率不高，幾乎要搜索全部的狀態(tài)空間。其原因是評價函數(shù)以及上下界的估計太低。為了設(shè)計求解TSP問題的更好的評價函數(shù)，先定義其代價矩陣的歸約矩陣和約數(shù)。給定代價矩陣C，從C的任何行i(或列i)的各元素中減去此行(或此列)的最小元素的值r(i)(或r’(i))，稱為對i行(或i列)的歸約。將C的各行和各列都?xì)w約后的矩陣稱為C的歸約矩陣。和數(shù)r=∑i≤nr(i)+∑i≤nr’(i)

稱為C的約數(shù)。2023/2/1計算機(jī)算法設(shè)計與分析27例子中的歸約矩陣和約數(shù)計算前面例子中的歸約矩陣及其約數(shù)如下：∞254031275∞1730251915∞6195024∞6228710∞先做行歸約：r(1)=25∞01562r(2)=50∞122520r(3)=11814∞50r(4)=634421∞0r(5)=715103∞再做列歸約：r’(1)=r’(2)=r’(3)=r’(5)=0r’(4)=33222∞0約數(shù)r=47。2023/2/1計算機(jī)算法設(shè)計與分析28約數(shù)是周游路線長度的下界定理：設(shè)C是圖G的代價矩陣，P是周游路線，則P的代價，即∑<i,j>∈Pcij=r+∑<i,j>∈Pc’ij，式中C’=[c’ij]是C的歸約矩陣，r為約數(shù)。證明：由歸約矩陣的構(gòu)造可知：c’ij=cij–r(i)–r’(j)

即cij=c’ij+r(i)+r’(j)。任何周游路線包含n條邊并且對應(yīng)在C中的每行每列有且僅有一條邊。于是∑<i,j>∈Pcij=∑<i,j>∈P(c’ij+r(i)+r’(j))。r+∑<i,j>∈Pc’ij。

2023/2/1計算機(jī)算法設(shè)計與分析29定義期望函數(shù)h(d)對開始結(jié)點(diǎn)1，令g(1)=0，h(1)=r，f(1)=r。若從結(jié)點(diǎn)1選擇了一條邊，不妨設(shè)邊<1,2>，則令g(2)=f(1)+從1到2的距離l，顯然l應(yīng)該是c’12，而不應(yīng)該再是c12了。

那么h(2)=？自然可以想到h(2)可以是從2開始的路線的下界r2。是否也可用類似求r一樣去求新的約數(shù)r2呢？可以，但在此之前應(yīng)將邊<1,2>和所有邊<1,k>和邊<k,2>都刪去，即置c’12、c’1k和c’k2為∞。設(shè)C’p為某路線上結(jié)點(diǎn)p的歸約矩陣。從p選擇邊<p,d>所得到結(jié)點(diǎn)d的歸約矩陣C’d和約數(shù)rd為：(1)將C’p中的c’pd，c’pk和c’kd置為∞，1≤k≤n；(2)依照求歸約矩陣C’的方法對C’p進(jìn)行行歸約和列歸約，便得到了C’d和rd。令f(1)=

g(1)+

h(1)，其中g(shù)(1)=0，h(1)=r。對任意路線上的結(jié)點(diǎn)d，設(shè)p是其前驅(qū)結(jié)點(diǎn)，則f(d)=g(d)+h(d)，其中，g(d)=f(p)+C’p[p][d]，h(d)=rd。2023/2/1計算機(jī)算法設(shè)計與分析30用新的評價函數(shù)求TSP下面用新的評價函數(shù)求前面的例子，我們已經(jīng)求得了它的歸約矩陣C’和約數(shù)r=47。∞015320∞1222201814∞2034418∞015100∞1472g(2)=47+0=47∞∞∞∞∞∞∞∞010801512h(2)=12+3=15f(2)=47+15=62623∞015320∞1222201814∞2034418∞015100∞g(3)=47+15=62

∞∞∞∞∞∞∞∞04313h(3)=1f(3)=63634類似地可求出f(4)=51。515類似地可求出f(5)=50。50下面優(yōu)先擴(kuò)展的是結(jié)點(diǎn)5。2此時C’2是在C’5的基礎(chǔ)上進(jìn)行。右邊就是C’5?！蕖蕖蕖蕖?∞1222∞1814∞2∞34418∞∞

∞000∞g(2)=50+0=50∞∞∞∞∞01601503h(2)=17f(2)=67673類似地計算出f(3)=68684類似地計算出f(4)=8181下面擴(kuò)展f(4)=51的結(jié)點(diǎn)4。并用同樣方法計算它們的評價函數(shù)值。2121369464154下面要擴(kuò)展的結(jié)點(diǎn)是f(2)=62的結(jié)點(diǎn)2。右邊是其對應(yīng)的歸約矩陣C’2。2∞∞

∞

∞

∞∞∞010815∞∞200∞18∞012∞00∞3g(3)=62+0=62；對C’2進(jìn)行歸約，∞∞∞∞∞得h(3)=0；于是f(3)=62。62對結(jié)點(diǎn)2的另外兩個兒子進(jìn)行同樣的計算，得：f(4)=84，f(5)=72。484572下面對f(3)=62的結(jié)點(diǎn)3進(jìn)行擴(kuò)展。它有兩個后繼結(jié)點(diǎn)。345對結(jié)點(diǎn)4，g(4)=62+2=64?！蕖蕖蕖?h(4)=12，于是f(4)=64+12=7676對結(jié)點(diǎn)5，g(5)=62+0=62?！蕖?/p>

∞

∞

∞∞∞∞

∞

∞15∞∞200∞∞∞012∞∞0∞∞∞∞∞∞h(5)=0，于是f(5)=62+0=6262對結(jié)點(diǎn)5(f(5)=62)再進(jìn)行擴(kuò)展。54g(4)=62+0=62，∞∞h(4)=0，f(4)=62。62結(jié)點(diǎn)4是目標(biāo)結(jié)點(diǎn)，找到了第一條路線。4這條路線的長度為62，以其為上界。其余未擴(kuò)展的結(jié)點(diǎn)的評價函數(shù)值均超過上界，因而不再需要擴(kuò)展了?！痢痢痢痢痢痢痢痢痢劣谑钦业搅艘粭l最短的周游路線：1→2→3→5→4→1。2023/2/1計算機(jī)算法設(shè)計與分析31分支邊與二叉樹在構(gòu)造求TSP的搜索樹時，還有另外一種算法稍有點(diǎn)不同，就是將搜索樹構(gòu)造成二叉樹。給定一條最短周游路線P，對于任一條邊<i,j>只有兩種情況，即<i,j>P或者<i,j>P。這就可以表示成右邊的二叉樹：km<i,j>n____<i,