《回溯法(马周游问题)——实验报告》由会员分享,可在线阅读,更多相关《回溯法(马周游问题)——实验报告(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)