回溯法 马周游

《回溯法 马周游》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验课程：算法分析与设计实验名称：回溯法的应用第一部分实验内容1．实验目标（1）熟悉使用回溯法求解问题的基本思路。（2）掌握回溯算法的程序实现方法。（3）理解回溯算法的特点。2.实验任务（1）从所给定的题目中选择一题，使用回溯法求解之。（2）用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。（3）在Windows环境下使用C/C++语言编程实现算法。（4）记录运行结果，包括输入数据，问题解答及运行时间。（5）分析算法最坏情况下时间复杂度和空间复杂度。（6）谈谈实验后的感想，包括关于

2、该问题或类似问题的求解算法的建议。3.实验设备及环境PC；C/C++等编程语言。4.实验主要步骤(1)根据实验目标，明确实验的具体任务；(2)设计求解问题的回溯算法，并编写程序实现算法；(3)设计实验数据并运行程序、记录运行的结果；(4)分析算法时空性能；(5)实验后的心得体会。第二部分问题及算法1.问题描述问题1：在一个8*8的棋盘上，一个放在棋盘上某个位置的马是否可以恰好访问每个方格一次，并且回到起始位置上？2.回溯法的一般思路深度优先搜索，若寻找到满足要求的解，则输出；否则推回上一层往下一

3、个方向搜索。3.求解问题的回溯算法描述对于当前所在位置（x，y），依次枚举8个方向搜索，直到找到一组可行解为止。使用剪枝有3处：第一、使用Warnsdorff'srule，枚举当前解得时候优先选择下一步可行步数最少的方向；第二、若第一点中的方向存在不止一个，则优先选择离中心位置较远的方向；每次都从中心点开始出发，求出一条合法路径后再平移映射回待求路径。4.算法实现的关键技巧在棋盘较大的时候，使用递归会使得函数暴栈，故应当使用非递归方法实现。程序实现时应细心记录清楚当前状态在栈顶。第三部分实验结果

4、与分析#include#include#include#includeusingnamespacestd;constintix[8]={1,2,2,1,-1,-2,-2,-1};constintiy[8]={2,1,-1,-2,2,1,-1,-2};intmidx,midy;structPoint{intx,y,c;Point(intxx=0,intyy=0,intcc=0):x(xx),y(yy),c(cc){}boolop

5、erator<(constPoint&b)const{if(c!=b.c)returncabs(b.x-midx)+abs(b.y-midy);}};structNode{intx,y;Node(intxx=0,intyy=0):x(xx),y(yy){}};templateinlinevoidswap(T&a,T&b){Tt=a;a=b;b=t;}intm,n;boolvis[10][10];inta[10]

6、[10];inlineboolcheck(intx,inty){if(x<1

7、

8、x>n

9、

10、y<1

11、

12、y>n)return0;if(vis[x][y])return0;return1;}boolfind(intx,inty){for(inti=0;i<8;++i)if(x+ix[i]==midx&&y+iy[i]==midy)return1;return0;}Nodess[10*10];Pointb[10*10][8],*tb;intdir[10*10],bn[10*10],top;booldfs

13、(intx,inty){inti,j,tbn,nx,ny,mx,my,cnt;top=1;vis[x][y]=1;a[x][y]=0;ss[top]=Node(x,y);dir[top]=-1;while(top){if(top==m&&find(ss[top].x,ss[top].y)){puts("已找到找到一个可行解！");return1;}if(top==m){vis[ss[top].x][ss[top].y]=0;--top;}elseif(dir[top]==-1){x=ss[top

14、].x;y=ss[top].y;tbn=0;tb=b[top];for(i=0;i<8;++i){nx=x+ix[i];ny=y+iy[i];if(!check(nx,ny))continue;cnt=0;for(j=0;j<8;++j){mx=nx+ix[j];my=ny+iy[j];if(check(mx,my))++cnt;}tb[tbn++]=Point(nx,ny,cnt);}if(tbn){bn[top]=tbn;sort(tb,tb+tbn);tb=b[top];i=++dir[t