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

第六章

分支限界法2023/2/41計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法是最佳優(yōu)先搜索法分支限界法就是最佳優(yōu)先(包括廣度優(yōu)先在內(nèi))的搜索法。分支限界法將要搜索的結(jié)點(diǎn)按評(píng)價(jià)函數(shù)的優(yōu)劣排序，讓好的結(jié)點(diǎn)優(yōu)先搜索，將壞的結(jié)點(diǎn)剪去。所以準(zhǔn)確說，此方法應(yīng)稱為界限剪支法。分支限界法中有兩個(gè)要點(diǎn)：(1)評(píng)價(jià)函數(shù)的構(gòu)造；(2)搜索路徑的構(gòu)造。2023/2/42計(jì)算機(jī)算法設(shè)計(jì)與分析評(píng)價(jià)函數(shù)的構(gòu)造評(píng)價(jià)函數(shù)要能夠提供一個(gè)評(píng)定候選擴(kuò)展結(jié)點(diǎn)的方法，以便確定哪個(gè)結(jié)點(diǎn)最有可能在通往目標(biāo)的最佳路徑上。一個(gè)評(píng)價(jià)函數(shù)f(d)通常可以由兩個(gè)部分構(gòu)成：⑴從開始結(jié)點(diǎn)到結(jié)點(diǎn)d的已有耗損值g(d)，和⑵再?gòu)慕Y(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/43計(jì)算機(jī)算法設(shè)計(jì)與分析搜索路徑的構(gòu)造在回溯法中，每次僅考察一條路徑，因而只需要構(gòu)造這一條路徑即可：前進(jìn)時(shí)記下相應(yīng)結(jié)點(diǎn)，回溯時(shí)刪去最末尾結(jié)點(diǎn)的記錄。這比較容易實(shí)現(xiàn)。在分支限界法中，是同時(shí)考察若干條路徑，那么又該如何構(gòu)造搜索的路徑呢？對(duì)每一個(gè)擴(kuò)展的結(jié)點(diǎn)，建立三個(gè)信息：(1)該結(jié)點(diǎn)的名稱；(2)它的評(píng)價(jià)函數(shù)值；(3)指向其前驅(qū)的指針；這樣一旦找到目標(biāo)，即可逆向構(gòu)造其路徑。用一個(gè)表保存準(zhǔn)備擴(kuò)展的結(jié)點(diǎn)，稱為Open表。用一個(gè)表保存已搜索過的結(jié)點(diǎn)，稱為Closed表。2023/2/44計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法⑴計(jì)算初始結(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并計(jì)算f(d)

；對(duì)每個(gè)后繼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/45計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法求單源最短路徑單源最短路徑問題的評(píng)價(jià)函數(shù)的構(gòu)造：g(d)定義為從源s到結(jié)點(diǎn)d所走的路徑長(zhǎng)度：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的評(píng)價(jià)函數(shù)f(s)=0。

評(píng)價(jià)函數(shù)的下界為0；上界初始時(shí)為∞，以后不斷用取得的更短路徑的長(zhǎng)度來替代。2023/2/46計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法求最短路徑舉例12543102050100301060賦權(quán)圖G初始時(shí)，將源[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中已有的兩個(gè)結(jié)點(diǎn)并依序排列。[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)是目標(biāo)結(jié)點(diǎn)，算法成功并終止。依據(jù)逆向指針可得最短路徑為1→4→3→5。2023/2/47計(jì)算機(jī)算法設(shè)計(jì)與分析界限(Bounding)評(píng)價(jià)函數(shù)f(d)關(guān)系著算法的效率乃至成敗。因?yàn)樵诖蠖鄶?shù)問題中f(d)只是個(gè)估計(jì)值，所以單靠f(d)是不夠的。通常還要設(shè)計(jì)它的上下界函數(shù)U(d)和L(d)。L(d)≤f(d)≤U(d)。所謂分支限界法就是通過評(píng)價(jià)函數(shù)及其上下界函數(shù)的計(jì)算，將狀態(tài)空間中不可能產(chǎn)生最佳解的子樹剪去，減少搜索的范圍，提高效率。因而更準(zhǔn)確的稱呼應(yīng)是“界限剪支法”2023/2/48計(jì)算機(jī)算法設(shè)計(jì)與分析用分支限界法求TSPTSP是求排列的問題，不是僅找一條路徑而已。因而需要對(duì)分支限界法的一般算法作些修改：(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/49計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法求排列⑴計(jì)算初始結(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；對(duì)每個(gè)后繼d⑻{計(jì)算f(d)；⑼若f(d)＜U,則{L=L{p};

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

5∞1730251915∞61

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

5∞1730251915∞61

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

稱為C的約數(shù)。2023/2/413計(jì)算機(jī)算法設(shè)計(jì)與分析例子中的歸約矩陣和約數(shù)計(jì)算前面例子中的歸約矩陣及其約數(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計(jì)算機(jī)算法設(shè)計(jì)與分析約數(shù)是周游路線長(zhǎng)度的下界定理：設(shè)C是圖G的代價(jià)矩陣，P是周游路線，則P的代價(jià)，即∑<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條邊并且對(duì)應(yīng)在C中的每行每列有且僅有一條邊。于是∑<i,j>∈P

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

c’ij

。

2023/2/415計(jì)算機(jī)算法設(shè)計(jì)與分析用約數(shù)定義期望函數(shù)h(d)既然約數(shù)是周游路線長(zhǎng)度的下界，我們可以考慮用約數(shù)來定義期望函數(shù)h(d)：對(duì)開始結(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呢？2023/2/416計(jì)算機(jī)算法設(shè)計(jì)與分析求新的約數(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’的方法對(duì)C’p進(jìn)行行歸約和列歸約，便得到了C’d和rd

。2023/2/417計(jì)算機(jī)算法設(shè)計(jì)與分析期望函數(shù)h(d)的定義應(yīng)用約數(shù)，可以得到h(d)的定義如下：令f(1)=g(1)+h(1),其中g(shù)(1)=0,h(1)=r。對(duì)任意路線上的結(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/418計(jì)算機(jī)算法設(shè)計(jì)與分析用新的評(píng)價(jià)函數(shù)求TSP下面用新的評(píng)價(jià)函數(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)先擴(kuò)展的是結(jié)點(diǎn)5。2此時(shí)C’2是在C’5的基礎(chǔ)上進(jìn)行。右邊就是C’5?！蕖蕖蕖蕖?/p>

0∞1222∞1814∞2∞

34418∞∞

∞

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

∞

∞

∞∞∞010815∞∞20

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

∞

∞

∞∞∞∞

∞

∞15∞∞20

0∞∞∞012∞∞0∞∞∞∞∞∞h(5)=0，于是f(5)=62+0=6262對(duì)結(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這條路線的長(zhǎng)度為62，以其為上界。其余未擴(kuò)展的結(jié)點(diǎn)的評(píng)價(jià)函數(shù)值均超過上界，因而不再需要擴(kuò)展了?！痢痢痢痢痢痢痢痢痢劣谑钦业搅艘粭l最短的周游路線：1→2→3→5→4→1。2023/2/419計(jì)算機(jī)算法設(shè)計(jì)與分析分支邊與二叉樹在構(gòu)造求TSP的搜索樹時(shí)，還有另外一種算法稍有點(diǎn)不同，就是將搜索樹構(gòu)造成二叉樹。給定一條最短周游路線P，對(duì)于任一條邊<i,j>只有兩種情況，即<i,j>P或者<i,j>P。這就可以表示成右邊的二叉樹：km<i,j>n____<i,j>其中____<i,j>表示<i,j>P。這樣的邊稱為分支邊。2023/2/420計(jì)算機(jī)算法設(shè)計(jì)與分析用二叉樹求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é)點(diǎn)16給出了一條最短周游路線：1→2→3→5→4→12023/2/421計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的效率從TSP問題的計(jì)算可看出，分支限界法搜索的狀態(tài)空間為O(2n)。對(duì)每個(gè)結(jié)點(diǎn)的計(jì)算時(shí)間為O(n2)。因此在最壞情況下，分支限界法計(jì)算TSP的時(shí)間復(fù)雜性為O(n22n)。顯然，用分支限界法計(jì)算TSP的空間復(fù)雜性為O(n22n)。因?yàn)閷?duì)每個(gè)結(jié)點(diǎn)需要n2的空間。2023/2/422計(jì)算機(jī)算法設(shè)計(jì)與分析對(duì)評(píng)價(jià)函數(shù)的討論分支限界法總耗時(shí)為O(n22n)，它與回溯法、動(dòng)態(tài)規(guī)劃法等在時(shí)間復(fù)雜性上沒有本質(zhì)的區(qū)別。然而，如果評(píng)價(jià)函數(shù)選擇得好，采用分支限界法可能有一個(gè)小得多的常數(shù)因子。好的評(píng)價(jià)函數(shù)應(yīng)該有一個(gè)盡可能高的下界估計(jì)和一個(gè)盡可能低的上界估計(jì)，從而使得搜索空間能夠得到有效的壓縮，從而提高效率。在理論上可以證明好的評(píng)價(jià)函數(shù)所搜索的結(jié)點(diǎn)不會(huì)多于壞的評(píng)價(jià)函數(shù)所搜索的結(jié)點(diǎn)。2023/2/423計(jì)算機(jī)算法設(shè)計(jì)與分析關(guān)系、傳遞閉包與搜索定義在集合S上關(guān)系R是笛卡兒直積S×S的一個(gè)子集，RS×S。關(guān)系R的傳遞閉包是包含R的最小的具有傳遞性質(zhì)的關(guān)系。若S是有限的，|S|=n，則R可表示為一個(gè)n×n的關(guān)系矩陣M或n個(gè)結(jié)點(diǎn)的有向圖G。求關(guān)系R的傳遞閉包實(shí)際上也就是在有向圖G上的搜索。而反過來，在有向圖G上的搜索也就是求某種關(guān)系的傳遞閉包。2023/2/424計(jì)算機(jī)算法設(shè)計(jì)與分析傳遞閉包的集合算法給定關(guān)系R以及S中的元素a，求R*(a)。

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

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

pRd}；