算法設(shè)計(jì)與分析 課件 8.4-分支限界 - 典型應(yīng)用 - 旅行售貨員問題

算法設(shè)計(jì)與分析分支限界—旅行售貨員問題信息工程大學(xué)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版問題描述：某售貨員要到若干城市去推銷商品，已知各城市之間的路程（或旅費(fèi)）。他要選定一條從駐地出發(fā)，經(jīng)過每個(gè)城市一遍，最后回到駐地的路線，使得總的路程（或總旅費(fèi)）最小。問題抽象：設(shè)G=(V,E)是一個(gè)帶權(quán)圖。圖中各邊的權(quán)值為正數(shù)。圖中一條周游路線是包括V中每個(gè)頂點(diǎn)在內(nèi)的一條回路。周游路線的費(fèi)用是這條回路上所有邊的權(quán)值之和。旅行售貨員問題就是要在圖G中找出費(fèi)用最小的回路。1243302010654實(shí)例分析：

優(yōu)先隊(duì)列：

小根堆，用于表示活結(jié)點(diǎn)優(yōu)先隊(duì)列

優(yōu)先級(jí)=下界lcostlcost=cc+頂點(diǎn)的最小費(fèi)用出邊和(未來最小的花費(fèi))12433020106544+5+5+4=180,0,18B4I2,26,9BCDEC21,30,14bestc：bestx：∞C3D1,6,14DCE41,4,141243302010645EDCEDCJ2J2,14,10DJCK3K2,24,10DJKCHH22,11,925DJKCHJKCIHJKICHJKIC4N3,25,0NJNKICH為n-2層結(jié)點(diǎn)18=4+5+5+414=5+5+4擴(kuò)展結(jié)點(diǎn)活結(jié)點(diǎn)優(yōu)先隊(duì)列最優(yōu)解樹中結(jié)點(diǎn)的信息：結(jié)點(diǎn)深度，已花費(fèi)代價(jià)，未來花費(fèi)代價(jià)的下界NICJNKIC0,0,18B4I2,26,9C21,30,14bestc：bestx：3D1,6,14E41,4,142J2,14,103K2,24,10H22,11,9251,3,2,4H4N3,25,0NJ3P3,25,0PNICN為葉子，結(jié)束擴(kuò)展結(jié)點(diǎn)活結(jié)點(diǎn)優(yōu)先隊(duì)列最優(yōu)解1243302010645樹中結(jié)點(diǎn)的信息：結(jié)點(diǎn)深度，已花費(fèi)代價(jià)，未來花費(fèi)代價(jià)的下界輸入：圖結(jié)點(diǎn)數(shù)n，圖鄰接矩陣a[][]輸出：最優(yōu)值bestc，最優(yōu)解v[]1BBTSP(){2若圖中存在沒有出邊的結(jié)點(diǎn)，則退出;3計(jì)算各頂點(diǎn)最小出邊和MinSum;4定義最優(yōu)值bestc=∞;5創(chuàng)建根結(jié)點(diǎn)E,令其s=0,cc=0,lcost=cc+MinSum,6x={1,2,…,n};7while(E不是葉結(jié)點(diǎn)){//遇到葉子時(shí)結(jié)束8

if(E是葉子的父結(jié)點(diǎn)){//E的層次為n-29c=E->cc+a[E->x[n-2]][E->x[n-1]]+10a[E->x[n-1]][1];11if(c<bestc){12bestc=c;改造E為擴(kuò)展的葉結(jié)點(diǎn),13E->s++,E->cc=bestc;E入隊(duì);14}15else釋放E;16}17else{//擴(kuò)展E的兒子結(jié)點(diǎn)18

for(i=E->s+1;i<=n-1;i++){19cc=E->cc+a[E->x[E->s]][E->x[i]];20lcost=cc+E->lcost-MinOut[E->x[E->s]];21if(lcost<bestc){22申請(qǐng)結(jié)點(diǎn)N;把E中x復(fù)制到N;23N->s=E->s+1;交換N->x[N->s]與N->x[i];

24N->cc=cc;N->lcost=lcost;25N入隊(duì);}26}27釋放E;28}29從隊(duì)列取下一個(gè)擴(kuò)展結(jié)點(diǎn)E;30if(E不存在)break;31}32if(bestc==∞)return∞;//無回路33從E中復(fù)制x到解v中；34釋放E及優(yōu)先隊(duì)列中剩余結(jié)點(diǎn);35returnbestc;}測(cè)試填空題：針對(duì)上述