實驗四單源最短路徑問題一、實驗?zāi)康模豪斫夥种藿绶ǖ募糁λ阉鞑呗裕徽莆辗种藿绶ǖ乃惴ü窦?；掌握分支限界法的算法步驟；通過應(yīng)用范例學(xué)習(xí)動態(tài)規(guī)劃算法的設(shè)計技巧與策略；實驗內(nèi)容及要求：1、使用分支限界法解決單源最短路徑問題。2、通過上機實驗進行算法實現(xiàn)。3、保存和打印出程序的運行結(jié)果，并結(jié)合程序進行分析，上交實驗報告。三、實驗原理：分支限界法的基本思想：1、分支限界法與回溯法的不同：1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。2、分支限界法基本思想：分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。3、常見的兩種分支限界法：1）隊列式(FIFO)分支限界法按照隊列先進先出（FIFO）原則選取下一個節(jié)點為擴展節(jié)點。2）優(yōu)先隊列式分支限界法按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當(dāng)前擴展節(jié)點。四、程序代碼：#include<iostream>usingnamespacestd;constintsize=100;constintinf=5000;//兩點距離上界/*//第一組測試參數(shù)constintn=6;//圖頂點個數(shù)加1intprev[n];//圖的前驅(qū)頂點intdist[]={0,0,5000,5000,5000,5000};//最短距離數(shù)組intc[n][n]={{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ù)constintn=5;//圖頂點個數(shù)加1intprev[n];//圖的前驅(qū)頂點intdist[]={0,0,5000,5000,5000};intc[n][n]={{0,0,0,0,0},{0,0,2,3,5000},{0,5000,0,1,3},{0,5000,5000,0,9},{0,5000,5000,5000,0}};classMinHeapNode{public:inti;//頂點編號intlength;//當(dāng)前路長};//循環(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!=front){front=(front+1)%size;//隊列在循環(huán)意義下加1returndata[front];}}//讀取隊頭元素，但不出隊MinHeapNodegetQuery(){if(rear!=front){returndata[(front+1)%size];}}//判斷隊列是否為空boolempty(){returnfront==rear;}//判斷隊列是否為滿boolfull(){return(rear+1)%size==front;}};//CirQueue結(jié)束//圖的表示classGraph{public://單源最短路徑問題的優(yōu)先隊列式分支限界法voidshortestPath(intv){//創(chuàng)建隊列CirQueueqq;//定義源為初始擴展結(jié)點MinHeapNodee;e.i=v;e.length=0;dist[v]=0;qq.queryIn(e);//搜索問題的解空間while(true){for(intj=1;j<n;j++){if(j>=n){break;}MinHeapNodem=qq.getQuery();if((c[m.i][j]<inf)&&(m.length+c[m.i][j]<dist[j])){//頂點i到頂點j可達，且滿足控制約束dist[j]=m.length+c[m.i][j];prev[j]=m.i;//加入活結(jié)點優(yōu)先隊列MinHeapNodemi;mi.i=j;mi.length=dist[j];if(qq.full()){break;}qq.queryIn(mi);//元素入隊}}//for循環(huán)結(jié)束if(qq.empty()){break;}qq.queryOut();//當(dāng)該結(jié)點的孩子結(jié)點全部入隊后，刪除該結(jié)點}//while循環(huán)結(jié)束}//方法結(jié)束};//類結(jié)束intmain(){Graphg;g.shortestPath(1);cout<<"最短路徑長為"<<dist[n-1]<<endl;cout<<"中間路徑為：";for(inti=3;i<n;i++){cout<<prev[i]<<"";}cout<<endl;