單源最短路徑分支限界法

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第 7 次實(shí)驗(yàn)姓名學(xué)號班級時(shí)間12.26上午地點(diǎn)四合院 實(shí)驗(yàn)名稱分支界限法求最短路徑實(shí)驗(yàn)?zāi)康模?）掌握并運(yùn)用分支限界法基本思想（2）運(yùn)用分支限界法實(shí)現(xiàn)單源最短路徑問題。實(shí)驗(yàn)原理給定下示有向圖，利用分支限界法的思想，計(jì)算并輸出其單源最短路徑。實(shí)驗(yàn)步驟1 算法從圖 G 的源頂點(diǎn) s 和空優(yōu)先隊(duì)列開始。結(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)作

2、為活結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中；4 結(jié)點(diǎn)擴(kuò)展過程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止關(guān)鍵代碼void shorest(int v) priority_queue<HeapNode> heap; HeapNode enode(v,0); for(int i=1; i<=n; i+) disti=MAX; distv=0;/搜索問題的解空間 while(1) for(int j=1; j<=n; j+) if(aenode.ij<MAX && enode.length+aenode.ij<distj)/頂點(diǎn)I到J是可達(dá)的，并且滿足控制約束 dist

3、j=enode.length+aenode.ij; HeapNode node(j,distj); heap.push(node);/加入活節(jié)點(diǎn)優(yōu)先隊(duì)列 if(heap.empty() break;/優(yōu)先隊(duì)列為空 else enode=heap.top(); heap.pop(); 測試結(jié)果隨機(jī)數(shù)產(chǎn)生圖的權(quán)值：實(shí)驗(yàn)心得通過這次實(shí)驗(yàn)，我回顧了分支界限法求解最短路徑問題，在其中加入了舍伍德隨機(jī)化取值過程，使數(shù)據(jù)分布更加均勻，讓我熟悉了隨機(jī)化算法，也讓結(jié)果更加公平可靠。本次實(shí)驗(yàn)在書本有詳細(xì)的算法，很容易實(shí)現(xiàn)了上面的圖形，同時(shí)仿照了回溯算法中隨機(jī)取值產(chǎn)生權(quán)值的方法生成了一個(gè)圖，并且通過改進(jìn)，實(shí)現(xiàn)了隨機(jī)

4、選擇源點(diǎn)的方法進(jìn)行求解最短路徑。通過這次實(shí)驗(yàn)，不僅掌握了分支界限算法，還掌握了隨機(jī)產(chǎn)生一個(gè)圖并計(jì)算其最短路徑的算法，讓我覺得收獲頗大。實(shí)驗(yàn)得分助教簽名附錄：完整代碼#include <iostream>#include <queue>#include<stdlib.h>using namespace std;#define MAX 9999/定義為無限大 #define N 60int n,distN,aNN;class HeapNode/最小堆來存儲活節(jié)點(diǎn)表 public: int i,length;/頂點(diǎn)編號，當(dāng)前的路徑長度 HeapNode() Hea

5、pNode(int ii,int l) i=ii; length=l; bool operator<(const HeapNode& node)const return length<node.length; ;void shorest(int v) priority_queue<HeapNode> heap; HeapNode enode(v,0); for(int i=1; i<=n; i+) disti=MAX; distv=0;/搜索問題的解空間 while(1) for(int j=1; j<=n; j+) if(aenode.ij<

6、MAX && enode.length+aenode.ij<distj)/頂點(diǎn)I到J是可達(dá)的，并且滿足控制約束 distj=enode.length+aenode.ij; HeapNode node(j,distj); heap.push(node);/加入活節(jié)點(diǎn)優(yōu)先隊(duì)列 if(heap.empty() break;/優(yōu)先隊(duì)列為空 else enode=heap.top(); heap.pop(); int main ()int v,i;cout<<"個(gè)數(shù)：" cin>>n; cout<<"源點(diǎn)："

7、;cin>>v; for(int i=1; i<=n; i+) for(int j=1; j<=n; j+) if(i!=j) if(aji=0)|(aji=MAX) aij=rand()%100+1; else aij=MAX; if(aij>50) aij=MAX; cout<<"n路徑： "<<endl; for( i=1;i<n+1;i+)for(int j=1;j<n+1;j+)cout<<aij<<" "cout<<endl; shorest(v); cout<<endl; for( i=2; i<n; i+) cout<<v<<"到"<<i<<"的最短路徑為："<<disti<<endl; cout<<v&l