《回溯法(马周游问题)——实验报告》由会员分享，可在线阅读，更多相关《回溯法(马周游问题)——实验报告（14页珍藏版）》请在金锄头文库上搜索。
1、华南师范大学本科生实验报告姓名黎国庄 学号 院系计算机学院 专业计算机科学与技术 年级 2006级 班级2班 小组实验任务分工 独立完成 实验时间 2008 年6月 3 日实验名称 回溯法的应用 指导老师及职称 陈卫东老师 华南师范大学教务处编印实验课程：算法分析与设计 实验名称：回溯法的应用 （综设型实验）第一部分 实验内容1实验目标（1）熟悉使用回溯法求解问题的基本思路。（2）掌握回溯算法的程序实现方法。（3）理解回溯算法的特点。2. 实验任务（1）从所给定的题目中选择一题，使用回溯法求解之。（2）用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。（3）在Windows环境下
2、使用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）马开始的起点 输出：马从第一步到最后一步（64）的先后次序数字1v
4、（）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 vertical=-1,-2,-2,-1
6、,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;elsereturn false;第
7、三部分 实验结果与分析1. 实验数据及结果测试数据和运行输出及结果2. 实验分析及结论实验框架具体分析见回溯法的一般思路结论：马可以从任何一格出发恰好访问每个方格一次，并回到起始位置上。第四部分 心得与展望1. 自我评价及心得体会评价：整个算法的实现挺完整的体会：算法中的每个函数的功能尽量单一，调用函数时要注意是否修改了其他参数的值。一定要静下心去做。调试也很重要，从中能知道错在哪里。2. 展望据知用启发式搜索会更快一点，但现在我还是没有学会用这种方法解决这个问题。第五部分 附录1. 程序主要界面2. 源程序/SqStack.h#pragma once#define OK 1#define E
8、RROR 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 Pop(SqStack &
9、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.base=s.stacks
10、ize)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;/horse.cpp#inclu
11、de #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 legal(point
12、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,n-1,n-1); pr
13、intf(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+horizontali;p1.y=p.y+verticali;if(legal(p1)
