分支限界法實(shí)現(xiàn)單源最短路徑

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

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告分支限界法實(shí)現(xiàn)單源最短路徑班級(jí)：11計(jì)算機(jī)1學(xué)號(hào)：110104200109姓名：金李揚(yáng)日期：5.221.問(wèn)題描述以分支限界法實(shí)現(xiàn)單源最短路徑1.以分支限界實(shí)現(xiàn)優(yōu)先隊(duì)列2.再以分支限界法的優(yōu)先隊(duì)列實(shí)現(xiàn)單元最短路徑以該圖為算法測(cè)試數(shù)據(jù)，獲得鏈接矩陣如下：以-1代表無(wú)法到達(dá)的點(diǎn)-1234-1-1-1-1-1-1-1-1-13-172-1-1-1-1-1-1-1-1-1-192-1-1-1-1-1-1-1-1-1-12-1-1-1-1-1-1-1-1-1-1-133-1-1-1-1-1-1-1-11-13-1-1-1-1-1-1-1-1-1-151-1-1-1-1-1-1

2、-1-1-1-1-13-1-1-1-1-1-1-1-1-1-13-1-1-1-1-1-1-1-1-1-12-1-1-1-1-1-1-1-1-1-1-12.算法思想分支限界法基本思想：分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(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í)為止。算法步驟1.用

3、一極小堆來(lái)存儲(chǔ)活結(jié)點(diǎn)表，其優(yōu)先級(jí)是結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。2.算法從圖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到頂點(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í)為止。剪枝函數(shù)1.在算法擴(kuò)展結(jié)點(diǎn)的過(guò)程中，一旦發(fā)現(xiàn)一個(gè)結(jié)點(diǎn)的下界不小于當(dāng)前找到的最短路長(zhǎng)，則算法剪去以該結(jié)點(diǎn)為根的子樹(shù)。2.在算法中，利用結(jié)點(diǎn)間的

4、控制關(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ù)剪去。3.算法設(shè)計(jì)1.定義HEAPNODE結(jié)構(gòu)體：typedefstructHeapNode{intleft,right;intweight;boolfriendoperator<(constHeapNode&a,constHeapNode&b){returna.weight>b.weight;}inti,length;HeapNode(){}HeapNode(intii,intl){i=ii;length=l;}};2.以堆實(shí)現(xiàn)優(yōu)先隊(duì)列類：#de

5、fineMAXN25500classpriority_queue{private:HeapNoder[MAXN];intlength;voidheap_adjust(ints,intm){HeapNoderc=r[s];for(intj=s<<1;j<=m;j<<=1){if(j

6、){for(inti=length>>1;i>0;i--){heap_adjust(i,length);}}voidset_size(intlength){this->length=length;}voidset_value(intid,HeapNodevalue){r[id]=value;}voidheap_sort(){for(inti=length;i>1;i--){HeapNodetmp=r[1];r[1]=r[i];r[i]=tmp;heap_adjust(1,i-1);}}boolis_heap(){intlen=length>>1-1,j;if(len<1){if(len

7、gth==1

8、

9、(!(r[1]