分支限界法實(shí)驗單源最短路徑

1、算法分析與設(shè)計實(shí)驗報告第 七 次實(shí)驗姓名學(xué)號班級時間12.26上午地點(diǎn)工訓(xùn)樓309 實(shí)驗名稱分支限界法實(shí)驗(單源最短路徑)實(shí)驗?zāi)康?. 掌握并運(yùn)用分支限界法的基本思想2. 運(yùn)用分支限界法實(shí)現(xiàn)單源最短路徑問題實(shí)驗原理問題描述：在下圖所給的有向圖G中，每一邊都有一個非負(fù)邊權(quán)。要求圖G的從源頂點(diǎn)s到目標(biāo)頂點(diǎn)t之間的最短路徑?；舅枷耄合聢D是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)所對應(yīng)的當(dāng)前路長。為了加速搜索的進(jìn)程，應(yīng)采用有效地方式選擇活結(jié)點(diǎn)進(jìn)行擴(kuò)展。按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。實(shí)驗步驟（1）算法從圖

2、G 的源頂點(diǎn) s 和空優(yōu)先隊列開始。結(jié)點(diǎn) s 被擴(kuò)展后，它的兒子 結(jié)點(diǎn)被依次插入堆中；（2）算法每次從堆中取出具有最小當(dāng)前路長的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)， 并依 次檢查與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰的所有頂點(diǎn)；（3）如果從當(dāng)前擴(kuò)展結(jié)點(diǎn) i 到 j 有邊可達(dá)，且從源出發(fā)，途經(jīng) i 再到 j 的所相應(yīng)路徑長度，小于當(dāng)前最優(yōu)路徑長度，則將該頂點(diǎn)作為活結(jié)點(diǎn)插入到活結(jié) 點(diǎn)優(yōu)先隊列中；（4）結(jié)點(diǎn)擴(kuò)展過程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊列為空時為止。關(guān)鍵代碼/單源最短路徑問題的優(yōu)先隊列式分支限界法templatevoid Graph:shortest_path(int v) /定義最小堆的容量為1000MinHeapMinHeapN

3、ode H(1000);/定義源為初始擴(kuò)展結(jié)點(diǎn)MinHeapNode E;/初始化源結(jié)點(diǎn)E.i=v;E.length=0;distv=0;while(true) /搜索問題的解空間for(int j=1;j=n;j+)if(cE.ij!=0)&(E.length+cE.ijdistj)/頂點(diǎn)i到頂點(diǎn)j可達(dá)，且滿足控制約束/頂點(diǎn)i和j之間有邊，且此路徑小于原先從源點(diǎn)到j(luò)的路徑長度distj=E.length+cE.ij; /更新dist數(shù)組prevj=E.i;/加入活結(jié)點(diǎn)優(yōu)先隊列MinHeapNode N;N.i=j;N.length=distj;H.Insert(N); /插入到最小堆中try

4、H.DeleteMin(E); / 取下一擴(kuò)展結(jié)點(diǎn)catch (int)break;if(H.currentsize=0) /優(yōu)先隊列空break;測試結(jié)果上述有向圖的結(jié)果： 實(shí)驗分析在實(shí)驗中并沒有生成多組數(shù)據(jù)，進(jìn)行比較，也沒有利用隨機(jī)生成函數(shù)，因為在這種有實(shí)際有關(guān)聯(lián)的問題中，利用隨機(jī)生成函數(shù)生成的數(shù)據(jù)是十分的不合適的，在此我們只需要驗證該程序是否正確即可。分支限界法求單源最短路徑問題與回溯法求單源最短路徑問題其大致思想是一致的，都是利用解空間樹，搜索子集樹，回溯法是利用深度優(yōu)先搜索子集樹，而分支限界法是利用廣度優(yōu)先搜索子集樹，然后利用隊列或優(yōu)先隊列，最小堆存放可擴(kuò)展的結(jié)點(diǎn)，然后將活結(jié)點(diǎn)出堆，

5、從而直到堆空為止，找到最優(yōu)解。實(shí)驗心得在這一章的分支限界法中，與上一章的回溯法很相似，都是利用解空間樹進(jìn)行搜索，從而找到最優(yōu)解。不同的是回溯法利用的是深度優(yōu)先回溯尋找，能夠找到所有的最優(yōu)解；而分支限界法則是利用廣度優(yōu)先搜索子集樹或者排序樹，利用隊列或者優(yōu)先級隊列的數(shù)據(jù)結(jié)構(gòu)組織所有滿足的結(jié)點(diǎn)，這樣只要找到一種最優(yōu)解就可以了，想對于回溯法來說時間上相對利用的沒有那么多。在這一章的學(xué)習(xí)上，由于會利用最小堆/最大堆，所以代碼看起來比較復(fù)雜，堆的實(shí)現(xiàn)也比較復(fù)雜，這是這一章我學(xué)習(xí)的一個難點(diǎn)，不過正在漸漸攻克。實(shí)驗得分助教簽名附錄：完整代碼（分支限界法）Shorest_path.cpp/單源最短路徑問題 分

6、支限界法求解#include#include#include#includeMinHeap2.husing namespace std;templateclass Graph /定義圖類friend int main();public:void shortest_path(int);private:int n, /圖的頂點(diǎn)數(shù)*prev; /前驅(qū)頂點(diǎn)數(shù)組Type *c, /圖的鄰接矩陣*dist; /最短距離數(shù)組;templateclass MinHeapNode /最小堆中的元素類型為MinHeapNodefriend Graph;public:operator int() constretu

7、rn length;private:int i; /頂點(diǎn)編號Type length; /當(dāng)前路長; /單源最短路徑問題的優(yōu)先隊列式分支限界法templatevoid Graph:shortest_path(int v) MinHeapMinHeapNode H(1000);/定義最小堆的容量為1000/定義源為初始擴(kuò)展結(jié)點(diǎn)MinHeapNode E;/初始化源結(jié)點(diǎn)E.i=v;E.length=0;distv=0;while(true)/搜索問題的解空間for(int j=1;j=n;j+)if(cE.ij!=0)&(E.length+cE.ijdistj)/頂點(diǎn)i到頂點(diǎn)j可達(dá)，且滿足控制約束/

8、頂點(diǎn)i和j之間有邊，且此路徑小于原先從源點(diǎn)i到j(luò)的路徑長度distj=E.length+cE.ij;/更新dist數(shù)組prevj=E.i;/加入活結(jié)點(diǎn)優(yōu)先隊列MinHeapNode N;N.i=j;N.length=distj;H.Insert(N);/插入到最小堆中tryH.DeleteMin(E); / 取下一擴(kuò)展結(jié)點(diǎn)catch (int)break;if(H.currentsize=0)/優(yōu)先隊列空break;int main()int n=11;int prev12=0,0,0,0,0,0,0,0,0,0,0,0;/初始化前驅(qū)頂點(diǎn)數(shù)組int dist12=1000,1000,1000,

9、1000,1000,1000,1000,1000,1000,1000,1000,1000;/初始化最短距離數(shù)組cout單源圖的鄰接矩陣如下：endl;int *c=new int*n+1;for(int i=1;i=n;i+) /輸入圖的鄰接矩陣ci=new intn+1;for(int j=1;jcij;int v=1; /源結(jié)點(diǎn)為1Graph G;G.n=n;G.c=c;G.dist=dist;G.prev=prev;clock_t start,end,over; /計算程序運(yùn)行時間的算法start=clock();end=clock();over=end-start;start=cloc

10、k(); G.shortest_path(v);/調(diào)用圖的最短路徑查找算法/輸出從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的最短路徑cout從S到T的最短路長是：dist11endl;for(int i=2;i=n;i+)/輸出每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)coutprev(i)=previ endl;for(int i=2;i=n;i+) /輸出從源結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑長度cout從1到i的最短路長是：distiendl;for(int i=1;i=n;i+) /刪除動態(tài)分配時的內(nèi)存delete ci;delete c;c=0;end=clock();printf(The time is %6.3f,(double)(en

11、d-start-over)/CLK_TCK); /顯示運(yùn)行時間coutendl;system(pause);return 0;MinHeap.h#includetemplateclass Graph;templateclass MinHeap /最小堆類templatefriend class Graph;public:MinHeap(int maxheapsize=10); /構(gòu)造函數(shù)，堆的大小是10MinHeap()delete heap; /最小堆的析構(gòu)函數(shù)int Size() constreturn currentsize; /Size()返回最小堆的個數(shù)T Max()if(curre

12、ntsize) return heap1; /第一個元素出堆MinHeap& Insert(const T& x); /最小堆的插入函數(shù)MinHeap& DeleteMin(T& x); /最小堆的刪除函數(shù)void Initialize(T x,int size,int ArraySize); /堆的初始化void Deactivate();void output(T a,int n);private:int currentsize,maxsize; T *heap; ;templatevoid MinHeap:output(T a,int n) /輸出函數(shù)，輸出a數(shù)組的元素for(int i

13、=1;i=n;i+)coutai ;coutendl;templateMinHeap:MinHeap(int maxheapsize)maxsize=maxheapsize;heap=new Tmaxsize+1; /創(chuàng)建堆currentsize=0;templateMinHeap& MinHeap:Insert(const T& x)if(currentsize=maxsize) /如果堆中的元素已經(jīng)等于堆的最大大小return *this; /那么不能在加入元素進(jìn)入堆中int i= +currentsize;while(i!=1 & xheapi/2)heapi=heapi/2;i/=2;

14、heapi=x;return *this;templateMinHeap& MinHeap:DeleteMin(T& x) /刪除堆頂元素if(currentsize=0) coutEmpty heap!endl;return *this;x=heap1; T y=heapcurrentsize-;int i=1,ci=2;while(ci=currentsize)if(ciheapci+1)ci+;if(y=heapci)break;heapi=heapci;i=ci;ci*=2;heapi=y;return *this;templatevoid MinHeap:Initialize(T x,int size,int ArraySize) /堆的初始化dele