算法之分支限界法實(shí)現(xiàn)

實(shí)驗(yàn)5分支限界法實(shí)現(xiàn)熟悉分支限界法應(yīng)用場(chǎng)景及實(shí)現(xiàn)的基本方法步驟；學(xué)會(huì)分支限界法的實(shí)現(xiàn)方法和分析方法：二實(shí)驗(yàn)內(nèi)容n后問題：編程計(jì)算當(dāng)n=1到8時(shí)解的個(gè)數(shù)，分別利用回溯法和分支限界法實(shí)現(xiàn)，比較并分析你的算法效率?；厮莘ǎ捍a：#include<iostream>#include<cmath>usingnamespacestd;〃法一：迭代回溯classQueen(friendintnQueen(int);private:boolPlace(intk);voidBacktrack(intt);intn;//皇后個(gè)數(shù)int*x;//當(dāng)前解intsum;//當(dāng)前已找到的可行方案數(shù)};boolQueen::Place(intk)for(intj=1;j<k;j++)(if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;}returntrue;}voidQueen::Backtrack(intt)(if(t>n)sum++;elsefor(inti=1;i<=n;i++)(x[t]=i;if(Place(t))Backtrack(t+1);}}intnQueen(intn)(QueenX;//初始化XX.n=n;X.sum=0;int*p=newint[n+1];for(inti=0;i<=n;i++)p[i]=0;X.x=p;X.Backtrack(1);delete[]p;returnX.sum;}intmain()(cout<<"共有〃<<nQueen(8)<<"種〃<<endl;system(〃pause〃)；return0;截圖：分支限界法:代碼：#include<iostream>#include<cmath>usingnamespacestd;classQueen(friendintnQueen(int);private:boolPlace(intk);voidredu(intt);intn;//皇后個(gè)數(shù)int*x;//當(dāng)前解intsum;//當(dāng)前已找到的可行方案數(shù)};〃剪枝函數(shù)〃判斷當(dāng)前狀態(tài)是否合理，即皇后會(huì)不會(huì)互相攻擊boolQueen::Place(intk)(for(intj=1;j<k;j++)(if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;}〃所有皇后都不會(huì)互相攻擊returntrue;intnQueen(intn)(QueenX;//初始化XX.n=n;X.sum=0;int*p=newint[n+1];for(inti=0;i<=n;i++)p[i]=0;X.x=p;X.redu(1);delete[]p;returnX.sum;}voidswap(int&a,int&b)(intt=a;a=b;b=t;}voidQueen::redu(intt)(if(t>n)sum++;elsefor(inti=1;i<=n;i++)(x[t]=i;if(Place(t))redu(t+1);}}intmain()(cout<<"共有〃<<nQueen(8)<<"種〃<<endl;system(〃pause〃)；return0;截圖：C:\Users\Acdminis-tratcr\sourcea\reapos\Projecii1\DeE3ug\Proj&cdt單源最短路徑問題:如圖求出從源頂點(diǎn)0到其它頂點(diǎn)的最短路徑長(zhǎng)度，比較貪心算法和分支限界法。貪心算法（dijk）代碼：#include<iostream>usingnamespacestd;#definemaxint10000//n為節(jié)點(diǎn)個(gè)數(shù)，v為源節(jié)點(diǎn)，dist為源節(jié)點(diǎn)到其他節(jié)點(diǎn)距離數(shù)組，//prev為源節(jié)點(diǎn)到頂點(diǎn)i的最短路徑上的前一個(gè)節(jié)點(diǎn)，c為個(gè)節(jié)點(diǎn)之間的距離數(shù)組voidDijkstra(intn,intv,intdist[],intprev[],int**c)(〃頂點(diǎn)集合Sbools[maxint];for(inti=1;i<=n;i++)(//源節(jié)點(diǎn)到各節(jié)點(diǎn)的距離記錄dist[i]=c[v][i];//S初始化為空s[i]=false;if(dist[i]==maxint)//不可達(dá)prev[i]=0;elseprev[i]=v;}//源節(jié)點(diǎn)初始化dist[v]=0;s[v]=true;//核心算法for(inti=1;i<n;i++)(inttemp=maxint;intu=v;for(intj=1;j<=n;j++)(〃尋找距離最小而且不在S中的節(jié)點(diǎn)if(!s[j]&&(dist[j]<temp))(u=j;temp=dist[j];}}〃把找到的節(jié)點(diǎn)加入到、s[u]=true;〃更新dist數(shù)組，通過(guò)u節(jié)點(diǎn)for(intj=1;j<=n;j++)(intnewdist=dist[u]+c[u][j];if(newdist<dist[j])(dist[j]=newdist;prev[j]=u;intmain()(cout<<"請(qǐng)輸入節(jié)點(diǎn)個(gè)數(shù)〃<<endl;intn;cin>>n;cout<<"請(qǐng)輸入起點(diǎn)(例如1,2,3。。。)"<<endl;intv;cin>>v;int**c=newint*[n+1];for(inti=1;i<=n;i++)c[i]=newint[n+1];cout<<"請(qǐng)輸入各節(jié)點(diǎn)之間距離"<<endl;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)(cin>>c[i][j];if(c[i][j]==0)c[i][j]=maxint;}〃測(cè)試數(shù)據(jù)//for(inti=1;i<=n;i++)//for(intj=1;j<=n;j++)//c[i][j]=maxint;//c[1][3]=20;//c[1][4]=5;//c[2][3]=30;//c[2][4]=20;//c[3][4]=30;//c[4][5]=10;intdist[maxint];intprev[maxint];Dijkstra(n,v,dist,prev,c);for(inti=1;i<=5;i++)(if(dist[i]==maxint)cout<<i<<"-->"<<v<<〃：〃<<"不可達(dá)〃<<endl;elsecout<<i<<"-->"<<v<<〃：〃<<dist[i]<<endl;}for(inti=1;i<=n;i++)deletec[i];deletec;system(〃pause〃)；return0;}截圖:分支限界法：代碼：#include<iostream>usingnamespacestd;#definemaxint10000classMinHeapNode(friendclassGraph;public:operatorint()const(returnlength;}private:inti;〃頂點(diǎn)編號(hào)intlength;〃當(dāng)前路長(zhǎng)};classMinHeap(friendclassGraph;public:MinHeap(intmaxheapsize=10);~MinHeap()(delete[]heap;}MinHeap&Insert(constMinHeapNode&x);MinHeap&DeleteMin(MinHeapNode&x);private:intcs,ms;MinHeapNode*heap;};MinHeap::MinHeap(intmaxheapsize)(ms=maxheapsize;heap=newMinHeapNode[ms+1];cs=0;}MinHeap&MinHeap::Insert(constMinHeapNode&x)(if(cs==ms)(return*this;}inti=++cs;while(i!=1&&x<heap[i/2])(heap[i]=heap[i/2];i/=2;}heap[i]=x;return*this;MinHeap&MinHeap::DeleteMin(MinHeapNode&x)(if(cs==0)(return*this;}x=heap[1];MinHeapNodey=heap[cs--];inti=1,ci=2;while(ci<=cs)(if(ci<cs&&heap[ci]>heap[ci+1])(ci++;}if(y<=heap[ci])(break;}heap[i]=heap[ci];i=ci;ci*=2;}heap[i]=y;return*this;}classGraph(friendintmain();public:voidShortesPaths(int);private:intn,〃圖G的頂點(diǎn)數(shù)*prev;//前驅(qū)頂點(diǎn)數(shù)組int**c,〃圖G的領(lǐng)接矩陣*dist;//最短距離數(shù)組};voidGraph::ShortesPaths(intv)//單源最短路徑問題的優(yōu)先隊(duì)列式分支限界法(MinHeapH(1000);MinHeapNodeE;〃定義源為初始擴(kuò)展節(jié)點(diǎn)E.i=v;E.length=0;dist[v]=0;while(true)//搜索問題的解空間(for(intj=1;j<=n;j++)if((c[E.i][j]!=0)&&(E.length+c[E.i][j]<dist[j]))(//頂點(diǎn)i到頂點(diǎn)j可達(dá)，且滿足控制約束dist[j]=E.length+c[E.i][j];prev[j]=E.i;//加入活結(jié)點(diǎn)優(yōu)先隊(duì)列MinHeapNodeN;N.i=j;N.length=dist[j];H.Insert(N);}try(H.DeleteMin(E);//取下一擴(kuò)展結(jié)點(diǎn)}catch(int)(break;}if(H.cs==0)//優(yōu)先隊(duì)列空(break;}}}intmain()cout<<"請(qǐng)輸入節(jié)點(diǎn)個(gè)數(shù)〃<<endl;intn;cin>>n;cout<<"請(qǐng)輸入起點(diǎn)(例如1,2,3。。。)"<<endl;intv;cin>>v;int**c=newint*[n+1];for(inti=1;i<=n;i++)c[i]=newint[n+1];cout<<"請(qǐng)輸入各節(jié)點(diǎn)之間距離"<<endl;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)(cin>>c[i][j];if(c[i][j]==0)c[i][j]=maxint;}intdist[maxint];for(inti=1;i<=n;i++)dist[i]=maxint;intprev[maxint];GraphG;G.n=n;G.c=c;G.dist=dist;G.prev=prev;G.ShortesPaths(v);cout<<endl<<"分支限界法"<<endl;for(inti=1;i<=5;i++)(if(dist[i]==maxint)cout<<i<<"-->"<<v<<":"<<"不可達(dá)"<<endl;elsecout<<i<<"-->"<<v<<":"<<dist[i]<<endl;}for(inti=1;i<=n;i++)(delete[]c[i];}deletec;system(〃pause〃)；return0;}截圖：IC:\Us.ers.XAdministrator\source\repos-XProject1\D-et>LigXProj&ct1.exe璋榆入節(jié)點(diǎn)十卸i青輸‘大起點(diǎn)LlM支HI,巳只--L吉身而A客節(jié)之?、°I、百1雖戶高02050rin30200門nn只廣I「nnnnin口□口□分支限界法1——>i：n=一一'〉1一f、口」j左i——>i土口-1——M:b5'■:-■［巳請(qǐng)接住音爬■紗:一--.矩陣連乘問題:AA3A430*2020*1515*2525*20已知A廣A4矩陣及其維數(shù)求最優(yōu)計(jì)算順序。代碼：#include<iostream>usingnamespacestd;voidmatrixChain(int*p,int**m,int**s,intlen)//p用來(lái)記錄矩陣，m[i][j]表示第i個(gè)矩陣到第j個(gè)矩陣的最優(yōu)解，s[][]記錄從最優(yōu)解斷開位置，len為矩陣個(gè)數(shù)(intn=len-1;for(inti=1;i<=n;i++)//初始化數(shù)組for(intj=1;j<=n;j++)m[i][j]=0;for(intr=2;r<=n;r++)(for(inti=1;i<=n-r+1;i++)//行循環(huán)(intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//初始化s[i][j]=k;尋找最優(yōu)解，以及最優(yōu)解斷開位置s[i][j]=i;for(intk=i+1;k<j;k++)(intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j])(s[i][j]=k;//在k位置斷開得到最優(yōu)解m[i][j]=t;}}}}}voidtraceback(int**s,inti,intj)(if(i==j)return;traceback(s,i,s[i][j]);traceback(s,s[i][j]+1,j);cout<<"MultiplyA"<<i<<","<<s[i][j]<<"andA"<<s[i][j]+1<<","<<j<<endl;}intmain()(intp[5]=(30,20,15,25,20};intlen=5;cout<<"各矩陣為："<<endl;for(inti=1;i<=4;i++)cout<<'M'<<i<<':'<<p[i-1]<<'*'<<p[i]<<cout<<endl<<endl;int**m=newint*[len];for(inti=1;i<len;i++)m[i]=newint[len];int**s=newint*[len];for(inti=1;i<len;i++)s[i]=newint[len];matrixChain(p,m,s,len);traceback(s,1,4);cout<<"最優(yōu)計(jì)算次數(shù)為〃<<m[1][4]<<endl<<endl;system(〃pause〃)；return0;}截圖:4.二分搜索問題：對(duì)于給定的有序整數(shù)集a={6,9,13,15,25,33,45},編寫程序查找18與33,記錄每次比較基準(zhǔn)數(shù)。代碼：#include<iostream>usingnamespacestd;voidbinary_search(inta[],intn,intkey)//a為按降序排列好了的數(shù)組，n為數(shù)組大小，key為查找的數(shù)字(intleft=0;//數(shù)組的首位置intright=n-1;//數(shù)組的最后一個(gè)位置whil