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

ID:9878720

大?。?3.50 KB

頁數(shù):9頁

時間:2018-05-13

分支限界法實現(xiàn)單源最短路徑_第1頁
分支限界法實現(xiàn)單源最短路徑_第2頁
分支限界法實現(xiàn)單源最短路徑_第3頁
分支限界法實現(xiàn)單源最短路徑_第4頁
分支限界法實現(xiàn)單源最短路徑_第5頁
資源描述:

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

1、算法分析與設(shè)計實驗報告分支限界法實現(xiàn)單源最短路徑班級:11計算機1學(xué)號:110104200109姓名:金李揚日期:5.221.問題描述以分支限界法實現(xiàn)單源最短路徑1.以分支限界實現(xiàn)優(yōu)先隊列2.再以分支限界法的優(yōu)先隊列實現(xiàn)單元最短路徑以該圖為算法測試數(shù)據(jù),獲得鏈接矩陣如下:以-1代表無法到達(dá)的點-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)先或以最小耗費(最大效益)優(yōu)先的方式搜索問題的解空間樹。在分支限界法中,每一個活結(jié)點只有一次機會成為擴展結(jié)點。活結(jié)點一旦成為擴展結(jié)點,就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中,導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄,其余兒子結(jié)點被加入活結(jié)點表中。此后,從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴展結(jié)點,并重復(fù)上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。算法步驟1.用

3、一極小堆來存儲活結(jié)點表,其優(yōu)先級是結(jié)點所對應(yīng)的當(dāng)前路長。2.算法從圖G的源頂點s和空優(yōu)先隊列開始。結(jié)點s被擴展后,它的兒子結(jié)點被依次插入堆中。此后,算法從堆中取出具有最小當(dāng)前路長的結(jié)點作為當(dāng)前擴展結(jié)點,并依次檢查與當(dāng)前擴展結(jié)點相鄰的所有頂點。如果從當(dāng)前擴展結(jié)點i到頂點j有邊可達(dá),且從源出發(fā),途經(jīng)頂點i再到頂點j的所相應(yīng)的路徑的長度小于當(dāng)前最優(yōu)路徑長度,則將該頂點作為活結(jié)點插入到活結(jié)點優(yōu)先隊列中。這個結(jié)點的擴展過程一直繼續(xù)到活結(jié)點優(yōu)先隊列為空時為止。剪枝函數(shù)1.在算法擴展結(jié)點的過程中,一旦發(fā)現(xiàn)一個結(jié)點的下界不小于當(dāng)前找到的最短路長,則算法剪去以該結(jié)點為根的子樹。2.在算法中,利用結(jié)點間的

4、控制關(guān)系進(jìn)行剪枝。從源頂點s出發(fā),2條不同路徑到達(dá)圖G的同一頂點。由于兩條路徑的路長不同,因此可以將路長長的路徑所對應(yīng)的樹中的結(jié)點為根的子樹剪去。3.算法設(shè)計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.以堆實現(xiàn)優(yōu)先隊列類:#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]

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭