}
else
{
cout<<"不存在这样的三角形符号!
";
}
}
运行结果:
分析:
计算可行性约束需要O(n)时间,在最坏情况下有O(2^n)个结点需要计算可行性约束,故解符号三角形问题的回溯算法所需的计算时间为O(n2^n)。
基本题二:
0—1背包问题
一、实验目的与要求
1、掌握0—1背包问题的回溯算法;
2、进一步掌握回溯算法;
二、实验题:
给定n种物品和一背包。
物品i的重量是wi,其价值为vi,背包的容量为C。
问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
三、实验代码
#include
intn,c,bestp;//物品的个数,背包的容量,最大价值
intp[10000],w[10000],x[10000],bestx[10000];//物品的价值,物品的重量,x[i]暂存物品的选中情况,物品的选中情况
voidBacktrack(inti,intcp,intcw)
{//cw当前包内物品重量,cp当前包内物品价值
intj;
if(i>n)//回溯结束
{
if(cp>bestp)
{
bestp=cp;
for(i=0;i<=n;i++)bestx[i]=x[i];
}
}
else
for(j=0;j<=1;j++)
{
x[i]=j;
if(cw+x[i]*w[i]<=c)
{
cw+=w[i]*x[i];
cp+=p[i]*x[i];
Backtrack(i+1,cp,cw);
cw-=w[i]*x[i];
cp-=p[i]*x[i];
}
}
}
intmain()
{
inti;
bestp=0;
printf("请输入背包最大容量:
\n");
scanf("%d",&c);
printf("请输入物品个数:
\n");
scanf("%d",&n);
printf("请依次输入物品的重量:
\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("请依次输入物品的价值:
\n");
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
Backtrack(1,0,0);
printf("最大价值为:
\n");
printf("%d\n",bestp);
printf("被选中的物品依次是(0表示未选中,1表示选中)\n");
for(i=1;i<=n;i++)
printf("%d",bestx[i]);
printf("\n");
return0;
}
运行结果:
分析:
计算上界需要O(n)时间,在最坏情况下有O(2^n)个右儿子节点需要计算上界,故解0-1背包问题的回溯算法所需要的计算时间为O(n2^n)。
提高题一:
旅行商售货员问题的分支限界算法
一、实验目的与要求
1、掌握旅行商售货员问题的分支限界算法;
2、区分分支限界算法与回溯算法的区别,加深对分支限界法的理解。
二、实验题:
某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。
他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。
三、实验代码
#include
#include
usingnamespacestd;
//---------------------宏定义------------------------------------------
#defineMAX_CITY_NUMBER10//城市最大数目
#defineMAX_COST10000000//两个城市之间费用的最大值
//---------------------全局变量----------------------------------------
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;kpinnode->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;iminiOut[i]=MAX_COST;//初始化时每一个结点都不可达
for(j=0;jif(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;iBest_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;kpNode->x[k]=Best_Cost_Path[k];//第一个结点所保存的路径也就是初始化的路径
}
put(heap,*pNode);//入堆
while(pNode!
=NULL&&(pNode->s)//堆不空不是叶子
for(intk=0;kBest_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;iif(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_rcostfor(j=0;jtemp_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;kpNextNode->x[k]=temp_x[k];
}
put(heap,*pNextNode);
deletepNextNode;
}
}
}
}
pNode=RemoveMiniHeap(heap);
}
}
intmain(){
inti,j;
printf("请输入旅行的节点数");
scanf("%d",&City_Size);
for(i=0;iprintf("请分别输入每个节点与其它节点的路程花费");
for(j=0;jscanf("%d",&City_Graph[i][j]);
}
}
Traveler();
printf("最小花费""%d\n",Best_Cost);
return1;
}
运行结果:
提高题二:
用回溯法求解跳马问题
一、实验要求与目的
1、掌握回溯法的基本原理。
2、使用回溯法编程,求解跳马问题
二、实验内容
1、问题描述:
在N*N棋盘上有N2个格子,马在初始位置(X0,Y0),按照象棋中马走“日”的规则,使马走遍全部格子且每个格子仅经过一次。
编程输出马的走法。
2、给出算法描述。
编程实现,给出N=5,(X0,Y0)=(1,1)时的运行结果。
三、实验代码
#include
usingnamespacestd;
classTiaoma
{
public:
intN;
intx;
inty;
intA;
intCount;
intMap[6][6];
Tiaoma(intn,intx,inty):
N(n),x(x),y(y){A=1;Count=1;}
voidHorse(intx,inty);
voidPrint();
voidRoud();
};
voidTiaoma:
:
Horse(intx,inty)
{
if(1<=x-2&&y+1<=N&&Map[x-2][y+1]==0)
{
Map[x-2][y+1]=++A;
Count++;
Horse(x-2,y+1);
}
if(1<=x-1&&y+2<=N&&Map[x-1][y+2]==0)
{
Map[x-1][y+2]=++A;
Count++;
Horse(x-1,y+2);
}
if(x+1<=N&&y+2<=N&&Map[x+1][y+2]==0)
{
Map[x+1][y+2]=++A;
Count++;
Horse(x+1,y+2);
}
if(x+2<=N&&y+1<=N&&Map[x+2][y+1]==0)
{
Map[x+2][y+1]=++A;
Count++;
Horse(x+2,y+1);
}
if(x+2<=N&&1<=y-1&&Map[x+2][y-1]==0)
{
Map[x+2][y-1]=++A;
Count++;
Horse(x+2,y-1);
}
if(x+1<=N&&1<=y-2&&Map[x+1][y-2]==0)
{
Map[x+1][y-2]=++A;
Count++;
Horse(x+1,y-2);
}
if(1<=x-1&&1<=y-2&&Map[x-1][y-2]==0)
{
Map[x-1][y-2]=++A;
Count++;
Horse(x-1,y-2);
}
if(1<=x-2&&1<=y-1&&Map[x-2][y-1]==0)
{
Map[x-2][y-1]=++A;
Count++;
Horse(x-2,y-1);
}
}
voidTiaoma:
:
Print()
{
cout<<'\t';
for(inti1=1;i1<=N;i1++)
cout<for(inti=1;i<=N;i++)
{
cout<cout<
for(intj=1;j<=N;j++)
{
cout<