資源描述：
《單源最短路徑1 分支限界》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、一、實驗名稱：單源最短路徑問題?時間：X年X月X日，星期3，第三、四節(jié)?地點：0#601?二、實驗目的及要求?1、掌握分支限界法解題步驟：?1在問題的邊帶權的解空間樹中進行廣度優(yōu)先搜索??2找一個葉結點使其對應路徑的權最小(最大)?3當搜索到達一個擴展結點時,一次性擴展它的所有兒子?4將滿足約束條件且最小耗費函數(shù)￡目標函數(shù)限界的兒子,插入活結點???表中?5從活結點表中取下一結點同樣擴展直到找到所需的解或活動結點表???為空為止?三、實驗環(huán)境?Window下的vs2010?四、實驗內容?單源最短路徑問題?以一個例子來說明單源最短路徑問題：在下圖所給的有向圖G
2、中，每一邊都有一個非負邊權。?求圖G的從源頂點s到目標頂點t之間的最短路徑?五、算法描述及實驗步驟??算法思想：解單源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結點表。其優(yōu)先級是結點所對應的當前路長。??算法從圖G的源頂點s和空優(yōu)先隊列開始。結點s被擴展后，它的兒子結點被依次插入堆中。?算法每次從堆中取出具有最小當前路長的結點作為當前擴展結點，并依次檢查與當前擴展結點相鄰的所有頂點。?如果從當前擴展結點i到j有邊可達，且從源出發(fā)，途經i再到j的所相應路徑長度，小于當前最優(yōu)路徑長度，則將該頂點作為活結點插入到活結點優(yōu)先隊列中。?結點擴展過程一直繼續(xù)到
3、活結點優(yōu)先隊列為空時為止二．單源最短路徑問題?1.問題描述?下面以一個例子來說明單源最短路徑問題：在下圖所給的有向圖G中，每一邊都有一個非負邊權。要求圖G的從源頂點s到目標頂點t之間的最短路徑。下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產生的解空間樹。其中，每一個結點旁邊的數(shù)字表示該結點所對應的當前路長。2.?算法思想?解單源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結點表。其優(yōu)先級是結點所對應的當前路長。算法從圖G的源頂點s和空優(yōu)先隊列開始。結點s被擴展后，它的兒子結點被依次插入堆中。此后，算法從堆中取出具有最小當前路長的結點作為當
4、前擴展結點，并依次檢查與當前擴展結點相鄰的所有頂點。如果從當前擴展結點i到頂點j有邊可達，且從源出發(fā)，途經頂點i再到頂點j的所相應的路徑的長度小于當前最優(yōu)路徑長度，則將該頂點作為活結點插入到活結點優(yōu)先隊列中。?這個結點的擴展過程一直繼續(xù)到活結點優(yōu)先隊列為空時為止。3.?剪枝策略???在算法擴展結點的過程中，一旦發(fā)現(xiàn)一個結點的下界不小于當前找到的最短路長，則算法剪去以該結點為根的子樹。??????在算法中，利用結點間的控制關系進行剪枝。從源頂點s出發(fā)，2條不同路徑到達圖G的同一頂點。由于兩條路徑的路長不同，因此可以將路長長的路徑所對應的樹中的結點為根的子樹剪去
5、。???下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產生的解空間樹的剪枝情況。三．程序設計：#includeusingnamespacestd;constintsize=100;constintinf=5000;//兩點距離上界//第一組測試參數(shù)constintn=6;//圖頂點個數(shù)加1intprev[n];//圖的前驅頂點intdist[]={0,0,5000,5000,5000,5000};//最短距離數(shù)組intc[n][n]={{0,0,0,0,0,0},{0,0,2,3,5000,5000},//圖的鄰接矩陣{0,50
6、00,0,1,2,5000},{0,5000,5000,0,9,2},{0,5000,5000,5000,0,2},{0,5000,5000,5000,5000,0}};/*第二組測試參數(shù)constintn=5;//圖頂點個數(shù)加1intprev[n];//圖的前驅頂點intdist[]={0,0,5000,5000,5000};intc[][n]={{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}};*/classMinHeapNode{publi
7、c:inti;//頂點編號intlength;//當前路長};//循環(huán)隊列classCirQueue{private:intfront,rear;MinHeapNodedata[size];public:CirQueue(){front=rear=0;}//元素入隊操作voidqueryIn(MinHeapNodee){if((rear+1)%size!=front){rear=(rear+1)%size;//隊尾指針在循環(huán)意義下加1data[rear]=e;//在隊尾插入元素}}//元素出隊操作MinHeapNodequeryOut(){if(rear!=
8、front){front=(front+1)%siz
