关于马踏棋盘的基本过程：国际象棋的棋盘为8*8的方格棋盘。现将"马"放在任意指定的方格中，按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次，*终使得"马"走遍棋盘的64个方格。深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次. （来自百度）
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是*好的选择。也就是说，不从整体*优上加以考虑，他所做出的仅是在某种意义上的局部*优解。贪心算法不是对所有问题都能得到整体*优解，但对范围相当广泛的许多问题他能产生整体*优解或者是整体*优解的近似解。（来自百度）
其中基于深度优先搜索的算法就是依据当前点找到下一个可能的点，然后对这个点进行深度优先搜索，然后依次递归，当出现条件不满足时，退回来，采用其他的路劲进行搜索，*后肯定能够得到对应的结果。实现的基本过程如下：
/*deepsearch to solve the horse chessproblem*/ #include #include #include #define ROWS 8 #define COLS 8
int chess[ROWS][COLS];
/*eight directions of x moved*/ const int x_move[] = {-2,-1,1,2,2,1,-1,-2}; /*eight directions of y moved*/ const int y_move[] = {1,2,2,1,-1,-2,-2,-1};
void print_matrix() { int i = 0,j = 0; for (i = 0; i < ROWS; ++ i) { for (j = 0; j < COLS; ++ j) { printf("%d",chess[i][j]); } printf(""); } }
/*find the next point*/ intnextxy(int *x,int *y,int count) { if(count > 7 && count < 0) return -1;switch(count) { case 0: /*check the conditions*/ if(*x + x_move[0] = 0 && *y + y_move[0]= 0 && chess[*x + x_move[0]][*y + y_move[0]] == 0) { *x += x_move[0]; *y += y_move[0]; break; } else/*failed*/ return 0; case 1: if(*x + x_move[1] = 0 && *y + y_move[1]= 0 && chess[*x + x_move[1]][*y + y_move[1]] == 0) { *x += x_move[1]; *y += y_move[1]; break; } else return 0; case 2: if(*x + x_move[2] = 0 && *y + y_move[2]= 0 && chess[*x + x_move[2]][*y + y_move[2]] == 0) { *x += x_move[2]; *y += y_move[2]; break; } else return 0; case 3: if(*x + x_move[3] = 0 && *y + y_move[3]= 0 && chess[*x + x_move[3]][*y + y_move[3]] == 0) { *x += x_move[3]; *y += y_move[3]; break; } else return 0; case 4: if(*x + x_move[4] = 0 && *y + y_move[4]= 0 && chess[*x + x_move[4]][*y + y_move[4]] == 0) { *x += x_move[4]; *y += y_move[4]; break; } else return 0; case 5: if(*x + x_move[5] = 0 && *y + y_move[5]= 0 && chess[*x + x_move[5]][*y + y_move[5]] == 0) { *x += x_move[5]; *y += y_move[5]; break; } else return 0; case 6: if(*x + x_move[6] = 0 && *y + y_move[6]= 0 && chess[*x + x_move[6]][*y + y_move[6]] == 0) { *x += x_move[6]; *y += y_move[6]; break; } else return 0; case 7: if(*x + x_move[7] = 0 && *y + y_move[7]= 0 && chess[*x + x_move[7]][*y + y_move[7]] == 0) { *x += x_move[7]; *y += y_move[7]; break; } else return 0; default: return 0; } return 1; } int deepsearch(int x,int y, int j) { /*save the value x,y*/ int x1 = x, y1 = y; int tag = 0, i = 0; /*save j on chess[x][y]*/ chess[x][y] = j;
/*recursion exit condition*/ if(j == COLS*ROWS) { return 1; } /*find the next point in eight directions*/ tag = nextxy(&x1,&y1,i); /*find the nextx,nexty */ while (tag == 0 && i < 7) { i ++; tag =nextxy(&x1,&y1, i); }
/*the nextxy be found*/ while(tag) { if(deepsearch(x1,y1,j+1)) return 1;
/*if failed, a new finding process */ x1 = x; y1 = y; i ++; tag = nextxy(&x1,&y1,i); while (tag == 0 && i < 7) { i ++; tag = nextxy(&x1,&y1,i); } } /*no direction can findnextpoint*/ if(tag == 0) chess[x][y] = 0; return 0; }
void main() { clock_t start = clock(); deepsearch(2,0,1); print_matrix(); int seconds = (clock()-start)/CLOCKS_PER_SEC;
printf("%d",seconds); return; }[page]
采用贪婪算法的实现，**应该设置一定的判断准则，然后根据设定的准则进行选择，在马踏棋盘中设定的准备是选择出路*少（至少为1）的一个方向为准则，能够实现马踏棋盘问题的解决。当然该问题为什么要选择出路*少，我暂时还不是很清楚。基本的实现如下：
#include #include #include
#define ROWS 8 #define COLS 8
/*axis i move matrix*/ const int iktmove[8] = {-2,-1,1,2,2,1,-1,-2}; /*axis j move matrix*/ const int jktmove[8] = {1,2,2,1,-1,-2,-2,-1};
int board[ROWS][COLS];
/*inital the matrix*/ voidmatrix_init(int matrix[][COLS],int rows,int cols) { int i, j; for(i = 0; i < rows ; ++ i) for (j = 0; j < cols ; ++ j) { matrix[i][j] = 0; } } /*print the matrix*/ void print_matrix(int matrix[][COLS],int rows,int cols) { int i,j; for(i = 0; i < rows; ++ i) { for(j = 0; j < cols; ++ j) printf("%d",matrix[i][j]); printf(""); } } /*find the index of min non-zeros positive*/ int minindex_in_matrix(int a[],int cols) { int i = 0,index = 0; int min = a[0]; for(i = 0 ; i0) { min = a[i]; index = i; break; } } for(i = index + 1; i 0 && min > a[i]) { min = a[i]; index = i; } } if(a[index] > 0) return index; return -1; } int maxindex_in_matrix(int a[],int cols) { int i = 0,index; int max ; for(i = 0 ; i0) { max = a[i]; index = i; break; } } for(i = index + 1; i 0 && max 0) return index; return -1; }
/**/ void warnsdorff_role(int matrix[][COLS],int rows,int cols,int start_i,int start_j) { int i,npos,m,min,j,nnpos;
int nexti[8] = {0,0,0,0,0,0,0,0}; intnextj[8] = {0,0,0,0,0,0,0,0}; int exit[8] = {0,0,0,0,0,0,0,0}; /*steps a*/ matrix_init(matrix,rows,cols); /*steps b*/matrix[start_i][start_j] = 1; /*steps c*/ for(m = 1; m < 64; ++ m) { /*steps d*/ npos = 0; for(i = 0; i < 8; ++ i) { /*ignore the point which doesn't satisfy the conditions*/ if( start_i + iktmove[i] = rows || start_j + jktmove[i] = cols ||matrix[start_i + iktmove[i]][start_j+jktmove[i]] > 0) { continue; } /*save the point which satisfy the conditions*/ nexti[npos] = start_i + iktmove[i];nextj[npos] = start_j + jktmove[i]; /*statistics how many point satisfy conditions*/ npos ++; } /*steps e*/ if(npos == 0) { printf("Can notfinishthegame!!,The steps of game can be %d",m); goto print; } /*steps e*/ if(npos == 1) { min = 0; goto set_nextpoint; } /*steps f*/ if(npos > 1) { /*calculate the possible way of the next next step */ for(i = 0; i < npos ; ++ i) { nnpos = 0; for(j = 0; j = 0 && nexti[i] + iktmove[j] = 0 && nextj[i] + jktmove[j] = 0) { goto set_nextpoint; } else /*failed*/ { printf("Can notfinishthe game!!,The steps of game can be %d",m); goto print; } } set_nextpoint: /*step g*/ /*set the next start point ofgame*/ start_i = nexti[min]; start_j =nextj[min]; matrix[start_i][start_j] = m+1; } print: /*step h*/ print_matrix(matrix,rows,cols); }
void main() { warnsdorff_role(board,ROWS,COLS,5,1); }
实现结果：当采用深度优先搜索算法的过程中发现当棋盘为8X8时，计算速度非常的慢，而当棋盘为5X5以后，计算速度非常的快速。说明算法存在一定的缺陷。而采用贪婪算法实现的速度非常的快，棋盘的大小对算法性能影响较小。
将矩阵改为5X5得到如下的结果：从结果中可以看见两种算法得到的结果存在一定的差异，但是都能解决马踏棋盘问题。
1、深度优先搜索算法：
2、贪婪算法：
百检网秉承“客户至上，服务为先，精诚合作，以人为本”的经营理念，始终站在用户的角度解决问题，为客户提供“一站购物式”的新奇检测体验，打开网站，像挑选商品一样简单，方便。打破行业信息壁垒，建构消费和检测机构之间高效的沟通平台
1stGB/T 38740-2020 实验动物 猴马尔堡病毒检测方法 现行
400-101-7153
15201733840
