lab6-回溯算法设计与应用

实验六回溯算法设计与应用一．基本原理的概括DFS+剪枝（在状态空间树上作带剪枝的DFS搜索）剪枝：若搜索到某结点，其对应的部分解不满足解的约束条件且可断定以其为根的子树上不包含答案结点，则不搜索该子树，直接回到其父结点，继续DFS。利用回溯法可求问题的一个解，多个解，所有解，最优解，还可判断解的存在性。二．该类算法设计与实现的要点回溯法通常包含以下3个步骤：1)定义给定问题的解空间；2)确定并表示解的约束条件和其它的剪枝条件；3)结合剪枝深度优先搜索相应的状态空间树。注意：回溯法的一个特征是在搜索过程中动态的产生问题的状态空间树，任何时候只存根到当前搜索的结点的路径。三．实验目的和要求理解回溯法的基本原理，掌握回溯法设计的基本方法及步骤，并应用于具体问题的解决。四．实验内容(一)马的周游问题1.问题描述在nxn棋盘（有nxn个格点的棋盘）的某个格点上有一个中国象棋马，马走日字。求一条周游棋盘的路径，使得马能够从起始位置起沿着该路径每个格点恰好走一次最后回到出发位置。2.具体要求用回溯法解决该问题。输入一个正整数n，输出一个解，解的输出形式尽可能直观。3.设计与实现代码如下：#includeiostream#includeiomanip#includestdlib.h#includeWindows.husingnamespacestd;inlineintgood(intx,inty,ints[30][30],intn){if(x=0&&x=n-1&&y=0&&y=n-1&&s[y][x]==88)return1;elsereturn0;}voidmain(){intflag=1;while(flag=1){coutendl;cout1、开始求解endl2、退出endl;coutendl;cout请输入您的选项(12)endl;intcd;cout您的选项是:;cincd;switch(cd){case1:{enumroad{d11,d12,d21,d22,d31,d32,d41,d42};roadd[100];intm=0;intx=0,y=0;intp=0,q=0;ints[30][30];inti,j;intw=1;intnum=0;intn;cout输入棋盘的大小(不大于10):n=;cinn;for(i=0;in;++i)for(j=0;jn;j++)s[i][j]=88;cout原始棋盘的情况endl;for(i=0;in;i++){for(j=0;jn;j++)couts[i][j];coutendl;}cout输入马在棋盘中的位置:endl;coutx=;cinp;couty=;cinq;p--;q--;x=p;y=q;d[0]=d11;s[y][x]=1;do{if(d[m]==d11&&good(x+1,y-2,s,n)){x++;y=y-2;d[++m]=d11;s[y][x]=++w;num++;}elseif(d[m]==d12&&good(x+2,y-1,s,n)){x=x+2;y--;d[++m]=d11;s[y][x]=++w;num++;}elseif(d[m]==d21&&good(x+2,y+1,s,n)){x=x+2;y++;d[++m]=d11;s[y][x]=++w;num++;}elseif(d[m]==d22&&good(x+1,y+2,s,n)){x++;y=y+2;d[++m]=d11;s[y][x]=++w;num++;}elseif(d[m]==d31&&good(x-1,y+2,s,n)){x--;y=y+2;d[++m]=d11;s[y][x]=++w;num++;}elseif(d[m]==d32&&good(x-2,y+1,s,n)){x=x-2;y++;d[++m]=d11;s[y][x]=++w;num++;}elseif(d[m]==d41&&good(x-2,y-1,s,n)){x=x-2;y--;d[++m]=d11;s[y][x]=++w;num++;}elseif(d[m]==d42&&good(x-1,y-2,s,n)){x--;y=y-2;d[++m]=d11;s[y][x]=++w;num++;}else{while(d[m]==d42){m--;if(d[m]==d11){s[y][x]=88;--w;x--;y=y+2;}if(d[m]==d12){s[y][x]=88;--w;x=x-2;y++;}if(d[m]==d21){s[y][x]=88;--w;x=x-2;y--;}if(d[m]==d22){s[y][x]=88;--w;x--;y=y-2;}if(d[m]==d31){s[y][x]=88;--w;x++;y=y-2;}if(d[m]==d32){s[y][x]=88;--w;x=x+2;y--;}if(d[m]==d41){s[y][x]=88;--w;x=x+2;y++;}if(m!=0&&d[m]==d42){s[y][x]=88;--w;x++;y=y+2;}}d[m]=road(d[m]+1);}}while((m!=0||d[0]!=d42||good(x-1,y-2,s,n))&&m!=n*n-1||(p-x)*(p-x)+(q-y)*(q-y)!=5);cout马跳之后的情况(数字表示跳跃先后顺序)endl;for(i=0;in;i++){for(j=0;jn;j++)coutsetfill('0')setw(2)s[i][j];coutendl;}coutendl;coutendl;break;}case2:exit(1);break;default:cout选择错误！请重新选择！endl;break;}}}(二)寻宝问题1.问题描述对于某个m*n的字符串数组，相当于一个m行n列的平面形状的方格。里面S表示起点，W表示障碍，B表示可走（但是不一定可以通），X表示出口。对于起点S，有8个方向可以走，当然前提是在没有障碍的情况之下，其中可以分为单步走（onfoot）和跳步走（byjump）两种情况，从起点S开始追寻最短的出口路径count2。2．设计与实现#includeiostreamusingnamespacestd;intmain(){chara[10][10];intn,m,x,y,i,j,sx,sy,x1,y1,x2,y2,min,k[100],flag[10][10]={0};inttag[8][2]={-1,0,0,1,1,0,0,-1,-2,2,2,2,2,-2,-2,-2};cinn;while(n--){cinxy;for(i=0;ix;i++)for(j=0;jy;j++){cina[i][j];if(a[i][j]=='S'){x1=i;y1=j;}}min=32767;i=1;k[0]=0;k[i]=-1;flag[x1][y1]=1;while(i=1){while(k[i]7){k[i]=k[i]+1;x2=x1+tag[k[i]][0];y2=y1+tag[k[i]][1];if(x2=0&&x2x&&y2=0&&y2y&&a[x2][y2]!='W'&&imin){if(a[x2][y2]=='X'){if(imin)min=i;}elseif(flag[x2][y2]==0){flag[x2][y2]=1;;x1=x2;y1=y2;i++;k[i]=-1;}}}i--;flag[x1][y1]=0;x1=x1-tag[k[i]][0];y1=y1-tag[k[i]][1];}if(min32767)coutminendl;elsecoutNOANSWERendl;}return0;}