回溯法(马周游问题)实验报告.docVIP

华南师范大学本科生实验报告 姓名＿黎国庄＿ 学号 20062101247 院系＿计算机学院 专业＿计算机科学与技术 年级 2006级 班级＿2班 ＿ 小组实验任务分工＿ 独立完成 实验时间 2008 年＿6＿月 3 ＿日 实验名称 回溯法的应用 指导老师及职称 陈卫东老师 华南师范大学教务处编印 实验课程：算法分析与设计 实验名称：回溯法的应用 （综设型实验） 第一部分 实验内容 1．实验目标 （1） 熟悉使用回溯法求解问题的基本思路。 （2）掌握回溯算法的程序实现方法。 （3）理解回溯算法的特点。 2. 实验任务 （1）从所给定的题目中选择一题，使用回溯法求解之。 （2）用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。 （3）在Windows环境下使用C/C++语言编程实现算法。 （4）记录运行结果，包括输入数据，问题解答及运行时间。 （5）分析算法最坏情况下时间复杂度和空间复杂度。 （6）谈谈实验后的感想，包括关于该问题或类似问题的求解算法的建议。 3. 实验设备及环境 PC；C/C++等编程语言。 4. 实验主要步骤 根据实验目标，明确实验的具体任务； 设计求解问题的回溯算法，并编写程序实现算法； 设计实验数据并运行程序、记录运行的结果； 分析算法时空性能； 实验后的心得体会。 第二部分 问题及算法 问题描述 给出一个88的棋盘，一个放在棋盘某个位置上的马（规定马的走法为走“日”）是否可以好访问每个方格一次，并回到起始位置上？对于马所在其中一格时，它可以走的位置有以下8种情况： 马 所以对于每一个马所在的格子里，马可以走对应的8个方向。 用满8叉树，每一个子树对应马可跳的方向 当要走下一子树（跳下一格）时，该子树可走（还没有走过并且在棋盘里边），即沿该方向走下去，当不可以走，即回溯到上一步，选择另一方向往下走；当该子树的8个子棋都遍历完了（即8个方向都走过了），则回溯到它父亲那里。 重复一直做下去，到棋盘每个格子都走过一遍，而且回到出发点或者找不到路径即结束。算法如下： 输入：V（x,y）马开始的起点 输出：马从第一步到最后一步（64）的先后次序数字没有被穷举 6. x← X中的下一个元素；将x加入v 7． if v为最终解then set flag ← true，且从两个while循环退出 8. else if v是部分解then k ← k+1 {前进} 9. end while 10． 重置X，使得下一个元素排在第一位 11． K ← k-1 {回溯} 12．end while 13．if flag then output v 14．else output “no solution” 4. 算法实现的关键技巧 void exit(point p) 参数：point 功能：计算出下一步可能位置,按其各个位置下一个位置的和压栈到s[]中 算法描述：接受参数传来的值，按次序加上 int horizontal[]={2,1,-1,-2,-2,-1,1,2}; int vertical[]={-1,-2,-2,-1,1,2,2,1}; 再根据legal函数来判断是否合法（x(0~7),y(0~7)）是，则保存在point ap[]中，再按各自下一步的数目从大到小排序。最后，将ap[]中的点压栈。 int number(point p) 参数：point 功能：找出当前位置下一步的各种可能位置,计算可能之和 算法描述：接受参数传来的值，按次序加上 int horizontal[]={2,1,-1,-2,-2,-1,1,2}; int vertical[]={-1,-2,-2,-1,1,2,2,1}; 再根据legal函数来判断是否合法（x(0~7),y(0~7)）是，则加1并将值返回 void next(point p) 参数：point 功能：/找出各个位置并将其步数记录 算法描述：将其步数记录在board[][]的相应位置，并将这点压栈到s1,判断步数是否小于64，再根据这四个条件选择执行其中的一个，再递归调用next. bool legal(point p) 参数：point 功能：判断是否可行，合法（是否在棋盘上，是否走过） 算法描述 ：用这样的语句if((p.x=0)(p.xn)(p.yn)(p.y=0)(board[p.x][p.y]==0)) return true; else return false; 第三部分 实验结果与分析 实验数