算法綜合試驗

1、本科學生實驗（實踐）報告院 系：計算機學院岸實驗課程：算法分析與設計實驗項目：回溯法應用馬周游指導老師：曹霆懋開課時間：20112012年度第一學期專業(yè)：網(wǎng)絡工程班 級：09級7班學 生：奚偉杰學 號：20092100217華南師范大學教務處綜合試驗：回溯法應用馬周游實驗目標：（1）熟悉使用回溯法求解問題的基本思路。（2）掌握回溯算法的程序?qū)崿F(xiàn)方法。（3）理解回溯算法的特點。實驗任務：（1）從所給定的題目中選擇一題，使用回溯法求解之。（2）用文字來描述你的算法思路，包括解空間、限界函數(shù)、算法主要步驟等。（3）在Windows環(huán)境下使用C/C+語言編程實現(xiàn)算法。（4）記錄運行結(jié)果，包括輸入數(shù)據(jù)，

2、問題解答及運行時間。（5）分析算法最壞情況下時間復雜度和空間復雜度。（6）談談實驗后的感想，包括關(guān)于該問題或類似問題的求解算法的建議。實驗設備及環(huán)境：PC； C/C+等編程語言。實驗主要步驟：（1）根據(jù)實驗目標，明確實驗的具體任務；（2）設計求解問題的回溯算法，并編寫程序?qū)崿F(xiàn)算法；（3）設計實驗數(shù)據(jù)并運行程序、記錄運行的結(jié)果；（4）分析算法時空性能；（5）實驗后的心得體會實驗分析：先假設馬一開始位置為（x，y），對于當前所在位置（x，y），依次枚舉8個方向搜索，直到 找到一組可行解為止。使用剪枝有3處：第一、使用Warnsdorffs rule，枚舉當前解得時候 優(yōu)先選擇下一步可行步數(shù)最少的方

3、向；第二、若第一點中的方向存在不止一個，則優(yōu)先選擇 離中心位置較遠的方向；每次都從中心點開始出發(fā)，求出一條合法路徑后再平移映射回待求 路徑。實驗源代碼：#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;七、實驗數(shù)據(jù):4 1-1解座可 商個-W一 ， 壬到: 莆商38 曩用411解 桎仃坐可始個.初一 口士到:騎 s28 費用31 請己所情輸入騎士初始坐標=x =8 , :IX =/ =8:八、實驗數(shù)據(jù)分析：上面的數(shù)值排成8*8的方陣，每個代表