算法综合试验

1、本科学生实验（实践）报告院 系：计算机学院岸实验课程：算法分析与设计实验项目：回溯法应用马周游指导老师：曹霆懋开课时间：20112012年度第一学期专业：网络工程班 级：09级7班学 生：奚伟杰学 号：20092100217华南师范大学教务处综合试验：回溯法应用马周游实验目标：（1）熟悉使用回溯法求解问题的基本思路。（2）掌握回溯算法的程序实现方法。（3）理解回溯算法的特点。实验任务：（1）从所给定的题目中选择一题，使用回溯法求解之。（2）用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。（3）在Windows环境下使用C/C+语言编程实现算法。（4）记录运行结果，包括输入数据，

2、问题解答及运行时间。（5）分析算法最坏情况下时间复杂度和空间复杂度。（6）谈谈实验后的感想，包括关于该问题或类似问题的求解算法的建议。实验设备及环境：PC； C/C+等编程语言。实验主要步骤：（1）根据实验目标，明确实验的具体任务；（2）设计求解问题的回溯算法，并编写程序实现算法；（3）设计实验数据并运行程序、记录运行的结果；（4）分析算法时空性能；（5）实验后的心得体会实验分析：先假设马一开始位置为（x，y），对于当前所在位置（x，y），依次枚举8个方向搜索，直到 找到一组可行解为止。使用剪枝有3处：第一、使用Warnsdorffs rule，枚举当前解得时候 优先选择下一步可行步数最少的方

3、向；第二、若第一点中的方向存在不止一个，则优先选择 离中心位置较远的方向；每次都从中心点开始出发，求出一条合法路径后再平移映射回待求 路径。实验源代码：#include #include #include #include using namespace std;const int ix8 = (1, 2, 2, 1, -1, -2, -2, -1;const int iy8 = (2, 1, -1, -2, 2, 1, -1, -2;int midx, midy;struct Point (int x, y, c;Point(int xx = 0, int yy = 0, int cc =

4、0):x(xx), y(yy), c(cc) (bool operator (const Point & b) const (if (c != b.c) return c abs(b.x - midx) + abs(b.y - midy);struct Node (int x, y;Node(int xx = 0, int yy = 0):x(xx), y(yy) (;template inline void swap(T & a, T & b)(T t = a; a = b; b = t;int m, n;bool vis1010;int a1010;inline bool check(in

5、t x, int y)(if (x n II y n) return 0;if (visxy) return 0;return 1;bool find(int x, int y)(for (int i = 0; i 8; +i)if (x + ixi = midx & y + iyi = midy)return 1;return 0;Node ss10 * 10;Point b10 * 108, *tb;int dir10 * 10, bn10 * 10, top;bool dfs(int x, int y) (int i, j, tbn, nx, ny, mx, my, cnt;top =

6、1;visxy = 1;axy = 0;sstop = Node(x, y);dirtop = -1;while (top) (if (top = m & find(sstop.x, sstop.y) ( puts(”已找到找到一个可行解！”)； return 1;if (top = m) (vis sstop.x sstop.y = 0;-top; else if (dirtop = -1) (x = sstop.x; y = sstop.y;tbn = 0;tb = btop;for (i = 0; i 8 II by v 1 II by 8) (printf(输入不合法！请重新输入骑士初

7、始坐标(1v=xv=8,1v=yv=8)：);scanf(%d %d, &bx, &by);n = 8;midx = midy = n / 2;begin = clock();memset(vis, 0, sizeof(vis);m = n * n;dfs(midx, midy);end = clock();printf(所用时间：.0lfmsn”, double(end - begin);if (n v= 20) (k = m - abxby;for (i = 1; i v= n; +i) (for (j = 1; j v= n; +j) (aij = (aij + k) % m + 1;printf(%4d”, aij);puts();return 0;七、实验数据:4 1-1解座可 商个-W一 ， 壬到: 莆商38 曩用411解 桎仃坐可始个.初一 口士到:骑 s28 费用31 请己所情输入骑士初始坐标=x =8 , :IX =/ =8:八、实验数据分析：上面的数值排成8*8的方阵，每个代表