第6章分支界限法

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

分支限界法2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析2分支限界法的求解目標(biāo)分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解空間樹(shù)T中滿(mǎn)足約束條件的所有解。分支限界法的求解目標(biāo)則是找出滿(mǎn)足約束條件的一個(gè)解，或是在滿(mǎn)足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析3分支限界法與回溯法的不同由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法有兩點(diǎn)不同：①回溯法只通過(guò)約束條件剪去非可行解，而分支限界法不僅通過(guò)約束條件，而且通過(guò)目標(biāo)函數(shù)的限界來(lái)減少無(wú)效搜索，也就是剪掉了某些不包含最優(yōu)解的可行解。②在解空間樹(shù)上的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹(shù)，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析4分支限界法是最佳優(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/1計(jì)算機(jī)算法設(shè)計(jì)與分析5評(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/1計(jì)算機(jī)算法設(shè)計(jì)與分析6搜索路徑的構(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/1計(jì)算機(jī)算法設(shè)計(jì)與分析7分支限界法的一般算法⑴計(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/1計(jì)算機(jī)算法設(shè)計(jì)與分析8分支限界法求單源最短路徑單源最短路徑問(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/1計(jì)算機(jī)算法設(shè)計(jì)與分析9分支限界法求最短路徑舉例12543102050100301060賦權(quán)圖G初始時(shí)，將源[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中已有的兩個(gè)結(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ì)算機(jī)算法設(shè)計(jì)與分析1015迷問(wèn)題在一個(gè)4×4的方格棋盤(pán)上，放著15個(gè)數(shù)字1,2,…,15，每個(gè)數(shù)字占一格，空出一格，要求通過(guò)盡量少次移動(dòng)格中的數(shù)字，將一個(gè)給定的初態(tài)變成目標(biāo)狀態(tài)。移動(dòng)的規(guī)則是：每次只能在空格的上下左右4個(gè)位置任選一個(gè)移入空格。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析11問(wèn)題分析對(duì)任意給定的初態(tài)，狀態(tài)不再現(xiàn)的各種可能的移動(dòng)，將產(chǎn)生多達(dá)16！種不同的狀態(tài)，而且其中只有一個(gè)狀態(tài)是目標(biāo)狀態(tài)。在狀態(tài)空間樹(shù)中，用空格的移動(dòng)來(lái)代表數(shù)字的相應(yīng)的移動(dòng)。結(jié)點(diǎn)d的一個(gè)兒子結(jié)點(diǎn)代表了從狀態(tài)d經(jīng)過(guò)一次合法的移動(dòng)所到達(dá)的狀態(tài)。用回溯法肯定可以找到所求的最優(yōu)解，但比較盲目。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析12構(gòu)造15迷問(wèn)題的評(píng)價(jià)函數(shù)評(píng)價(jià)函數(shù)f(d)=g(d)+h(d)，其中：⑴從開(kāi)始結(jié)點(diǎn)到結(jié)點(diǎn)d的已有耗損值g(d)，在此就設(shè)為從根到結(jié)點(diǎn)d的路徑長(zhǎng)。⑵從結(jié)點(diǎn)d到達(dá)目標(biāo)的期望耗損值h(d)。在此可設(shè)為15個(gè)數(shù)字中還沒(méi)有到達(dá)相應(yīng)目標(biāo)位置的數(shù)字的個(gè)數(shù)。搜索過(guò)程見(jiàn)圖6.22023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析131+41+41+21+42+12+32+33+23+02023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析14界限(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/1計(jì)算機(jī)算法設(shè)計(jì)與分析15界限剪枝法求0-1背包問(wèn)題在回溯法中的“剪枝”：通過(guò)“物品總重量不能大于背包容量”這一約束條件將非可行解剪去。界限剪枝法中的“剪枝”：通過(guò)構(gòu)造更加嚴(yán)格的約束條件（即限界函數(shù)）將一些非最優(yōu)解的可行解分支也剪去，從而大大減少搜索空間。限界函數(shù)如何構(gòu)造呢？2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析160-1背包問(wèn)題的限界函數(shù)評(píng)價(jià)函數(shù)f(d)=背包中已經(jīng)裝載的物品價(jià)值限界函數(shù)u(d)=當(dāng)前已經(jīng)找到的最好的可行解的值-（背包中已經(jīng)裝載的物品價(jià)值+剩余可選擇物品的總價(jià)值）若u(d)>0，則說(shuō)明即使把剩余的所有物品都裝入背包也不可能得到更優(yōu)的可行解，所以無(wú)須擴(kuò)展該結(jié)點(diǎn)，可以剪枝。算法請(qǐng)自行完成2023年2月1日17分支限界法的基本思想分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(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ò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。2023年2月1日18常見(jiàn)的兩種分支限界法從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式導(dǎo)致不同的分支限界法：隊(duì)列式(FIFO)分支限界法：將活結(jié)點(diǎn)表組織成一個(gè)隊(duì)列，按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。優(yōu)先隊(duì)列式分支限界法：將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先隊(duì)列，按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。最大優(yōu)先隊(duì)列：使用最大堆，體現(xiàn)最大效益優(yōu)先最小優(yōu)先隊(duì)列：使用最小堆，體現(xiàn)最小費(fèi)用優(yōu)先2023年2月1日19

隊(duì)列式分支限界法的搜索解空間樹(shù)的方式類(lèi)似于解空間樹(shù)的寬度優(yōu)先搜索，不同的是隊(duì)列式分支限界法不搜索以不可行結(jié)點(diǎn)（已經(jīng)被判定不能導(dǎo)致可行解或不能導(dǎo)致最優(yōu)解的結(jié)點(diǎn)）為根的子樹(shù)。這是因?yàn)?，按照?guī)則，這樣的結(jié)點(diǎn)未被列入活結(jié)點(diǎn)表。2023年2月1日20優(yōu)先隊(duì)列式分支限界法的搜索方式是根據(jù)活結(jié)點(diǎn)的優(yōu)先級(jí)確定下一個(gè)擴(kuò)展結(jié)點(diǎn)。結(jié)點(diǎn)的優(yōu)先級(jí)常用一個(gè)與該結(jié)點(diǎn)有關(guān)的評(píng)價(jià)函數(shù)值f(d)來(lái)表示。最大優(yōu)先隊(duì)列規(guī)定f(d)值較大的結(jié)點(diǎn)的優(yōu)先級(jí)較高。在算法實(shí)現(xiàn)時(shí)通常用一個(gè)最大堆來(lái)實(shí)現(xiàn)最大優(yōu)先隊(duì)列，用最大堆的Deletemax運(yùn)算抽取堆中的下一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，體現(xiàn)最大效益優(yōu)先的原則。類(lèi)似地，最小優(yōu)先隊(duì)列規(guī)定f(d)值較小的結(jié)點(diǎn)的優(yōu)先級(jí)較高。在算法實(shí)現(xiàn)時(shí)，常用一個(gè)最小堆來(lái)實(shí)現(xiàn)，用最小堆的Deletemin運(yùn)算抽取堆中下一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，體現(xiàn)最小耗費(fèi)優(yōu)先的原則。如何確定合適的評(píng)價(jià)函數(shù)好的評(píng)價(jià)函數(shù)不僅計(jì)算簡(jiǎn)單，還要保證最優(yōu)解在搜索空間中，更重要的是能在搜索的早期對(duì)超出目標(biāo)函數(shù)界的結(jié)點(diǎn)進(jìn)行丟棄，減少搜索空間，從而盡快找到問(wèn)題的最優(yōu)解。2023年2月1日212023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析22用分支限界法求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/1計(jì)算機(jī)算法設(shè)計(jì)與分析23分支限界法求排列⑴計(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/1計(jì)算機(jī)算法設(shè)計(jì)與分析24分支限界法求TSP舉例設(shè)有向圖G=(V,E)的邊的代價(jià)矩陣為C=[cij]。若不存在有向邊<i,j>∈E，則定義cij=∞且規(guī)定cii=∞。不失一般性，設(shè)周游路線(xiàn)均以頂點(diǎn)1為起點(diǎn)。左下為一個(gè)有向圖G的代價(jià)矩陣C?！?54031275∞1730251915∞6195024∞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/1計(jì)算機(jī)算法設(shè)計(jì)與分析25分支限界法求TSP的搜索∞254031275∞1730251915∞6195024∞6228710∞102243394305262340453548523333243542793535453246437234946242843584286找到了第一條周游路線(xiàn)1→5→3→4→2→1，其長(zhǎng)度為95。這不是最短周游路線(xiàn)，需要修改上界后繼續(xù)搜索。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析26歸約矩陣以及約數(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/1計(jì)算機(jī)算法設(shè)計(jì)與分析27例子中的歸約矩陣和約數(shù)計(jì)算前面例子中的歸約矩陣及其約數(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ì)算機(jī)算法設(shè)計(jì)與分析28約數(shù)是周游路線(xiàn)長(zhǎng)度的下界定理：設(shè)C是圖G的代價(jià)矩陣，P是周游路線(xiàn)，則P的代價(jià)，即∑<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)。任何周游路線(xiàn)包含n條邊并且對(duì)應(yīng)在C中的每行每列有且僅有一條邊。于是∑<i,j>∈Pcij=∑<i,j>∈P(c’ij+r(i)+r’(j))。r+∑<i,j>∈Pc’ij。

2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析29定義期望函數(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)始的路線(xiàn)的下界r2。是否也可用類(lèi)似求r一樣去求新的約數(shù)r2呢？可以，但在此之前應(yīng)將邊<1,2>和所有邊<1,k>和邊<k,2>都刪去，即置c’12、c’1k和c’k2為∞。設(shè)C’p為某路線(xiàn)上結(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。令f(1)=

g(1)+

h(1)，其中g(shù)(1)=0，h(1)=r。對(duì)任意路線(xiàn)上的結(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ì)算機(jī)算法設(shè)計(jì)與分析30用新的評(píng)價(jià)函數(shù)求TSP下面用新的評(píng)價(jià)函數(shù)求前面的例子，我們已經(jīng)求得了它的歸約矩陣C’和約數(shù)r=47?！?15320∞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類(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?！蕖蕖蕖蕖?∞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∞∞200∞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∞∞200∞∞∞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)，找到了第一條路線(xiàn)。4這條路線(xiàn)的長(zhǎng)度為62，以其為上界。其余未擴(kuò)展的結(jié)點(diǎn)的評(píng)價(jià)函數(shù)值均超過(guò)上界，因而不再需要擴(kuò)展了。××××××××××于是找到了一條最短的周游路線(xiàn)：1→2→3→5→4→1。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析31分支邊與二叉樹(shù)在構(gòu)造求TSP的搜索樹(shù)時(shí)，還有另外一種算法稍有點(diǎn)不同，就是將搜索樹(shù)構(gòu)造成二叉樹(shù)。給定一條最短周游路線(xiàn)P，對(duì)于任一條邊<i,j>只有兩種情況，即<i,j>P或者<i,j>P。這就可以表示成右邊的二叉樹(shù)：km<i,j>n____<i,