單源最短路徑分支限界

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

2、解單源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結(jié)點表。 所對應(yīng)的當(dāng)前路長。算法從圖G的源頂點s和空優(yōu)先隊列開始。結(jié)點s被擴(kuò)展后，它的兒子結(jié)點被依次插入堆中。 算法每次從堆中取出具有最小當(dāng)前路長的結(jié)點作為當(dāng)前擴(kuò)展結(jié)點，并依次檢查與當(dāng)前擴(kuò)展結(jié)點相鄰的所有頂點。如果從當(dāng)前擴(kuò)展結(jié)點i到j(luò)有邊可達(dá)，且從源出發(fā)，途經(jīng) i再到j(luò)的所相應(yīng)路徑長度，小于 當(dāng)前最優(yōu)路徑長度，則將該頂點作為活結(jié)點插入到活結(jié)點優(yōu)先隊列中。結(jié)點擴(kuò)展過程一直繼續(xù)到活結(jié)點優(yōu)先隊列為空時為止二單源最短路徑問題1問題描述下面以一個例子來說明單源最短路徑問題：在下圖所給的有向圖G中，每一邊都有一個非負(fù)邊權(quán)。要求圖 G的從源頂點s到目

3、標(biāo)頂點t之間的最短路徑。下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中,每一個結(jié)點旁邊的數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長。Ca324eh55,126gm567107r1172. 算法思想解單源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結(jié)點表。其優(yōu)先級是 結(jié)點所對應(yīng)的當(dāng)前路長。算法從圖G的源頂點s和空優(yōu)先隊列開始。結(jié)點 s被擴(kuò)展后，它的兒子結(jié)點被依次插入 堆中。此后，算法從堆中取出具有最小當(dāng)前路長的結(jié)點作為當(dāng)前擴(kuò)展結(jié)點，并依次檢查與當(dāng)前擴(kuò)展結(jié)點相鄰的所有頂點。如果從當(dāng)前擴(kuò)展結(jié)點i到頂點j有邊可達(dá)，且從源出發(fā)，途經(jīng)頂點i再到頂點j的所相應(yīng)的路徑的長度小于當(dāng)前最

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

5、ce std;const int size = 100;con st int inf = 5000;/ 兩點距離上界/第一組測試參數(shù)const int n = 6;/圖頂點個數(shù)加 1int prevn;/圖的前驅(qū)頂點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;/* 第二組測試參數(shù)const int

6、n = 5; /圖頂點個數(shù)加 1int prevn; / 圖的前驅(qū)頂點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;/ 頂點編號int length; / 當(dāng)前路長;/循環(huán)隊列class CirQueueprivate:int front,rear;MinHeapNode datasize; public:CirQueue()front = rear = 0;

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

8、判斷隊列是否為空bool empty()return front = rear;/判斷隊列是否為滿bool full()return (rear +1)%size = front;/CirQueue 結(jié)束/圖的表示class Graphpublic:/單源最短路徑問題的優(yōu)先隊列式分支限界法void shortestPath(int v)/ 創(chuàng)建隊列CirQueue qq;/定義源為初始擴(kuò)展結(jié)點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)/頂點i到頂點j可達(dá)，且滿足控制約束distj = m.length + cm.ij;prevj = m.i;/加入活結(jié)點優(yōu)先隊列MinHeapNode mi;mi.i = j;mi.length = distj;if(qq.full()break;qq.queryIn(mi);/元素入隊/for 循環(huán)結(jié)束if(qq.empty()break;qq.queryOut(); /當(dāng)該結(jié)點的孩子結(jié)

10、點全部入隊后，刪除該結(jié)點/while 循環(huán)結(jié)束/ 方法結(jié)束;/ 類結(jié)束int main()Graph g;g.shortestPath(1);cout<<" 最短路徑長為"<<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)缺點：每一步的擴(kuò)散為當(dāng)前耗散度的最優(yōu)。隊列式分支限界法的搜索解空間樹的方式類似于解空間樹的寬度優(yōu)先搜索，不同的是隊 列式分支限界法不搜索以不可行結(jié)點（已經(jīng)被判定不能導(dǎo)致可行解或不能導(dǎo)致最優(yōu)解的結(jié) 點）為根的子樹。按照規(guī)則，這樣的結(jié)點不被列入活結(jié)點表。A->E->Q->M優(yōu)先隊列式分支限界法的搜索方式是根據(jù)活結(jié)點的優(yōu)先級確定下一個擴(kuò)展結(jié)點。結(jié)點的 優(yōu)先級常用一個與該結(jié)點有關(guān)的數(shù)值p來表