算法設(shè)計與分析 第六章分支界限法

第六章

分支限界法2023/2/41計算機算法設(shè)計與分析分支限界法是最佳優(yōu)先搜索法分支限界法就是最佳優(yōu)先(包括廣度優(yōu)先在內(nèi))的搜索法。分支限界法將要搜索的結(jié)點按評價函數(shù)的優(yōu)劣排序，讓好的結(jié)點優(yōu)先搜索，將壞的結(jié)點剪去。所以準確說，此方法應稱為界限剪支法。分支限界法中有兩個要點：(1)評價函數(shù)的構(gòu)造；(2)搜索路徑的構(gòu)造。2023/2/42計算機算法設(shè)計與分析評價函數(shù)的構(gòu)造評價函數(shù)要能夠提供一個評定候選擴展結(jié)點的方法，以便確定哪個結(jié)點最有可能在通往目標的最佳路徑上。一個評價函數(shù)f(d)通?？梢杂蓛蓚€部分構(gòu)成：⑴從開始結(jié)點到結(jié)點d的已有耗損值g(d)，和⑵再從結(jié)點d到達目標的期望耗損值h(d)。即：f(d)=g(d)+h(d)通常g(d)的構(gòu)造較易，h(d)的構(gòu)造較難。2023/2/43計算機算法設(shè)計與分析搜索路徑的構(gòu)造在回溯法中，每次僅考察一條路徑，因而只需要構(gòu)造這一條路徑即可：前進時記下相應結(jié)點，回溯時刪去最末尾結(jié)點的記錄。這比較容易實現(xiàn)。在分支限界法中，是同時考察若干條路徑，那么又該如何構(gòu)造搜索的路徑呢？對每一個擴展的結(jié)點，建立三個信息：(1)該結(jié)點的名稱；(2)它的評價函數(shù)值；(3)指向其前驅(qū)的指針；這樣一旦找到目標，即可逆向構(gòu)造其路徑。用一個表保存準備擴展的結(jié)點，稱為Open表。用一個表保存已搜索過的結(jié)點，稱為Closed表。2023/2/44計算機算法設(shè)計與分析分支限界法的一般算法⑴計算初始結(jié)點s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠Φ){⑶從Open中取出[p,f(p),x](f(p)為最小);⑷將[p,f(p),x]放入Closed;⑸若p是目標，則成功返回；否則⑹{產(chǎn)生p的后繼d并計算f(d)

；對每個后繼d有二種情況：①dClosed||dOpen；②dOpen&&dClosed。⑺{若([d,f’(d),p]Closed||[d,f’(d),p]Open)&&f(d)＜f’(d)，則刪去舊結(jié)點并將[d,f(d),p]

重新插入到Open中;否則⑻將[d,f(d),p]

插入到Open中}}}。2023/2/45計算機算法設(shè)計與分析分支限界法求單源最短路徑單源最短路徑問題的評價函數(shù)的構(gòu)造：g(d)定義為從源s到結(jié)點d所走的路徑長度：g(d)=g(p)+C[p][d]這里p為d的前驅(qū)結(jié)點，C[p][d]為p到d的距離。h(d)定義為0。于是f(d)=g(d)。源s的評價函數(shù)f(s)=0。

評價函數(shù)的下界為0；上界初始時為∞，以后不斷用取得的更短路徑的長度來替代。2023/2/46計算機算法設(shè)計與分析分支限界法求最短路徑舉例12543102050100301060賦權(quán)圖G初始時，將源[1,0,0]放入Open，Closed為空。Open表[1,0,0]Closed表取出[1,0,0]放入Closed；生成其后繼[2,10,1]、[4,30,1]和[5,100,1]，并依序放入Open。[1,0,0][5,100,1][4,30,1][2,10,1]取出[2,10,1]放入Closed；生成其后繼[3,60,2]，并依序插入Open。[2,10,1][3,60,2][4,30,1]取出[4,30,1]放入Closed；生成其后繼[3,50,4]和[5,90,4]，修訂Open中已有的兩個結(jié)點并依序排列。[4,30,1][5,90,4][3,50,4]取出[3,50,4]放入Closed；生成其后繼[2,100,3]和[5,60,3]，前者因劣于Closed中的[2,10,1]而被拋棄，后者修訂了Open中的[5,90,4]。[3,50,4][5,60,3]取出[5,60,3]，因其已經(jīng)是目標結(jié)點，算法成功并終止。依據(jù)逆向指針可得最短路徑為1→4→3→5。2023/2/47計算機算法設(shè)計與分析界限(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)生最佳解的子樹剪去，減少搜索的范圍，提高效率。因而更準確的稱呼應是“界限剪支法”2023/2/48計算機算法設(shè)計與分析用分支限界法求TSPTSP是求排列的問題，不是僅找一條路徑而已。因而需要對分支限界法的一般算法作些修改：(1)待擴展的結(jié)點如果在本路徑上已經(jīng)出現(xiàn)，則不再擴展，但若是在其他路徑上出現(xiàn)過，則仍需要擴展。(2)新結(jié)點，無論其優(yōu)劣，既不影響其它路徑上的結(jié)點，也不受其它路徑上的結(jié)點的影響。(3)依據(jù)上界函數(shù)決定結(jié)點是否可以剪去。2023/2/49計算機算法設(shè)計與分析分支限界法求排列⑴計算初始結(jié)點s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠Φ){⑶從Open中取出[p,f(p),L];//L是路徑已有結(jié)點⑷若f(p)≥U，則拋棄該路徑；⑸若p是目標，則考慮修改上界函數(shù)值；否則⑹{將[p,f(p),L]放入Closed;⑺在該路徑上擴展結(jié)點p；對每個后繼d⑻{計算f(d)；⑼若f(d)＜U,則{L=L{p};

將[d,f(d),L]依序放入Open。}}}}2023/2/410計算機算法設(shè)計與分析分支限界法求TSP舉例設(shè)有向圖G=(V,E)的邊的代價矩陣為C=[cij]。若不存在有向邊<i,j>∈E，則定義cij=∞且規(guī)定cii=∞。不失一般性，設(shè)周游路線均以頂點1為起點。左下為一個有向圖G的代價矩陣C?！?5403127

5∞1730251915∞61

95024∞6228710∞評價函數(shù)f(d)為1到d的代價減去已經(jīng)過的邊數(shù)。初始時f(1)=0;f(d)=f(p)+cpd–1，這里p是d的前驅(qū)。2023/2/411計算機算法設(shè)計與分析分支限界法求TSP的搜索∞25403127

5∞1730251915∞61

95024∞6228710∞102243394305262340453548523333243542793535453246437234946242843584286找到了一條周游路線1→5→3→4→2→1，其長度為95。這不是最短周游路線，需要修改上界后繼續(xù)搜索。2023/2/412計算機算法設(shè)計與分析歸約矩陣以及約數(shù)前面的搜索的效率不高，幾乎要搜索全部的狀態(tài)空間。其原因是評價函數(shù)以及上下界的估計太低。為了設(shè)計求解TSP問題的更好的評價函數(shù)，先定義其代價矩陣的歸約矩陣和約數(shù)。給定代價矩陣C，從C的任何行i(或列i)的各元素中減去此行(或此列)的最小元素的值r(i)(或r’(i))，稱為對i行(或i列)的歸約。將C的各行和各列都歸約后的矩陣稱為C的歸約矩陣。和數(shù)r=∑i≤nr(i)+∑i≤nr’(i)

稱為C的約數(shù)。2023/2/413計算機算法設(shè)計與分析例子中的歸約矩陣和約數(shù)計算前面例子中的歸約矩陣及其約數(shù)如下：∞25403127

5∞1730251915∞61

95024∞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/414計算機算法設(shè)計與分析約數(shù)是周游路線長度的下界定理：設(shè)C是圖G的代價矩陣，P是周游路線，則P的代價，即∑<i,j>∈P

cij=r+∑<i,j>∈P

c’ij，

式中C’=[c’ij]是C的歸約矩陣，r為約數(shù)。證明：由歸約矩陣的構(gòu)造可知：c’ij=cij–r(i)–r’(j)

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

cij=∑<i,j>∈P(c’ij+r(i)+r’(j))。r+∑<i,j>∈P

c’ij

。

2023/2/415計算機算法設(shè)計與分析用約數(shù)定義期望函數(shù)h(d)既然約數(shù)是周游路線長度的下界，我們可以考慮用約數(shù)來定義期望函數(shù)h(d)：對開始結(jié)點1，令g(1)=0，h(1)=r，f(1)=r。若從結(jié)點1選擇了一條邊，不妨設(shè)邊<1,2>，則令g(2)=f(1)+從1到2的距離l，顯然l應該是c’12，而不應該再是c12了。

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

。2023/2/417計算機算法設(shè)計與分析期望函數(shù)h(d)的定義應用約數(shù)，可以得到h(d)的定義如下：令f(1)=g(1)+h(1),其中g(shù)(1)=0,h(1)=r。對任意路線上的結(jié)點d，設(shè)p是其前驅(qū)結(jié)點，則

f(d)=g(d)+h(d)，其中，g(d)=f(p)+C’p[p][d]，h(d)=rd。2023/2/418計算機算法設(shè)計與分析用新的評價函數(shù)求TSP下面用新的評價函數(shù)求前面的例子，我們已經(jīng)求得了它的歸約矩陣C’和約數(shù)r=47?！?1532

0∞1222201814∞20

34418∞015100∞1472g(2)=47+0=47∞∞∞∞∞∞∞∞010801512h(2)=12+3=15f(2)=47+15=62623∞01532

0∞1222201814∞20

34418∞015100∞g(3)=47+15=62

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

0∞1222∞1814∞2∞

34418∞∞

∞

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

∞

∞

∞∞∞010815∞∞20

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

∞

∞

∞∞∞∞

∞

∞15∞∞20

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

____<2,1>3622<4,5>453

____<4,5>5684<1,4>664

____<1,4>7653<4,1>862

____<4,1>9748

<2,3>1062____

<2,3>117010

<3,5>1262___

<3,5>136612

<5,4>1462___

<5,4>156614

<1,2>1662____

<1,2>17∞結(jié)點16給出了一條最短周游路線：1→2→3→5→4→12023/2/421計算機算法設(shè)計與分析分支限界法的效率從TSP問題的計算可看出，分支限界法搜索的狀態(tài)空間為O(2n)。對每個結(jié)點的計算時間為O(n2)。因此在最壞情況下，分支限界法計算TSP的時間復雜性為O(n22n)。顯然，用分支限界法計算TSP的空間復雜性為O(n22n)。因為對每個結(jié)點需要n2的空間。2023/2/422計算機算法設(shè)計與分析對評價函數(shù)的討論分支限界法總耗時為O(n22n)，它與回溯法、動態(tài)規(guī)劃法等在時間復雜性上沒有本質(zhì)的區(qū)別。然而，如果評價函數(shù)選擇得好，采用分支限界法可能有一個小得多的常數(shù)因子。好的評價函數(shù)應該有一個盡可能高的下界估計和一個盡可能低的上界估計，從而使得搜索空間能夠得到有效的壓縮，從而提高效率。在理論上可以證明好的評價函數(shù)所搜索的結(jié)點不會多于壞的評價函數(shù)所搜索的結(jié)點。2023/2/423計算機算法設(shè)計與分析關(guān)系、傳遞閉包與搜索定義在集合S上關(guān)系R是笛卡兒直積S×S的一個子集，RS×S。關(guān)系R的傳遞閉包是包含R的最小的具有傳遞性質(zhì)的關(guān)系。若S是有限的，|S|=n，則R可表示為一個n×n的關(guān)系矩陣M或n個結(jié)點的有向圖G。求關(guān)系R的傳遞閉包實際上也就是在有向圖G上的搜索。而反過來，在有向圖G上的搜索也就是求某種關(guān)系的傳遞閉包。2023/2/424計算機算法設(shè)計與分析傳遞閉包的集合算法給定關(guān)系R以及S中的元素a，求R*(a)。

初始化：U=A={a};q=true;while(q){

for(p∈A)U=U∪{d|d∈S且

pRd}；