單源最短路徑1 分支限界

《單源最短路徑1 分支限界》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、一、實(shí)驗(yàn)名稱：?jiǎn)卧醋疃搪窂絾?wèn)題?時(shí)間：X年X月X日，星期3，第三、四節(jié)?地點(diǎn)：0#601?二、實(shí)驗(yàn)?zāi)康募耙?1、掌握分支限界法解題步驟：?1在問(wèn)題的邊帶權(quán)的解空間樹(shù)中進(jìn)行廣度優(yōu)先搜索??2找一個(gè)葉結(jié)點(diǎn)使其對(duì)應(yīng)路徑的權(quán)最小(最大)?3當(dāng)搜索到達(dá)一個(gè)擴(kuò)展結(jié)點(diǎn)時(shí),一次性擴(kuò)展它的所有兒子?4將滿足約束條件且最小耗費(fèi)函數(shù)￡目標(biāo)函數(shù)限界的兒子,插入活結(jié)點(diǎn)???表中?5從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)同樣擴(kuò)展直到找到所需的解或活動(dòng)結(jié)點(diǎn)表???為空為止?三、實(shí)驗(yàn)環(huán)境?Window下的vs2010?四、實(shí)驗(yàn)內(nèi)容?單源最短路徑問(wèn)題?以一個(gè)例子來(lái)說(shuō)明單源最短路徑問(wèn)題：在下圖所給的有向圖G

2、中，每一邊都有一個(gè)非負(fù)邊權(quán)。?求圖G的從源頂點(diǎn)s到目標(biāo)頂點(diǎn)t之間的最短路徑?五、算法描述及實(shí)驗(yàn)步驟??算法思想：解單源最短路徑問(wèn)題的優(yōu)先隊(duì)列式分支限界法用一極小堆來(lái)存儲(chǔ)活結(jié)點(diǎn)表。其優(yōu)先級(jí)是結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。??算法從圖G的源頂點(diǎn)s和空優(yōu)先隊(duì)列開(kāi)始。結(jié)點(diǎn)s被擴(kuò)展后，它的兒子結(jié)點(diǎn)被依次插入堆中。?算法每次從堆中取出具有最小當(dāng)前路長(zhǎng)的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并依次檢查與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰的所有頂點(diǎn)。?如果從當(dāng)前擴(kuò)展結(jié)點(diǎn)i到j(luò)有邊可達(dá)，且從源出發(fā)，途經(jīng)i再到j(luò)的所相應(yīng)路徑長(zhǎng)度，小于當(dāng)前最優(yōu)路徑長(zhǎng)度，則將該頂點(diǎn)作為活結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。?結(jié)點(diǎn)擴(kuò)展過(guò)程一直繼續(xù)到

3、活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止二．單源最短路徑問(wèn)題?1.問(wèn)題描述?下面以一個(gè)例子來(lái)說(shuō)明單源最短路徑問(wèn)題：在下圖所給的有向圖G中，每一邊都有一個(gè)非負(fù)邊權(quán)。要求圖G的從源頂點(diǎn)s到目標(biāo)頂點(diǎn)t之間的最短路徑。下圖是用優(yōu)先隊(duì)列式分支限界法解有向圖G的單源最短路徑問(wèn)題產(chǎn)生的解空間樹(shù)。其中，每一個(gè)結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。2.?算法思想?解單源最短路徑問(wèn)題的優(yōu)先隊(duì)列式分支限界法用一極小堆來(lái)存儲(chǔ)活結(jié)點(diǎn)表。其優(yōu)先級(jí)是結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。算法從圖G的源頂點(diǎn)s和空優(yōu)先隊(duì)列開(kāi)始。結(jié)點(diǎn)s被擴(kuò)展后，它的兒子結(jié)點(diǎn)被依次插入堆中。此后，算法從堆中取出具有最小當(dāng)前路長(zhǎng)的結(jié)點(diǎn)作為當(dāng)

4、前擴(kuò)展結(jié)點(diǎn)，并依次檢查與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰的所有頂點(diǎn)。如果從當(dāng)前擴(kuò)展結(jié)點(diǎn)i到頂點(diǎn)j有邊可達(dá)，且從源出發(fā)，途經(jīng)頂點(diǎn)i再到頂點(diǎn)j的所相應(yīng)的路徑的長(zhǎng)度小于當(dāng)前最優(yōu)路徑長(zhǎng)度，則將該頂點(diǎn)作為活結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。?這個(gè)結(jié)點(diǎn)的擴(kuò)展過(guò)程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止。3.?剪枝策略???在算法擴(kuò)展結(jié)點(diǎn)的過(guò)程中，一旦發(fā)現(xiàn)一個(gè)結(jié)點(diǎn)的下界不小于當(dāng)前找到的最短路長(zhǎng)，則算法剪去以該結(jié)點(diǎn)為根的子樹(shù)。??????在算法中，利用結(jié)點(diǎn)間的控制關(guān)系進(jìn)行剪枝。從源頂點(diǎn)s出發(fā)，2條不同路徑到達(dá)圖G的同一頂點(diǎn)。由于兩條路徑的路長(zhǎng)不同，因此可以將路長(zhǎng)長(zhǎng)的路徑所對(duì)應(yīng)的樹(shù)中的結(jié)點(diǎn)為根的子樹(shù)剪去

5、。???下圖是用優(yōu)先隊(duì)列式分支限界法解有向圖G的單源最短路徑問(wèn)題產(chǎn)生的解空間樹(shù)的剪枝情況。三．程序設(shè)計(jì)：#includeusingnamespacestd;constintsize=100;constintinf=5000;//兩點(diǎn)距離上界//第一組測(cè)試參數(shù)constintn=6;//圖頂點(diǎn)個(gè)數(shù)加1intprev[n];//圖的前驅(qū)頂點(diǎn)intdist[]={0,0,5000,5000,5000,5000};//最短距離數(shù)組intc[n][n]={{0,0,0,0,0,0},{0,0,2,3,5000,5000},//圖的鄰接矩陣{0,50

6、00,0,1,2,5000},{0,5000,5000,0,9,2},{0,5000,5000,5000,0,2},{0,5000,5000,5000,5000,0}};/*第二組測(cè)試參數(shù)constintn=5;//圖頂點(diǎn)個(gè)數(shù)加1intprev[n];//圖的前驅(qū)頂點(diǎn)intdist[]={0,0,5000,5000,5000};intc[][n]={{0,0,0,0,0},{0,0,2,3,5000},{0,5000,0,1,2},{0,5000,5000,0,9},{0,5000,5000,5000,0}};*/classMinHeapNode{publi

7、c:inti;//頂點(diǎn)編號(hào)intlength;//當(dāng)前路長(zhǎng)};//循環(huán)隊(duì)列classCirQueue{private:intfront,rear;MinHeapNodedata[size];public:CirQueue(){front=rear=0;}//元素入隊(duì)操作voidqueryIn(MinHeapNodee){if((rear+1)%size!=front){rear=(rear+1)%size;//隊(duì)尾指針在循環(huán)意義下加1data[rear]=e;//在隊(duì)尾插入元素}}//元素出隊(duì)操作MinHeapNodequeryOut(){if(rear!=

8、front){front=(front+1)%siz