实验四 回溯算法和分支限界法.docx
- 文档编号:7341288
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:19
- 大小:235.14KB
实验四 回溯算法和分支限界法.docx
《实验四 回溯算法和分支限界法.docx》由会员分享,可在线阅读,更多相关《实验四 回溯算法和分支限界法.docx(19页珍藏版)》请在冰点文库上搜索。
实验四回溯算法和分支限界法
实验四回溯算法和分支限界法
基本题一:
符号三角形问题
一、实验目的与要求
1、掌握符号三角形问题的算法;
2、初步掌握回溯算法;
二、实验题图
下面都是“-”。
下图是由14个“+”和14个“-”组成的符号三角形。
2个同号下面都是“+”,2个异号下面都是“-”。
+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+
在一般情况下,符号三角形的第一行有n个符号。
符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。
三、实验代码
#include
usingnamespacestd;
typedefunsignedcharuchar;
intsum;//表示满足要求的三角形个数
uchar**p;//符号存储空间;
charch[2]={'+','-'};
intn;//第一行符号总数
inthalf;
intcount;//用来计算‘-’的个数
voidBackTrace(intt)
{
if(t>n)
{
sum++;
cout<<"第"< "< for(inti=1;i<=n;i++) { for(intj=1;j { cout<<""; } for(j=1;j<=n-i+1;j++) { cout< } cout< } } else { for(inti=0;i<=1;i++) { p[1][t]=i;//确定第一行第t个的值; count+=i;//用来计算‘-’的个数; for(intj=2;j<=t;j++) { p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];//对于第一行大于等于2时确定后面从第2行开始增加的一 count+=p[j][t-j+1];//列中符号,计算‘-’个数; } if(count<=half&&(t*(t+1)/2-count)<=half)//约束条件; { BackTrace(t+1); } for(j=2;j<=t;j++)//回溯,判断另一种符号情况; { count-=p[j][t-j+1]; } count-=p[1][t]; } } } voidmain() { cout<<"请输入第一行符号的个数: "; cin>>n; count=0; sum=0; half=n*(n+1)/2; if(half%2==0) { half=half/2; p=newuchar*[n+1]; for(inti=0;i<=n;i++) { p[i]=newuchar[n+1]; memset(p[i],0,sizeof(uchar)*(n+1)); } BackTrace (1); for(i=0;i<=n;i++) { delete[]p[i]; } delete[]p; cout<<"满足要求的三角形符号共有: "< } 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;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); } } intmain(){ inti,j; printf("请输入旅行的节点数"); scanf("%d",&City_Size); for(i=0;i printf("请分别输入每个节点与其它节点的路程花费"); for(j=0;j scanf("%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<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验四 回溯算法和分支限界法 实验 回溯 算法 分支 限界