《回溯法(马周游问题)——实验报告(共14页).doc》由会员分享，可在线阅读，更多相关《回溯法(马周游问题)——实验报告(共14页).doc（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上华南师范大学本科生实验报告姓名黎国庄 学号 院系计算机学院 专业计算机科学与技术 年级 2006级 班级2班 小组实验任务分工 独立完成 实验时间 2008 年6月 3 日实验名称 回溯法的应用 指导老师及职称 陈卫东老师 华南师范大学教务处编印实验课程：算法分析与设计 实验名称：回溯法的应用 （综设型实验）第一部分 实验内容1实验目标（1）熟悉使用回溯法求解问题的基本思路。（2）掌握回溯算法的程序实现方法。（3）理解回溯算法的特点。2. 实验任务（1）从所给定的题目中选择一题，使用回溯法求解之。（2）用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。（
2、3）在Windows环境下使用C/C+语言编程实现算法。（4）记录运行结果，包括输入数据，问题解答及运行时间。（5）分析算法最坏情况下时间复杂度和空间复杂度。（6）谈谈实验后的感想，包括关于该问题或类似问题的求解算法的建议。3. 实验设备及环境PC；C/C+等编程语言。4. 实验主要步骤(1) 根据实验目标，明确实验的具体任务；(2) 设计求解问题的回溯算法，并编写程序实现算法；(3) 设计实验数据并运行程序、记录运行的结果；(4) 分析算法时空性能；(5) 实验后的心得体会。第二部分 问题及算法1. 问题描述给出一个88的棋盘，一个放在棋盘某个位置上的马（规定马的走法为走“日”）是否可以恰好
3、访问每个方格一次，并回到起始位置上？2. 回溯法的一般思路对于马所在其中一格时，它可以走的位置有以下8种情况： 马 所以对于每一个马所在的格子里，马可以走对应的8个方向。 用满8叉树，每一个子树对应马可跳的方向 当要走下一子树（跳下一格）时，该子树可走（还没有走过并且在棋盘里边），即沿该方向走下去，当不可以走，即回溯到上一步，选择另一方向往下走；当该子树的8个子棋都遍历完了（即8个方向都走过了），则回溯到它父亲那里。 重复一直做下去，到棋盘每个格子都走过一遍，而且回到出发点或者找不到路径即结束。3. 求解问题的回溯算法描述算法如下： 输入：V（x,y）马开始的起点 输出：马从第一步到最后一步（
4、64）的先后次序数字1v （）2.flag false3k 14while k15 while X没有被穷举6. x X中的下一个元素；将x加入v7 if v为最终解then set flag true，且从两个while循环退出8. else if v是部分解then k k+1 前进9. end while10 重置X，使得下一个元素排在第一位11 K k-1 回溯12end while13if flag then output v14else output “no solution”4. 算法实现的关键技巧void exit(point p)参数：point 功能：计算出下一步可能位置,
5、按其各个位置下一个位置的和压栈到s中 算法描述：接受参数传来的值，按次序加上int horizontal=2,1,-1,-2,-2,-1,1,2;int vertical=-1,-2,-2,-1,1,2,2,1;再根据legal函数来判断是否合法（x(07),y(07)）是，则保存在point ap中，再按各自下一步的数目从大到小排序。最后，将ap中的点压栈。int number(point p)参数：point 功能：找出当前位置下一步的各种可能位置,计算可能之和算法描述：接受参数传来的值，按次序加上int horizontal=2,1,-1,-2,-2,-1,1,2;int vertica
6、l=-1,-2,-2,-1,1,2,2,1;再根据legal函数来判断是否合法（x(07),y(07)）是，则加1并将值返回void next(point p)参数：point 功能：/找出各个位置并将其步数记录算法描述：将其步数记录在board的相应位置，并将这点压栈到s1,判断步数是否小于64，再根据这四个条件选择执行其中的一个，再递归调用next.bool legal(point p)参数：point 功能：判断是否可行，合法（是否在棋盘上，是否走过）算法描述 ：用这样的语句if(p.x=0)&(p.xn)&(p.y=0)&(boardp.xp.y=0)return true;elser
7、eturn false;第三部分 实验结果与分析1. 实验数据及结果测试数据和运行输出及结果2. 实验分析及结论实验框架具体分析见回溯法的一般思路结论：马可以从任何一格出发恰好访问每个方格一次，并回到起始位置上。第四部分 心得与展望1. 自我评价及心得体会评价：整个算法的实现挺完整的体会：算法中的每个函数的功能尽量单一，调用函数时要注意是否修改了其他参数的值。一定要静下心去做。调试也很重要，从中能知道错在哪里。2. 展望据知用启发式搜索会更快一点，但现在我还是没有学会用这种方法解决这个问题。第五部分 附录1. 程序主要界面2. 源程序/SqStack.h#pragma once#define
8、OK 1#define ERROR 0#define OVERFLOW -2#define STACK_INIT_SIZE8#defineSTACKINCREMENT 57typedef struct int x,y;point;typedef point SElemType;typedef int Status;typedef struct SElemType * base;SElemType * top;int stacksize;SqStack;Status InitStack(SqStack &s);Status Push(SqStack &s,SElemType e);Status
9、Pop(SqStack &s,SElemType &e);/SqStack.cpp#include SqStack.h#include #include Status InitStack(SqStack &s)s.base = ( SElemType * )malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!s.base) return OVERFLOW;s.top = s.base;s.stacksize = STACK_INIT_SIZE;return OK;Status Push(SqStack &s,SElemType e)if (s.top-s.
10、base=s.stacksize)s.base=(SElemType * )realloc(s.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType);if (!s.base)return OVERFLOW;s.top = s.base + s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+ = e;return OK;Status Pop(SqStack &s,SElemType &e)if(s.top=s.base)return ERROR;e = *-s.top;return OK;/ho
11、rse.cpp#include #include #include SqStack.hint horizontal=2,1,-1,-2,-2,-1,1,2;int vertical=-1,-2,-2,-1,1,2,2,1;int board88=0;int step=1;SqStack s65;SqStack s1;#define n 8void exit(point p);/计算出下一步可能位置，按其各个位置下一个位置的和压栈到s中int number(point p);/找出当前位置下一步的各种可能位置,计算可能之和void next(point p);/找出各个位置并将其步数记录bool
12、 legal(point p);/判断是否可行void main()point p; printf(n);printf(*欢迎使用回溯法解决马周游问题*nn);printf(*下面请输入马的初始位置坐标 x(0-%d),y(0-%d):n,n-1,n-1); printf(n);scanf(%d%d,&p.x,&p.y); printf(n);printf(周游路线如下:n);printf(n);while(!(p.x=0)&(p.xn)&(p.y=0)printf(输入不合法,请重新输入!n); printf(n);printf(请重新输入马的初始位置 x(0-%d!),y(0-%d!):n
13、,n-1,n-1); printf(n);scanf(%d%d,&p.x,&p.y); printf(n); printf(周游路线如下:n); printf(n);InitStack(s1);/初始化栈next(p);for (int i=0;in;i+)/打印棋盘for (int j=0;jn;j+)printf(%5d,boardij);printf(n); printf(此次周游完毕!n); main();int number(point p)/找出当前位置下一步的各种可能位置,计算可能之和point p1;int j=0;for(int i=0;i8;i+)p1.x=p.x+hori
14、zontali;p1.y=p.y+verticali;if(legal(p1)j+;return (j);void next(point p)/找出各个位置并将其步数记录point p1,p2;InitStack(sstep);boardp.xp.y=step;Push(s1,p);if(stepn*n)exit(p);Pop(sstep,p2);if (sstep.base=sstep.top&number(p2)=0)&step!=n*n-1)Pop(s1,p1);boardp1.xp1.y=0;-step;while (sstep.base=sstep.top)Pop(s1,p1);bo
15、ardp1.xp1.y=0;step-; Pop(sstep,p2);step+;next(p2);/退栈，悔棋else if(number(p2)=0&sstep.base!=sstep.top)Pop(sstep,p2);step+;next(p2);else if (number(p2)!=0&sstep.base=sstep.top)step+;next(p2);else step+;next(p2);void exit(point p)/计算出下一步可能位置，按其各个位置下一个位置的和压栈到s中point temp; point p1; int j=0; point ap8=0; f
16、or(int i=0;i8;i+) p1.x=p.x+horizontali; p1.y=p.y+verticali; if(legal(p1) apj=p1; j+;/将下一步的可能位置储存在ap中for(int count=0;countnumber(p)-1;count+) /使用冒泡法，对下一步的八个规则的从大到小排序 for(int k=0;knumber(p)-1;k+)if (number(apk)number(apk+1)temp=apk+1;apk+1=apk;apk=temp; for (int t=0;t=0)&(p.xn)&(p.y=0)&(boardp.xp.y=0)return true;elsereturn false;参考文献1 算法设计技巧与分析 沙特 M.H.Alsuwaiyel著 （电子工业出版社）2 数据结构与算法 黄定 黄煜廉 刘贤兴编 （广东科技出版社）专心-专注-专业