分枝限界法-實(shí)驗(yàn)報(bào)告

一、課題名稱用分枝限界法求解單源最短路徑問題二、課題內(nèi)容和要求設(shè)計(jì)要求：學(xué)習(xí)算法設(shè)計(jì)中分枝限界法的思想，設(shè)計(jì)算法解決數(shù)據(jù)結(jié)構(gòu)中求解單源最短路徑問題，編程實(shí)現(xiàn)：（1）給出指定源點(diǎn)的單源最短路徑；（2）說明算法的時(shí)間復(fù)雜度。三、需求分析1.實(shí)現(xiàn)極小堆的創(chuàng)建，用來存儲(chǔ)活結(jié)點(diǎn)表。2.實(shí)現(xiàn)循環(huán)隊(duì)列的創(chuàng)建、初始化、入隊(duì)、出隊(duì)等操作。3.實(shí)現(xiàn)分支限界法來實(shí)現(xiàn)求解單元最短路徑的算法。4.實(shí)現(xiàn)最短路徑的正確輸出。四、概要設(shè)計(jì)建立工程MinPath.dsw,加入源文件main.cpp，頭文件CirQueue.h,init.h，Minpath.h和output.h.CirQueue.h中實(shí)現(xiàn)極小堆的創(chuàng)建，循環(huán)隊(duì)列的創(chuàng)建、初始化、入隊(duì)、出隊(duì)等操作，Minpath.h中實(shí)現(xiàn)分支限界法來實(shí)現(xiàn)求解單元最短路徑的算法。output.h中實(shí)現(xiàn)最短路徑的正確輸出。如下圖所示：實(shí)驗(yàn)用例如下，通過鄰接矩陣的方式寫在init.h中：1125811346971023432922122237333522五、詳細(xì)設(shè)計(jì)main函數(shù)：#include<iostream.h>#include"init.h"#include"CirQueue.h"#include"MinPath.h"#include"output.h"voidmain(){ intk; intq; cout<<"------------歡迎使用本系統(tǒng)---------------"<<endl; cout<<"------------請(qǐng)選擇單元路徑的起點(diǎn)：---------------"<<endl; cout<<"------------提示：輸入"<<1<<"到"<<n-1<<"之間的整數(shù)---------------"<<endl; cin>>k; cout<<"------------請(qǐng)選擇單元路徑的終點(diǎn)：---------------"<<endl; cin>>q; while(k<1||k>11) { cout<<"------------提示：輸入"<<1<<"到"<<n-1<<"之間的數(shù)，請(qǐng)重新輸入---------------"<<endl; cin>>k; }MinPath(k); output(k,q);}init.hconstintsize=200;constintinf=1000;//兩點(diǎn)距離上界置為1000constintn=12;//圖頂點(diǎn)個(gè)數(shù)加1intprev[n];//圖的前驅(qū)頂點(diǎn)intdist[]={0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf};//最短距離數(shù)組intc[n][n]={{0,0,0,0,0,0,0,0,0,0,0,0},{0,0,2,3,4,inf,inf,inf,inf,inf,inf,inf},{0,inf,0,3,inf,7,2,inf,inf,inf,inf,inf},{0,inf,inf,0,inf,inf,9,2,inf,inf,inf,inf},{0,inf,inf,inf,0,inf,inf,2,inf,inf,inf,inf},{0,inf,inf,inf,inf,0,inf,inf,3,3,inf,inf},{0,inf,inf,inf,inf,inf,0,1,inf,3,inf,inf},{0,inf,inf,inf,inf,inf,inf,0,inf,5,1,inf},{0,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,3},{0,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,2},{0,inf,inf,inf,inf,inf,inf,inf,inf,2,inf,2},{0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0},};//圖的鄰接矩陣CirQueue.hclassMinHeapNode//創(chuàng)建極小堆用來存儲(chǔ)活結(jié)點(diǎn)表{public:inti;//頂點(diǎn)編號(hào)intlength;//當(dāng)前路長(zhǎng)};classCirQueue//循環(huán)隊(duì)列{private:intfront,rear;//頭指針和尾指針MinHeapNodedata[size];public:CirQueue()//初始化建空隊(duì)列{front=rear=0;}voidqueryIn(MinHeapNodee)//元素入隊(duì)操作{ if((rear+1)%size!=front)//隊(duì)列未滿 { rear=(rear+1)%size;//插入新的隊(duì)尾元素 data[rear]=e;//在隊(duì)尾插入元素 }}voidqueryOut()//元素出隊(duì)操作{if(rear!=front){front=(front+1)%size;//刪除隊(duì)頭元素}}MinHeapNodegetQuery()//讀取隊(duì)頭元素，但不出隊(duì){if(rear!=front){returndata[(front+1)%size];}returndata[1];}boolempty()//判斷隊(duì)列是否為空{(diào)returnfront==rear;}boolfull()//判斷隊(duì)列是否為滿{return(rear+1)%size==front;}};//CirQueue結(jié)束MainPath.hvoidMinPath(intv){CirQueues;//定義源為初始擴(kuò)展結(jié)點(diǎn)MinHeapNodee;e.i=v;e.length=0;dist[v]=0;s.queryIn(e);//將源節(jié)點(diǎn)加入隊(duì)列while(true){for(intj=1;j<n;j++){if(j>=n){ break;}MinHeapNodem=s.getQuery();if((c[m.i][j]<inf)&&(m.length+c[m.i][j]<dist[j]))//頂點(diǎn)i到頂點(diǎn)j可達(dá)，且從源出發(fā)途經(jīng)i到j(luò)的路徑長(zhǎng)度小于當(dāng)前最優(yōu)路徑長(zhǎng)度{dist[j]=m.length+c[m.i][j];prev[j]=m.i; MinHeapNodemi;//加入活結(jié)點(diǎn)優(yōu)先隊(duì)列mi.i=j; mi.length=dist[j];if(s.full()) { break; }s.queryIn(mi);//元素入隊(duì)}}//for循環(huán)結(jié)束if(s.empty()){break;}s.queryOut();//當(dāng)該結(jié)點(diǎn)的孩子結(jié)點(diǎn)全部入隊(duì)后，刪除該結(jié)點(diǎn)}//while循環(huán)結(jié)束}//方法結(jié)束output.hvoidoutput(intk,intq){intq1=q;if(dist[q1]==1000){ cout<<"------------找不到此路徑---------------"<<endl; return;}cout<<"最短路徑長(zhǎng)為:"<<dist[q1]<<endl;cout<<"單源最短路徑為:";inta[12]={0};intt=q1;ints=0;for(inti=0;t!=k;i++){ a[i]=prev[t]; t=prev[t]; s=s+1;}for(i=s-1;i>-1;i--){ cout<<a[i]<<"";}cout<<q1;cout<<endl<<"------------歡迎使用本系統(tǒng)---------------"<<endl;}六、測(cè)試數(shù)據(jù)及其結(jié)果分析1.選擇起點(diǎn)：1，終點(diǎn)：111到11最短路徑長(zhǎng)為8，為1->3->7->10->11所獲得。2.選擇起點(diǎn)：2，終點(diǎn)：92到9最短路徑長(zhǎng)為5，為2->6->9所獲得。3.選擇起點(diǎn)8，終點(diǎn)28到2沒有路徑，輸出“找不到此路徑”。4.選擇起點(diǎn)11，終點(diǎn)111到1沒有路徑，輸出“找不到此路徑”。七、調(diào)試過程中的問題1.CirQueue.h中，函數(shù)getQuery()中在調(diào)試過程中出現(xiàn)warnig:'CirQueue::getQuery':notallcontrolpathsreturnavalue.解決方案：在if語句下面加上returndata[1];使當(dāng)rear=front時(shí)函數(shù)也返回一個(gè)值。2.當(dāng)兩結(jié)點(diǎn)間沒有路徑時(shí)，程序執(zhí)行時(shí)出現(xiàn)錯(cuò)誤。解決方案：在輸出函數(shù)output中加入下面代碼if(dist[q1]==1000){ cout<<"------------找不到此路徑---------------"<<endl; return;}即當(dāng)兩結(jié)點(diǎn)無路徑時(shí)，輸出提示“找不到此路徑”，程序執(zhí)行時(shí)不會(huì)崩潰。3.輸出過程中，如何使結(jié)點(diǎn)按順序輸出？定義一個(gè)數(shù)組a[],應(yīng)用遞歸對(duì)存儲(chǔ)前驅(qū)結(jié)點(diǎn)的數(shù)組prev[]從后往前求解，將得到的值賦給數(shù)組a[],最后逆向輸出對(duì)應(yīng)的數(shù)組a[],即得到正確的路徑順序。如下：for(inti=0;t!=k;i++){ a[i]=prev[t]; t=prev[t]; s=s+1;}for(i=s-1;i>-1;i--){ cout<<a