版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第六章
分支限界法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)確說(shuō),此方法應(yīng)稱(chē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)成:⑴從開(kāi)始結(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)的名稱(chēng);(2)它的評(píng)價(jià)函數(shù)值;(3)指向其前驅(qū)的指針;這樣一旦找到目標(biāo),即可逆向構(gòu)造其路徑。用一個(gè)表保存準(zhǔn)備擴(kuò)展的結(jié)點(diǎn),稱(chēng)為Open表。用一個(gè)表保存已搜索過(guò)的結(jié)點(diǎn),稱(chēng)為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ì)與分析分支限界法求單源最短路徑單源最短路徑問(wèn)題的評(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)度來(lái)替代。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ù)問(wèn)題中f(d)只是個(gè)估計(jì)值,所以單靠f(d)是不夠的。通常還要設(shè)計(jì)它的上下界函數(shù)U(d)和L(d)。L(d)≤f(d)≤U(d)。所謂分支限界法就是通過(guò)評(píng)價(jià)函數(shù)及其上下界函數(shù)的計(jì)算,將狀態(tài)空間中不可能產(chǎn)生最佳解的子樹(shù)剪去,減少搜索的范圍,提高效率。因而更準(zhǔn)確的稱(chēng)呼應(yīng)是“界限剪支法”2023/2/48計(jì)算機(jī)算法設(shè)計(jì)與分析用分支限界法求TSPTSP是求排列的問(wèn)題,不是僅找一條路徑而已。因而需要對(duì)分支限界法的一般算法作些修改:(1)待擴(kuò)展的結(jié)點(diǎn)如果在本路徑上已經(jīng)出現(xiàn),則不再擴(kuò)展,但若是在其他路徑上出現(xiàn)過(guò),則仍需要擴(kuò)展。(2)新結(jié)點(diǎn),無(wú)論其優(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?!?5403127
5∞1730251915∞61
95024∞6228710∞評(píng)價(jià)函數(shù)f(d)為1到d的代價(jià)減去已經(jīng)過(guò)的邊數(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問(wèn)題的更好的評(píng)價(jià)函數(shù),先定義其代價(jià)矩陣的歸約矩陣和約數(shù)。給定代價(jià)矩陣C,從C的任何行i(或列i)的各元素中減去此行(或此列)的最小元素的值r(i)(或r’(i)),稱(chēng)為對(duì)i行(或i列)的歸約。將C的各行和各列都?xì)w約后的矩陣稱(chēng)為C的歸約矩陣。和數(shù)r=∑i≤nr(i)+∑i≤nr’(i)
稱(chēng)為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ù)來(lái)定義期望函數(shù)h(d):對(duì)開(kāi)始結(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開(kāi)始的路線的下界r2。是否可用類(lèi)似求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類(lèi)似地可求出f(4)=51。515類(lèi)似地可求出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類(lèi)似地計(jì)算出f(3)=68684類(lèi)似地計(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?!蕖蕖蕖?h(4)=12,于是f(4)=64+12=7676對(duì)結(jié)點(diǎn)5,g(5)=62+0=62?!蕖?/p>
∞
∞
∞∞∞∞
∞
∞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ù)值均超過(guò)上界,因而不再需要擴(kuò)展了。××××××××××于是找到了一條最短的周游路線:1→2→3→5→4→1。2023/2/419計(jì)算機(jī)算法設(shè)計(jì)與分析分支邊與二叉樹(shù)在構(gòu)造求TSP的搜索樹(shù)時(shí),還有另外一種算法稍有點(diǎn)不同,就是將搜索樹(shù)構(gòu)造成二叉樹(shù)。給定一條最短周游路線P,對(duì)于任一條邊<i,j>只有兩種情況,即<i,j>P或者<i,j>P。這就可以表示成右邊的二叉樹(shù):km<i,j>n____<i,j>其中____<i,j>表示<i,j>P。這樣的邊稱(chēng)為分支邊。2023/2/420計(jì)算機(jī)算法設(shè)計(jì)與分析用二叉樹(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é)點(diǎn)16給出了一條最短周游路線:1→2→3→5→4→12023/2/421計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的效率從TSP問(wèn)題的計(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ù)雜性上沒(méi)有本質(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上的搜索。而反過(guò)來(lái),在有向圖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};
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年慶陽(yáng)如何考貨運(yùn)從業(yè)資格證
- 2025年?yáng)|莞道路運(yùn)輸從業(yè)資格證考試
- 2025年西藏貨運(yùn)從業(yè)資格考試題目
- 叉車(chē)應(yīng)急事故現(xiàn)場(chǎng)演練
- 手術(shù)室放射防護(hù)培訓(xùn)
- 停車(chē)場(chǎng)操作規(guī)范樣本
- 2024年浙江省中考語(yǔ)文真題卷及答案解析
- 軟件開(kāi)發(fā)服務(wù)合作合同管理要點(diǎn)
- 商業(yè)步行街廣告位租賃協(xié)議
- 博物館門(mén)窗維護(hù)服務(wù)協(xié)議
- 危重患者氣道管理
- 探索·鄱陽(yáng)湖智慧樹(shù)知到期末考試答案章節(jié)答案2024年江西師范大學(xué)
- 2024年天津城市運(yùn)營(yíng)發(fā)展有限公司招聘筆試沖刺題(帶答案解析)
- 班級(jí)預(yù)防校園欺凌排查表
- B737NG 機(jī)型執(zhí)照試題集
- 手術(shù)室組長(zhǎng)競(jìng)聘演講
- 高中體育-籃球-單手肩上投籃教學(xué)設(shè)計(jì)學(xué)情分析教材分析課后反思
- 中國(guó)腫瘤整合診治指南(CACA)-胃癌智慧樹(shù)知到期末考試答案章節(jié)答案2024年溫州醫(yī)科大學(xué)
- 市場(chǎng)營(yíng)銷(xiāo)學(xué)實(shí)踐總結(jié)
- HG-T 2737-2023 非金屬化工設(shè)備 丙烯腈-丁二烯-苯乙烯、聚氯乙烯、均聚聚丙烯、聚偏氟乙烯和玻璃纖維增強(qiáng)聚丙烯球閥
- 關(guān)于ESG體系相關(guān)研究的文獻(xiàn)綜述
評(píng)論
0/150
提交評(píng)論