算法之分支限界法实现

/实验5分支限界法实现一、实验目标：1.熟悉分支限界法应用场景及实现的基本方法步骤；2.学会分支限界法的实现方法和分析方法：二、实验内容1.n后问题：编程计算当n=1到8时解的个数.分别利用回溯法和分支限界法实现.比较并分析你的算法效率。回溯法：代码：#include<iostream>#include<cmath>usingnamespacestd;//法一：迭代回溯classQueen{ friendintnQueen<int>;private: boolPlace<intk>; voidBacktrack<intt>; intn;//皇后个数 int*x;//当前解 intsum;//当前已找到的可行方案数};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++; else for<inti=1;i<=n;i++> { x[t]=i; if<Place<t>> Backtrack<t+1>; }}intnQueen<intn>{ QueenX; //初始化X X.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;//皇后个数 int*x;//当前解 intsum;//当前已找到的可行方案数};//剪枝函数//判断当前状态是否合理.即皇后会不会互相攻击boolQueen::Place<intk>{ for<intj=1;j<k;j++> { if<<abs<k-j>==abs<x[j]-x[k]>>||<x[j]==x[k]>> returnfalse; } //所有皇后都不会互相攻击 returntrue;}intnQueen<intn>{ QueenX; //初始化X X.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++; else for<inti=1;i<=n;i++> { x[t]=i; if<Place<t>> redu<t+1>; }}intmain<>{ cout<<"共有"<<nQueen<8><<"种"<<endl;system<"pause">; return0;}截图：2.单源最短路径问题：如图求出从源顶点0到其它顶点的最短路径长度.比较贪心算法和分支限界法。贪心算法〔dijk代码：#include<iostream>usingnamespacestd;#definemaxint10000//n为节点个数.v为源节点.dist为源节点到其他节点距离数组.//prev为源节点到顶点i的最短路径上的前一个节点.c为个节点之间的距离数组voidDijkstra<intn,intv,intdist[],intprev[],int**c>{ //顶点集合S bools[maxint]; for<inti=1;i<=n;i++> { //源节点到各节点的距离记录 dist[i]=c[v][i]; //S初始化为空 s[i]=false; if<dist[i]==maxint>//不可达 prev[i]=0; else prev[i]=v; } //源节点初始化 dist[v]=0; s[v]=true; //核心算法 for<inti=1;i<n;i++> { inttemp=maxint; intu=v; for<intj=1;j<=n;j++>{ //寻找距离最小而且不在S中的节点if<!s[j]&&<dist[j]<temp>> { u=j; temp=dist[j]; } } //把找到的节点加入到S s[u]=true; //更新dist数组.通过u节点 for<intj=1;j<=n;j++> { intnewdist=dist[u]+c[u][j]; if<newdist<dist[j]> { dist[j]=newdist; prev[j]=u; } } }}intmain<>{ cout<<"请输入节点个数"<<endl; intn; cin>>n; cout<<"请输入起点<例如1,2,3。。。>"<<endl; intv; cin>>v; int**c=newint*[n+1];for<inti=1;i<=n;i++> c[i]=newint[n+1]; cout<<"请输入各节点之间距离"<<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; } //测试数据 //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<<":"<<"不可达"<<endl; else cout<<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; //顶点编号 intlength; //当前路长};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:int n, //图G的顶点数 *prev;//前驱顶点数组 int **c,//图G的领接矩阵 *dist;//最短距离数组};voidGraph::ShortesPaths<intv>//单源最短路径问题的优先队列式分支限界法{ MinHeapH<1000>; MinHeapNodeE; //定义源为初始扩展节点 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]>>{//顶点i到顶点j可达.且满足控制约束dist[j]=E.length+c[E.i][j]; prev[j]=E.i; //加入活结点优先队列 MinHeapNodeN; N.i=j; N.length=dist[j]; H.Insert<N>; } try { H.DeleteMin<E>;//取下一扩展结点 } catch<int> { break; } if<H.cs==0>//优先队列空 { break; } }}intmain<>{ cout<<"请输入节点个数"<<endl; intn; cin>>n; cout<<"请输入起点<例如1,2,3。。。>"<<endl; intv; cin>>v; int**c=newint*[n+1];for<inti=1;i<=n;i++>c[i]=newint[n+1]; cout<<"请输入各节点之间距离"<<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<<":"<<"不可达"<<endl; else cout<<i<<"-->"<<v<<":"<<dist[i]<<endl; } for<inti=1;i<=n;i++>{ delete[]c[i]; } deletec;system<"pause">; return0;}截图：3.矩阵连乘问题：A1A2A3A430*2020*1515*2525*20已知A1~A4矩阵及其维数求最优计算顺序。代码：#include<iostream>usingnamespacestd;voidmatrixChain<int*p,int**m,int**s,intlen>//p用来记录矩阵.m[i][j]表示第i个矩阵到第j个矩阵的最优解.s[][]记录从最优解断开位置.len为矩阵个数{ intn=len-1; for<inti=1;i<=n;i++>//初始化数组 for<intj=1;j<=n;j++> m[i][j]=0;for<intr=2;r<=n;r++> { for<inti=1;i<=n-r+1;i++>//行循环 { intj=i+r-1; m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//初始化s[i][j]=k;寻找最优解.以及最优解断开位置 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位置断开得到最优解 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<<"最优计算次数为"<<m[1][4]<<endl<<endl; system<"pause">; return0;}截图：4.二分搜索问题：对于给定的有序整数集a={6.9.13.15.25.33.45}.编写程序查找18与33.记录每次比较基准数。代码：#include<iostream>usingnamespacestd;voidbinary_search<inta[],intn,intke