算法之分支限界法实现.docx
《算法之分支限界法实现.docx》由会员分享，可在线阅读，更多相关《算法之分支限界法实现.docx（23页珍藏版）》请在冰点文库上搜索。
算法之分支限界法实现
实验5分支限界法实现
一、实验目标：
1. 熟悉分支限界法应用场景及实现的基本方法步骤；
2. 学会分支限界法的实现方法和分析方法：
二、实验内容
1.n后问题：
编程计算当n=1到8时解的个数，分别利用回溯法和分支限界法实现，比较并分析你的算法效率。
回溯法：
代码：
#include
#include
usingnamespacestd;
//法一：
迭代回溯
classQueen
{
friendintnQueen（int）;
private:
boolPlace（intk）;
voidBacktrack（intt）;
intn;//皇后个数
int*x;//当前解
intsum;//当前已找到的可行方案数
};
boolQueen:
:
Place（intk）
{
for（intj=1;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<<"共有"<system（"pause"）;
return0;
}
截图：
分支限界法：
代码：
#include
#include
usingnamespacestd;
classQueen
{
friendintnQueen（int）;
private:
boolPlace（intk）;
voidredu（intt）;
intn;//皇后个数
int*x;//当前解
intsum;//当前已找到的可行方案数
};
//剪枝函数
//判断当前状态是否合理，即皇后会不会互相攻击
boolQueen:
:
Place（intk）
{
for（intj=1;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<<"共有"<system（"pause"）;
return0;
}
截图：
2.单源最短路径问题：
如图求出从源顶点0到其它顶点的最短路径长度，比较贪心算法和分支限界法。
贪心算法（dijk）
代码：
#include
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{
inttemp=maxint;
intu=v;
for（intj=1;j<=n;j++）
{
//寻找距离最小而且不在S中的节点
if（!
s[j]&&（dist[j]{
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]=newdist;
prev[j]=u;
}
}
}
}
intmain（）
{
cout<<"请输入节点个数"<intn;
cin>>n;
cout<<"请输入起点（例如1,2,3。
。
。
）"<intv;
cin>>v;
int**c=newint*[n+1];
for（inti=1;i<=n;i++）
c[i]=newint[n+1];
cout<<"请输入各节点之间距离"<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<"<"<<"不可达"<else
cout<"<"<}
for（inti=1;i<=n;i++）
deletec[i];
deletec;
system（"pause"）;
return0;
}
截图：
分支限界法：
代码：
#include
usingnamespacestd;
#definemaxint10000
classMinHeapNode
{
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]=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（ciheap[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的顶点数
*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]//顶点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<<"请输入节点个数"<intn;
cin>>n;
cout<<"请输入起点（例如1,2,3。
。
。
）"<intv;
cin>>v;
int**c=newint*[n+1];
for（inti=1;i<=n;i++）
c[i]=newint[n+1];
cout<<"请输入各节点之间距离"<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<for（inti=1;i<=5;i++）
{
if（dist[i]==maxint）
cout<"<"<<"不可达"<else
cout<"<"<}
for（inti=1;i<=n;i++）
{
delete[]c[i];
}
deletec;
system（"pause"）;
return0;
}
截图：
3.矩阵连乘问题：
A1
A2
A3
A4
30*20
20*15
15*25
25*20
已知A1~A4矩阵及其维数求最优计算顺序。
代码：
#include
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{
intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if（t{
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"<}
intmain（）
{
intp[5]={30,20,15,25,20};
intlen=5;
cout<<"各矩阵为:
"<for（inti=1;i<=4;i++）
cout<<'M'<'<cout<int**m=newint*[len];
for（inti=1;im[i]=newint[len];
int**s=newint*[len];
for（inti=1;is[i]=newint[len];
matrixChain（p,m,s,len）;
traceback（s,1,4）;
cout<<"最优计算次数为"<system（"pause"）;
return0;
}
截图：
4.二分搜索问题：
对于给定的有序整数集a={6，9，13，15，25，33，45}，编写程序查找18与33，记录每次比较基准数。
代码：
#include
usingnamespacestd;
voidbinary_search（inta[],intn,intkey）
//a为按降序排列好了的数组，n为数组大小，key为查找的数字
{
intleft=0;//数组的首位置
intright=n-1;//数组的最后一个位置
while（left<=right）
{
intmid=left+（（right-left）>>1）;//用移位代替除以2可以提高效率
if（a[mid]>key）
{
cout<right=mid-1;
}
elseif（a[mid]{
cout<left=mid+1;
}
else
{
cout<cout<<"找到！
！
"<return;
}
}
//未找到
cout<<"此数不存在!
!
"<return;
}
intmain（）
{
inta[7]={6,9,13,15,25,33,45};
intn=7;
binary_search（a,7,18）;
cout<binary_search（a,7,33）;
system（"pause"）;
return0;
}
截图：
四、实验体会：
n后问题来说，回溯和分支限界法没有什么差别，因为回溯法，基于深度搜索，遍历每一种方案后，寻找一种最佳方法，而这题，是求次数，需要遍历每一种可行的方法。
而分支限界法，因为，最终每一种可行方案都是[1..n]的一个全排列，所以n后问题中，回溯和分支限界，差别不大，基本没有差别。
第二题贪心算法，主要就是借助新加入的节点，作为中间节点，搜索路径，看看有没有能够找到更近到其他未到节点的路径。
升级会员 