回溯算法之骑士旅行问题

回溯算法之骑士旅行问题

回溯法不同于纯暴力的瞎走，它通过不断的试探，层次变化，攻击问题，实现”保留现有信息“高效作战。

骑士旅行问题：

在N*N的国际象棋棋盘中有一个骑士在一角，问能否通过类似于中国象棋中马的走法走完所有的格子。所有的格子只能走一次。

最开始一看这个问题觉得，啊，这不就是个深度优先搜索吗，随便写写。

嗯，我的噩梦就这样开始了。处理好越界，访问格子，回溯等问题后，程序就是死循环！ （严格的说是时间极长的递归）

为什么呢？我检查了很长时间都没能发现错误（我经常会遇到千奇百怪的错误，无论是高级错误，低级错误，来者不拒），好吧，今晚我就陪你玩。这晚上的所有时间我就来研究这个recursion。

在痛苦的查看代码后，我有了这样的发现：

能正常工作的方向设置：

int dx[8]={2,1,-1,-2,-2,-1, 1, 2};int dy[8]={1,2, 2, 1,-1,-2, -2,-1};

其他设置：

/* 死循环int dx[8]={ 2, 2, 1, 1, -1, -1, -2, -2};int dy[8]={ 1, -1, 2, -2, 2, -2, -1, 1};*//* 死循环int dx[8] = { 2, 1, 1, 2, -2, -1,-1, -2 };int dy[8] = { 1, 2, -2, -1, -1, -2, 2, 1 };*//*顺时针象限-死循环int dx[8] = { 2, 1, 1, 2, -2, -1, -1, -2 };int dy[8] = { 1, 2, -2, -1, -1, -2, 2, 1 };*//*逆时针1,2先后位置变化-死循环int dx[8]={1, 2, -2, -1,-1,-2,2, 1};int dy[8]={2, 1, 1, 2, -2,-1,-1,-2};*/

嗯，就是这样。为什么有这样的结果呢？和正常工作的方向向量相比，随机向量没有规律，也正因为没有规律，带有了暴力色彩，效率变低。其他的方案按理说也能找出结果，但是时间花费是惊人的。想想，每一个格子有8个方向需要试探，对于8*8的棋盘一共有64-1个格子进行试探操作，那么总共的tests就该是

，啊，这太可拍了。怪不得我觉得是死循环。

代码：

#include #include #include using namespace std;int n;int vis[105][105];/*逆时针象限 OK *///int dx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };//int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };/* 死循环int dx[8]={ 2, 2, 1, 1, -1, -1, -2, -2};int dy[8]={ 1, -1, 2, -2, 2, -2, -1, 1};*//* 死循环int dx[8] = { 2, 1, 1, 2, -2, -1,-1, -2 };int dy[8] = { 1, 2, -2, -1, -1, -2, 2, 1 };*//*顺时针象限-死循环int dx[8] = { 2, 1, 1, 2, -2, -1, -1, -2 };int dy[8] = { 1, 2, -2, -1, -1, -2, 2, 1 };*//*逆时针1,2先后位置变化-死循环int dx[8]={1, 2, -2, -1,-1,-2,2, 1};int dy[8]={2, 1, 1, 2, -2,-1,-1,-2};*/int dx[8]={2,1,-1,-2,-2,-1, 1, 2};int dy[8]={1,2, 2, 1,-1,-2, -2,-1};bool ok(int x,int y){ if( x>=0 && x=0 && y>n){ memset(vis,0,sizeof(vis)); if(tour(0,0,1)){ printf("find one solution :\n"); for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。