回溯法 马周游.doc

实验课程：算法分析与设计 实验名称：回溯法的应用 第一部分 实验内容1实验目标（1）熟悉使用回溯法求解问题的基本思路。（2）掌握回溯算法的程序实现方法。（3）理解回溯算法的特点。2. 实验任务（1）从所给定的题目中选择一题，使用回溯法求解之。（2）用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。（3）在Windows环境下使用C/C+语言编程实现算法。（4）记录运行结果，包括输入数据，问题解答及运行时间。（5）分析算法最坏情况下时间复杂度和空间复杂度。（6）谈谈实验后的感想，包括关于该问题或类似问题的求解算法的建议。3. 实验设备及环境PC；C/C+等编程语言。4. 实验主要步骤(1) 根据实验目标，明确实验的具体任务；(2) 设计求解问题的回溯算法，并编写程序实现算法；(3) 设计实验数据并运行程序、记录运行的结果；(4) 分析算法时空性能；(5) 实验后的心得体会。第二部分 问题及算法1. 问题描述问题1：在一个8*8的棋盘上，一个放在棋盘上某个位置的马是否可以恰好访问每个方格一次，并且回到起始位置上？2. 回溯法的一般思路深度优先搜索，若寻找到满足要求的解，则输出；否则推回上一层往下一个方向搜索。3. 求解问题的回溯算法描述对于当前所在位置（x，y），依次枚举8个方向搜索，直到找到一组可行解为止。使用剪枝有3处：第一、使用Warnsdorffs rule，枚举当前解得时候优先选择下一步可行步数最少的方向；第二、若第一点中的方向存在不止一个，则优先选择离中心位置较远的方向；每次都从中心点开始出发，求出一条合法路径后再平移映射回待求路径。4. 算法实现的关键技巧在棋盘较大的时候，使用递归会使得函数暴栈，故应当使用非递归方法实现。程序实现时应细心记录清楚当前状态在栈顶。第三部分 实验结果与分析#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 = 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(int x, int y) if (x n | 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 = 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; +i) nx = x + ixi; ny = y + iyi; if (!check(nx, ny) continue; cnt = 0; for (j = 0; j 8; +j) mx = nx + ixj; my = ny + iyj; if (check(mx, my) +cnt; tbtbn+ = Point(nx, ny, cnt); if (tbn) bntop = tbn; sort(tb, tb + tbn); tb = btop; i = +dirtop; vis tb0.x tb0.y = 1; a tb0.x tb0.y = top; ss+top = Node(tb0.x, tb0.y); dirtop = -1; else vis sstop.x sstop.y = 0; -top; else if (dirtop = bntop - 1) vis sstop.x sstop.y = 0; -top; else tb = btop; i = +dirtop; vis tbi.x tbi.y = 1; a tbi.x tbi.y = top; ss+top = Node(tbi.x, tbi.y); dirtop = -1; return 0;int main() clock_t begin, end; int i, j, bx, by, k; while (1) printf(请输入骑士初始坐标(1=x=8,1=y=8)：); scanf(%d %d, &bx, &by); while (bx 8 | by 8) printf(输入不合法！请重新输入骑士初始坐标(1=x=8,1=y=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 = 20) k = m - abxby; for (i = 1; i = n; +i) for (j = 1; j = n; +j) aij = (aij + k) % m + 1; printf(%4d, aij); puts(); puts(); return 0;1. 实验数据及结果2. 实验分析及结果首先先说明上面的数值的意思。上面的数值排成8*8的方阵，每个代表棋盘上的格子，而数字的大小表示骑士走到这个格子的次序，即骑士是第n步走到这个格子的。从上面是几个实验结果看，程序均能准确地找出一条路径