算法之回溯法实现.docx
《算法之回溯法实现.docx》由会员分享，可在线阅读，更多相关《算法之回溯法实现.docx（33页珍藏版）》请在冰点文库上搜索。
实验4回溯法实现
一、实验目标：
1.熟悉回溯法应用场景及实现的基本方法步骤；
2.学会回溯法的实现方法和分析方法：
二、实验内容
1.旅行售货员问题：
当结点数为4，权重矩阵为0110239429340660，求最优路径及开销。
2.0-1背包问题：
对于n=5，C=10，vi={6,3,5,4,6}，wi={2,2，6,5,4}，计算xi及最优价值V。
分别利用动态规划、回溯法和分支限界法解决此问题，比较并分析这三种算法实现！
三、实验过程
1.源代码
旅行售货员问题（回溯法）：
#include
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]） {
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]] {
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<<"请输入节点数:
"< intn;
cin>>n;
int*v=newint[n];//保存路径
intNoEdge=0;
int**p=newint*[max];
for（inti=0;i p[i]=newint[n+1];
cout<<"请依次输入各城市之间的路程：
"< for（inti=0;i for（intj=0;j cin>>p[i+1][j+1];
cout<<"最短路径长度：
"< cout<<"路径为：
";
for（inti=1;i<5;i++）
cout< cout< return0;
}
运行截图：
旅行售货员问题（分支限界法）：
#include
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];//当前结点对应的路径
structNode*pNext;//指向下一个结点
}Node;
//堆
typedefstructMiniHeap{
Node*pHead;//堆的头
}MiniHeap;
//初始化
voidInitMiniHeap（MiniHeap*pMiniHeap）{
pMiniHeap->pHead=newNode;
pMiniHeap->pHead->pNext=NULL;
}
//入堆
voidput（MiniHeap*pMiniHeap,Nodenode）{
Node*next;
Node*pre;
Node*pinnode=newNode;//将传进来的结点信息copy一份保存
//这样在函数外部对node的修改就不会影响到堆了
pinnode->cc=node.cc;
pinnode->lcost=node.lcost;
pinnode->pNext=node.pNext;
pinnode->rcost=node.rcost;
pinnode->s=node.s;
pinnode->pNext=NULL;
for（intk=0;k pinnode->x[k]=node.x[k];
}
pre=pMiniHeap->pHead;
next=pMiniHeap->pHead->pNext;
if（next==NULL）{
pMiniHeap->pHead->pNext=pinnode;
}
else{
while（next!
=NULL）{
if（（next->lcost）>（pinnode->lcost））{//发现一个优先级大的，则置于其前面
pinnode->pNext=pre->pNext;
pre->pNext=pinnode;
break;//跳出
}
pre=next;
next=next->pNext;
}
pre->pNext=pinnode;//放在末尾
}
}
//出堆
Node*RemoveMiniHeap（MiniHeap*pMiniHeap）{
Node*pnode=NULL;
if（pMiniHeap->pHead->pNext!
=NULL）{
pnode=pMiniHeap->pHead->pNext;
pMiniHeap->pHead->pNext=pMiniHeap->pHead->pNext->pNext;
}
returnpnode;
}
//分支限界法找最优解
voidTraveler（）{
inti,j;
inttemp_x[MAX_CITY_NUMBER];
Node*pNode=NULL;
intminiSum;//所有结点最小出边的费用和
intminiOut[MAX_CITY_NUMBER];
//保存每个结点的最小出边的索引
MiniHeap*heap=newMiniHeap;//分配堆
InitMiniHeap（heap）;//初始化堆
miniSum=0;
for（i=0;i miniOut[i]=MAX_COST;//初始化时每一个结点都不可达
for（j=0;j if（City_Graph[i][j]>0&&City_Graph[i][j] //从i到j可达，且更小
miniOut[i]=City_Graph[i][j];
}
}
if（miniOut[i]==MAX_COST）{//i城市没有出边
Best_Cost=-1;
return;
}
miniSum+=miniOut[i];
}
for（i=0;i Best_Cost_Path[i]=i;
}
Best_Cost=MAX_COST;//初始化的最优费用是一个很大的数
pNode=newNode; //初始化第一个结点并入堆
pNode->lcost=0;//当前结点的优先权为0也就是最优
pNode->cc=0;//当前费用为0（还没有开始旅行）
pNode->rcost=miniSum;//剩余所有结点的最小出边费用和就是初始化的miniSum
pNode->s=0;//层次为0
pNode->pNext=NULL;
for（intk=0;k pNode->x[k]=Best_Cost_Path[k];//第一个结点所保存的路径也就是初始化的路径
}
put（heap,*pNode）;//入堆
while（pNode!
=NULL&&（pNode->s） //堆不空不是叶子
for（intk=0;k Best_Cost_Path[k]=pNode->x[k];//将最优路径置换为当前结点本身所保存的
}
/*
** pNode结点保存的路径中的含有这条路径上所有结点的索引
**x路径中保存的这一层结点的编号就是x[City_Size-2]
** 下一层结点的编号就是x[City_Size-1]
*/
if（（pNode->s）==City_Size-2）{//是叶子的父亲
intedge1=City_Graph[（pNode->x）[City_Size-2]][（pNode->x）[City_Size-1]];
intedge2=City_Graph[（pNode->x）[City_Size-1]][（pNode->x）[0]];
if（edge1>=0&&edge2>=0&&（pNode->cc+edge1+edge2） //edge1-1表示不可达
//叶子可达起点费用更低
Best_Cost=pNode->cc+edge1+edge2;
pNode->cc=Best_Cost;
pNode->lcost=Best_Cost;//优先权为Best_Cost
pNode->s++; //到达叶子层
}
}
else{ //内部结点
for（i=pNode->s;i if（City_Graph[pNode->x[pNode->s]][pNode->x[i]]>=0）{//可达
//pNode的层数就是它在最优路径中的位置
inttemp_cc=pNode->cc+City_Graph[pNode->x[pNode->s]][pNode->x[i]];
inttemp_rcost=pNode->rcost-miniOut[pNode->x[pNode->s]];
//下一个结点的剩余最小出边费用和
//等于当前结点的rcost减去当前这个结点的最小出边费用
if（temp_cc+temp_rcost for（j=0;j temp_x[j]=Best_Cost_Path[j];
}
temp_x[pNode->x[pNode->s+1]]=Best_Cost_Path[i];
//将当前结点的编号放入路径的深度为s+1的地方
temp_x[i]=Best_Cost_Path[pNode->s+1];
//将原路//径中的深度为s+1的结点编号放入当前路径的
//相当于将原路径中的的深度为i的结点与深度W为s+1的结点交换
Node*pNextNode=newNode;
pNextNode->cc=temp_cc;
pNextNode->lcost=temp_cc+temp_rcost;
pNextNode->rcost=temp_rcost;
pNextNode->s=pNode->s+1;
pNextNode->pNext=NULL;
for（intk=0;k pNextNode->x[k]=temp_x[k];
}
put（heap,*pNextNode）;
deletepNextNode;
}
}
}
}
pNode=RemoveMiniHeap（heap）;
}
for（intk=0;k Best_Cost_Path[k]=temp_x[k];
}
}
intmain（）{
cout<<"请输入节点数：
"< cin>>City_Size;
cout<<"请依次输入各城市之间的距离"< for（inti=0;i for（intj=0;j {
cin>>City_Graph[i][j];
if（City_Graph[i][j]==0）
City_Graph[i][j]=1000;
}
Traveler（）;
cout<<"最短路径长度：
"< cout<<"路径为：
";
for（inti=0;i<4;i++）
cout< return0;
}
运行截图：
0-1背包问题（动态规划）：
#include
#include
usingnamespacestd;
voidknapsack（intv[],int*w,intc,intn,int**m）{
intjmax=min（w[n]-1,c）;//1）仅可选物品n时，容量为j的子问题的最优值
for（intj=0;j<=jmax;j++）m[n][j]=0;//注意j为整数
for（intj=w[n];j<=c;j++）m[n][j]=v[n];
for（inti=n-1;i>0;i--）{//2）逐步增加物品数至n及容量至c
jmax=min（w[i]-1,c）;//仅可选物品i时，容量为j的子问题的最优值
for（intj=0;j<=jmax;j++）m[i][j]=m[i+1][j];
for（intj=w[i];j<=c;j++）m[i][j]=max（m[i+1][j],m[i+1][j-w[i]]+v[i]）;
}
m[1][c]=m[2][c];//处理物品1，最后一件的边界情况
if（c>=w[1]）m[1][c]=max（m[1][c],m[2][c-w[1]]+v[1]）;
}
voidtraceback（int**m,int*w,intc,intn,int*x）
{
for（inti=1;i if（m[i][c]==m[i+1][c]）
x[i]=0;//二者相等说明物品i不装入
else{
x[i]=1;
c=c-w[i];
}
x[n]=（m[n][c]）?
1:
0;
}
}
intmax（inta,intb）
{
returna>b?
a:
b;
}
intmin（inta,intb）
{
returna>b?
b:
a;
}
intmain（）
{
intn,c;
cout<<"请输入物品数：
"< cin>>n;
cout<<"请输入背包容量：
"< cin>>c;
int*v=newint[n+1];
int*w=newint[n+1];
cout<<"请输入物品重量数组：
"< for（inti=1;i cin>>w[i];
cout<<"请输入物品价值数组：
"< for（inti=1;i cin>>v[i];
int**p=newint*[n+1];//子问题最优解
for（inti=1;i p[i]=newint[c+1];
int*x=newint[n+1];
knapsack（v,w,c,n,p）;
traceback（p,w,c,n,x）;
cout<<"m（i,j）:
"< for（inti=5;i>0;i--）
{
for（intj=0;j<11;j++）
cout<（2）< cout< }
cout<<"xi=";
for（inti=1;i<6;i++）
cout< cout< cout<<"V="< for（inti=1;i deletep[i];
deletep;
deletev,w;
return0;
}
运行截图：
0-1背包问题（回溯法）
#include
usingnamespacestd;
intn,c,bestp;//物品的个数，背包的容量，最大价值
intp[10000],w[10000],x[10000],bestx[10000];//物品的价值，物品的重量，x[i]暂存物品的选中情况,物品的选中情况
voidBacktrack（inti,intcp,intcw）
{//cw当前包内物品重量，cp当前包内物品价值
升级会员 