算法之回溯法实现.docx

实验4回溯法实现
一、实验目标：
1.熟悉回溯法应用场景及实现的基本方法步骤；
2.学会回溯法的实现方法和分析方法：
二、实验内容
1.旅行售货员问题：
2.0-1背包问题：
对于n=5，C=10，vi={6,3,5,4,6}，wi={2,2，6,5,4}，计算xi及最优价值V。
分别利用动态规划、回溯法和分支限界法解决此问题，比较并分析这三种算法实现！

三、实验过程
1.源代码
旅行售货员问题（回溯法）：
#include<iostream>
usingnamespacestd;
classtravel//回溯
{
friendintTSP(int**,int[],int,int);
private:
voidBacktrack(inti);
intn,//顶点数
*x,
*bestx;
int**a,
cc,
bestc,
NoEdge;
};
voidSwap(inta,intb)
{
inttemp;
temp=a;
a=b;
b=temp;
return;
}
voidtravel::Backtrack(inti)
{
if(i==n)
{
if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&
(cc+a[x[n-1]][x[n]]+a[x[n]][1])<bestc||bestc==NoEdge)
{
for(intj=1;j<=n;j++)bestx[j]=x[j];
bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];
}
}
else
{
for(intj=i;j<=n;j++)
{
if(a[x[i-1]][j]!=NoEdge&&a[x[n]][1]!=NoEdge
&&(cc+a[x[i-1]][x[j]]<bestc||bestc==NoEdge))
{
swap(x[i],x[j]);
cc+=a[x[i-1]][x[i]];
Backtrack(i+1);
cc-=a[x[i-1]][x[i]];
swap(x[i],x[j]);
}
}
}
}
intTSP(int**a,intv[],intn,intNoEdge)
{
travelY;
Y.x=newint[n+1];
for(inti=1;i<=n;i++)
Y.x[i]=i;
Y.a=a;
Y.n=n;
Y.bestc=NoEdge;
Y.bestx=v;
Y.cc=0;
Y.NoEdge=NoEdge;
Y.Backtrack(2);
delete[]Y.x;
returnY.bestc;
}
intmain()
{
intconstmax=10000;
cout<<"请输入节点数:"<<endl;
intn;
cin>>n;
int*v=newint[n];//保存路径
intNoEdge=0;
int**p=newint*[max];
for(inti=0;i<n+1;i++)//生成二维数组
p[i]=newint[n+1];
cout<<"请依次输入各城市之间的路程："<<endl;
for(inti=0;i<n;i++)
for(intj=0;j<n;j++)
cin>>p[i+1][j+1];
cout<<"最短路径长度："<<TSP(p,v,4,1000)<<endl;
cout<<"路径为：";
for(inti=1;i<5;i++)
cout<<v[i]<<'';
cout<<endl;
return0;
}
运行截图：

旅行售货员问题（分支限界法）：
#include<iostream>
usingnamespacestd;
#defineMAX_CITY_NUMBER10//城市最大数目
#defineMAX_COST1000//两个城市之间费用的最大值
intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];//表示城市间边权重的数组
intCity_Size;//表示实际输入的城市数目
intBest_Cost;//最小费用
intBest_Cost_Path[MAX_CITY_NUMBER];
//结点
typedefstructNode{
intlcost;//优先级
intcc;//当前费用
intrcost;//剩余所有结点的最小出边费用的和
ints;//当前结点的深度，也就是它在解数组中的索引位置
intx[MAX_CITY_NUMBER];//当前结