單源最短路徑分支限界

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

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

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

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

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

6、n = 5; /圖頂點個數加 1int prevn; / 圖的前驅頂點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; / 當前路長;/循環(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 結束/圖的表示class Graphpublic:/單源最短路徑問題的優(yōu)先隊列式分支限界法void shortestPath(int v)/ 創(chuàng)建隊列CirQueue qq;/定義源為初始擴展結點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可達，且滿足控制約束distj = m.length + cm.ij;prevj = m.i;/加入活結點優(yōu)先隊列MinHeapNode mi;mi.i = j;mi.length = distj;if(qq.full()break;qq.queryIn(mi);/元素入隊/for 循環(huán)結束if(qq.empty()break;qq.queryOut(); /當該結點的孩子結

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