單源最短路徑分支限界

1、一、實(shí)驗(yàn)名稱：?jiǎn)卧醋疃搪窂絾栴}時(shí)間：X年X月X日，星期3,第三、四節(jié)地點(diǎn)：0#601二、實(shí)驗(yàn)?zāi)康募耙?、掌握分支限界法解題步驟：1在問題的邊帶權(quán)的解空間樹中進(jìn)行廣度優(yōu)先搜索2找一個(gè)葉結(jié)點(diǎn)使其對(duì)應(yīng)路徑的權(quán)最?。ㄗ畲螅?當(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)容單源最短路徑問題以一個(gè)例子來說明單源最短路徑問題：在下圖所給的有向圖G中，每一邊都有一個(gè)非負(fù)邊權(quán)。五、算法描述及實(shí)驗(yàn)步驟 算法思想：其優(yōu)先級(jí)是結(jié)點(diǎn)

2、解單源最短路徑問題的優(yōu)先隊(duì)列式分支限界法用一極小堆來存儲(chǔ)活結(jié)點(diǎn)表。 所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。算法從圖G的源頂點(diǎn)s和空優(yōu)先隊(duì)列開始。結(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ò)展過程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止二單源最短路徑問題1問題描述下面以一個(gè)例子來說明單源最短路徑問題：在下圖所給的有向圖G中，每一邊都有一個(gè)非負(fù)邊權(quán)。要求圖 G的從源頂點(diǎn)s到目

3、標(biāo)頂點(diǎn)t之間的最短路徑。下圖是用優(yōu)先隊(duì)列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中,每一個(gè)結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。Ca324eh55,126gm567107r1172. 算法思想解單源最短路徑問題的優(yōu)先隊(duì)列式分支限界法用一極小堆來存儲(chǔ)活結(jié)點(diǎn)表。其優(yōu)先級(jí)是 結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。算法從圖G的源頂點(diǎn)s和空優(yōu)先隊(duì)列開始。結(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)前最

4、優(yōu)路徑長(zhǎng)度，則將該頂點(diǎn)作為活結(jié)點(diǎn)插 入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。這個(gè)結(jié)點(diǎn)的擴(kuò)展過程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止。3. 剪枝策略在算法擴(kuò)展結(jié)點(diǎn)的過程中，一旦發(fā)現(xiàn)一個(gè)結(jié)點(diǎn)的下界不小于當(dāng)前找到的最短路長(zhǎng)，則算法剪去以該結(jié)點(diǎn)為根的子樹。在算法中，利用結(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)的樹中的結(jié)點(diǎn)為根的子樹剪去。下圖是用優(yōu)先隊(duì)列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹的剪枝情況。經(jīng)過不同 的路徑到 達(dá)相同的三.程序設(shè)計(jì)：#in clude<iostream>using n amespa

5、ce std;const int size = 100;con st int inf = 5000;/ 兩點(diǎn)距離上界/第一組測(cè)試參數(shù)const int n = 6;/圖頂點(diǎn)個(gè)數(shù)加 1int prevn;/圖的前驅(qū)頂點(diǎn)int dist = 0,0,5000,5000,5000,5000;/最短距離數(shù)組int cnn = 0,0,0,0,0,0,0,0,2,3,5000,5000,/ 圖的鄰接矩陣0,5000,0,1,2,5000,0,5000,5000,0,9,2, 0,5000,5000,5000,0,2,0,5000,5000,5000,5000,0;/* 第二組測(cè)試參數(shù)const int

6、n = 5; /圖頂點(diǎn)個(gè)數(shù)加 1int prevn; / 圖的前驅(qū)頂點(diǎn)int dist = 0,0,5000,5000,5000;int cn=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 ;*/class MinHeapNodepublic :int i;/ 頂點(diǎn)編號(hào)int length; / 當(dāng)前路長(zhǎng);/循環(huán)隊(duì)列class CirQueueprivate:int front,rear;MinHeapNode datasize; public:CirQueue()front = rear = 0;

7、/元素入隊(duì)操作void queryIn(MinHeapNode e)if(rear +1)%size != front)rear = (rear+1)%size; / 隊(duì)尾指針在循環(huán)意義下加 1 datarear = e; / 在隊(duì)尾插入元素/元素出隊(duì)操作MinHeapNode queryOut()if(rear != front)front = (front+1)%size; / 隊(duì)列在循環(huán)意義下加 1 return datafront;/讀取隊(duì)頭元素，但不出隊(duì)MinHeapNode getQuery()if(rear != front)return data(front+1)%size;/

8、判斷隊(duì)列是否為空bool empty()return front = rear;/判斷隊(duì)列是否為滿bool full()return (rear +1)%size = front;/CirQueue 結(jié)束/圖的表示class Graphpublic:/單源最短路徑問題的優(yōu)先隊(duì)列式分支限界法void shortestPath(int v)/ 創(chuàng)建隊(duì)列CirQueue qq;/定義源為初始擴(kuò)展結(jié)點(diǎn)MinHeapNode e;e.i = v;e.length = 0;distv = 0;qq.queryIn(e);/搜索問題的解空間while(true)for(int j = 1;j<n;j+

9、)if(j>=n)break;MinHeapNode m = qq.getQuery();if(cm.ij<inf)&&(m.length + cm.ij < distj)/頂點(diǎn)i到頂點(diǎn)j可達(dá)，且滿足控制約束distj = m.length + cm.ij;prevj = m.i;/加入活結(jié)點(diǎn)優(yōu)先隊(duì)列MinHeapNode mi;mi.i = j;mi.length = distj;if(qq.full()break;qq.queryIn(mi);/元素入隊(duì)/for 循環(huán)結(jié)束if(qq.empty()break;qq.queryOut(); /當(dāng)該結(jié)點(diǎn)的孩子結(jié)

10、點(diǎn)全部入隊(duì)后，刪除該結(jié)點(diǎn)/while 循環(huán)結(jié)束/ 方法結(jié)束;/ 類結(jié)束int main()Graph g;g.shortestPath(1);cout<<" 最短路徑長(zhǎng)為"<<distn-1<<endl;cout<<" 中間路徑為："for(int i =3;i<n;i+)cout<<previ<<" "cout<<endl<<"歡迎使用本系統(tǒng)"<<endl; return 0;contInue'C:Prcgram Files (x86)Microsoft Visual S1=1S e恵用翔間迎;統(tǒng)> 系 石為本五算法優(yōu)缺點(diǎn)：每一步的擴(kuò)散為當(dāng)前耗散度的最優(yōu)。隊(duì)列式分支限界法的搜索解空間樹的方式類似于解空間樹的寬度優(yōu)先搜索，不同的是隊(duì) 列式分支限界法不搜索以不可行結(jié)點(diǎn)（已經(jīng)被判定不能導(dǎo)致可行解或不能導(dǎo)致最優(yōu)解的結(jié) 點(diǎn)）為根的子樹。按照規(guī)則，這樣的結(jié)點(diǎn)不被列入活結(jié)點(diǎn)表。A->E->Q->M優(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)的數(shù)值p來表