文档章节

马周游问题非递归算法(不要求回到起点)

__August__
 __August__
发布于 2015/04/27 10:52
字数 3103
阅读 55
收藏 1

一、  原题中文大意;

对于一个8*8的棋盘,用下列的方式编号 

如果它走63步正好经过除起点外的其他位置各一次,这样一种走法则称马的周游路线,设计一个算法,从给定的起点出发,找出它的一条周游路线。马的走法是“日”字形路线。 

 Input

输入有若干行。每行一个整数N(1<=N<=64),表示马的起点。最后一行用-1表示结束,不用处理。 

 Output

对输入的每一个起点,求一条周游线路。对应地输出一行,有64个整数,从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。

  1. 二、  算法思想及解题用到的主要数据结构;

最本质的还是图的遍历的问题。这里使用深度优先搜索,不用广度优先是因为通常在寻找路径或者迷宫之类的题目中,都是探寻的问题,用深度优先比广度优先容易比较快地找到解。

涉及到回溯算法,即走到一个“死胡同”后,返回上一步,选择其他方向。这里就是到达一个不能往其他任何方向走的位置。

回溯和深度优先确定了,然后就是选择非递归算法,因为自己确实理解能力有限,递归的方法不能完全想明白。于是就自己思考加上查阅资料,使用非递归算法。

其中要提高效率,需要剪枝,即每次选择下一位置时,要通过一定筛选策略选择比较快速高效的一步。这里选择下一步位置具有最少可行步数的一步。

 

主要数据结构:

1、路径的树节点,使用自定义结构体,

struct Node {

            int x, y, num; // x, y 为矩阵坐标(0~7 0~7 num为对应的数值,由xy算出

         int neighbor[8]; // 下一步数组,每一个为对应的方向数组,在运算中使用坐标值,可以访问为0 反之为1

};

2、每一个位置对应的走“日”字的方向数组

         int dirx[8] = {2,1,-1,-2,-2,-1,1,2};  // x方向数组

int diry[8] = {-1,-2,-2,-1,1,2,2,1}; // y方向数组

   queue<node> states;

3、记录访问顺序的数组

int seq[64];  // 记录走的过程

   4、深度优先回溯中用到的栈

stack<Node> t_route;  // 树节点栈

5、标记数组

int board[8][8]; // 记录已访问的位置,已访问为 1 ,未访问为0

三、  详细解题思路

1、 对于每组数据,首先把board访问数组清零,step值置0,声明一个Node栈的t_route。

将起始位置初始化为一个Node结点,压栈。

2、进入一个while循环,循环判断条件是栈不为空。

取栈顶元素,seq数组中step下标位置为改栈顶元素的num值,记录路径, step++。如果此时step的值等于64,则说明走完了整个棋盘,退出循环。

同时,board数组也将栈顶元素对应坐标位设为1(已访问)

3、针对栈顶元素,遍历它的8个邻居节点,在可行的邻居节点中选择可行步数最少的一个。

找到后,用flag记录该邻居节点的下标值,未找到则flag为-1

  4、找到一个可行节点,将栈顶元素的neighbor数组对应下标位设为1(已访问)将该节点的值初始化(x,y,num,neighbor[8]),压栈。

     栈顶元素没有一个可行节点,将step减1,board数组对应下标位置设为0,出栈,回溯。

  5、判断step是否等于64,若是,则找到解,一次输出seq数组的值;反之,没有解,输出-1。

其中计算一个位置是否可以到达,调用函数canmove判断,判断条件为该位置坐标不越界合法并且board数组中对应下标位置为0。

  每个Node里面有二维数组的坐标值和本身数组,用一个转换函数xy_to_num,可以利用坐标值算出数值。

  计算下一步的可行步数时,调用函数next_neighbor计算,函数中用canmove函数计算。

四、  逐步求精算法描述(含过程及变量说明)

变量及函数说明

// 非递归DFS中树节点的结构体

struct Node {

         int x, y, num; // x, y 为矩阵坐标(0~7 0~7 num为对应的数值,由xy算出

         int neighbor[8]; // 下一步数组,每一个为对应的方向数组,在运算中使用坐标值,可以访问为0 反之为1

};                                      

 

int dirx[8] = {2,1,-1,-2,-2,-1,1,2};  // x方向数组

int diry[8] = {-1,-2,-2,-1,1,2,2,1}; // y方向数组

int seq[64];  // 记录走的过程

int step;    // 指向seq对应的下标进行赋值, 每走一步step + 1,回溯一次step - 1

int board[8][8]; // 记录已访问的位置,已访问为 1 ,未访问为0

int xy_to_num(int x, int y);     // 计算坐标对应数值,参数为坐标

bool canmove(int x, int y);      // 计算该位置是否可行,参数为坐标

int next_neighbor(int x, int y); // 计算下一位置的可行步数,参数为坐标

 

初始化起始位置结点,board数组,step

标记board数组,初始结点压栈;

While(栈不为空) {

   seq[step] = 栈顶元素的num

   board中栈顶元素设为已访问

   step++

   min = 8;  //初始化最小步数

   if ( step  == 64)

     找到路径,退出循环;

  遍历栈顶元素的邻居节点,计算邻居节点的可行步数

  If(找到一个邻居节点){

     栈顶元素的该邻居下标设为1,已访问。

     初始化下一步节点的x, y, num, neighbor[8]

     压栈

}

  Else {

     栈顶元素出栈;

     Board对应位置设置为 0

     Step--;

}

}

  If (step == 64)  // 找到解

输出seq数组

  Else

    输出“-1

五、  程序注释清单(重要过程的说明);

#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<cstring>
#include<stack>
using namespace std;
// 非递归DFS中树节点的结构体
struct Node {
         int x, y, num; // x, y 为矩阵坐标(0~7, 0~7 ,num为对应的数值,由x,y算出
         int neighbor[8]; // 下一步数组,每一个为对应的方向数组,在运算中使用坐标值,可以访问为0, 反之为1;
};                                      
 
int dirx[8] = {2,1,-1,-2,-2,-1,1,2};  // x方向数组
int diry[8] = {-1,-2,-2,-1,1,2,2,1}; // y方向数组
int seq[64];  // 记录走的过程
int step;    // 指向seq对应的下标进行赋值, 每走一步step + 1,回溯一次step - 1
int board[8][8]; // 记录已访问的位置,已访问为 1 ,未访问为0
int xy_to_num(int x, int y);     // 计算坐标对应数值,参数为坐标
bool canmove(int x, int y);      // 计算该位置是否可行,参数为坐标
int next_neighbor(int x, int y); // 计算下一位置的可行步数,参数为坐标
 
int main() {
         int N, min, flag, step, i, nextloc;
        
         while(scanf("%d", &N) && N != -1) {
           if (N >= 1 && N <= 64) {                         
                   stack<Node> t_route;  // 树节点栈
                   step = 0;
                   memset(board, 0, sizeof(int) * 64);
                   // 初始化根节点状态,压栈
                   Node ini;
                   ini.y = (N-1) % 8;
                   ini.x = (N-1) / 8;
                   ini.num = N;
                   for (i = 0; i < 8; i++) {
                            if(canmove(ini.x + dirx[i], ini.y + diry[i]))
                                     ini.neighbor[i] = 0;
                            else
                                     ini.neighbor[i] = 1;                                
                  }
                   t_route.push(ini);
 
                   while (!t_route.empty()) {
                            Node temp = t_route.top();
                            board[temp.x][temp.y] = 1; // 栈顶已访问
                            seq[step++] = temp.num; // 路径数组赋值
                            // 找到路径,退出
                            if (step == 64)
                                     break;
                            flag = -1; // 记录有最少可行步数的邻居节点的下标
                            min = 8;  // 最少步数
                            // 寻找最小步数的节点
                            for (i = 0; i < 8; i++) {
                                     if (temp.neighbor[i] == 0) {
                                               int t = next_neighbor(temp.x + dirx[i], temp.y + diry[i]);
                                               if (t <= min ) {
                                                        min = t;
                                                        flag = i;
                                               }
                                     }
                       }
                            // 找到最小步数的邻居节点
                            if (flag != -1) {
                                     temp.neighbor[flag] = 1; // 在栈顶结点中将该节点设置为已访问  
                                     // 初始化下一步节点的值,压栈
                                     Node newnode;
                                     newnode.x = temp.x + dirx[flag];
                                     newnode.y = temp.y + diry[flag];
                                     newnode.num = xy_to_num(newnode.x, newnode.y);
                           for (i = 0; i < 8; i++) {
                                   if(canmove(newnode.x + dirx[i], newnode.y + diry[i]))
                                          newnode.neighbor[i] = 0;
                                   else
                                          newnode.neighbor[i] = 1;                            
                          }
                                     t_route.push(newnode);
                            }
                            // 栈顶节点没有可以行走的下一位置,出栈,设为未访问
                            else  {
                                     t_route.pop();
                                     board[temp.x][temp.y] = 0;      
                                     step --; //路径数组下标值同步减1
                            }
                   }      
                   // output
                   if (step == 64) {
                            for( i = 0; i < 63; i++)
                                     printf("%d ", seq[i]);
                        printf("%d\n", seq[i]);
                   }      
                   else
                            printf("-1\n");     
           } // end of if (判断起始位置是否合法)
            else
                      printf("-1\n");
    }
         return 0;
}
 
int xy_to_num(int x, int y) {
         return x * 8 + y + 1;
}
bool canmove(int x, int y) {
         if(x >= 0 && x <= 7 && y >= 0 && y <= 7 && board[x][y] == 0)
                   return true;
         return false;
}
int next_neighbor(int x, int y) {
         int i, num;
         for (i = 0, num = 0; i < 8; i++)
                   if(canmove(x + dirx[i], y + diry[i]))
                            num++;
         return num;
}


  1. 六、  测试数据(5-10组有梯度的测试数据,要考虑边界条件)

1、考虑出发位置合法,位于角落位置时。

2、 考虑出发位置合法,位于边界位置时。

 

3、 考虑出发位置合法,位于中间位置时。

   

 

4、出发位置不合法:

5、调试,查看过程中的回溯信息,在回溯的代码中增加输出:

else  {

                                     t_route.pop();

                                     board[temp.x][temp.y] = 0;      

                                     step --; //路径数组下标值同步减1

                                     cout << "back "<<endl;

                          }

从 1-64 逐个调试,发现只有21有回溯信息:


七、  对时间复杂度,空间复杂度方面的分析、估算及程序优化的分析和改进.

时间复杂度:

 深度优先非递归实现的话,一样有最好和最坏的情况。对于n*n的棋盘。该题实际上是一颗n叉树。最好情况就是一次性就找到。每一步有8次循环寻找下一步节点,一共找n*n-1次。所以时间复杂度为On2)。最坏的话,不太好分析,因为不好从数学上证明一个明确的发生回溯的个数,大概就是每层都要回溯(不过实际问题中肯定没有每层都回溯),类似于满8叉数的深度优先遍历,则为O8n*n)。

 

  代码在sicily上耗时是0 s,还是比较理想,但是如果棋盘更大一点就不一定了,网上资料说如果只用一次剪枝,那么20*20的棋盘就比较慢了。

空间复杂度:

  这个空间复杂度就是树的深度,每个结点使用空间为常数,则为O(n*n)。

程序优化分析改进:

  1、一开始想用递归,可是一是因为自己不太明白,想不通递归过程,二是觉得递归不太好控制,于是用了非递归。

   2、剪枝方案只使用了最简单的一种,就是选择下一步可行位置最少的(Warnsdorff's rule。在网上查阅了一些资料,发现还有一些剪枝方法:

   1)使用Warnsdorff's rule剪枝后,如果可以优先选择的下一个位置不止一个,则优先选择离中心位置较远的位置作为下一步(即靠近边边的位置)。

通俗点理解,第一点的剪枝就是走那些位置可能走到机会比较小的,反正走到的机会小,那么先走完总是好的,要不然你兜一圈回来,还是要走这一个位置的。

第二点的剪枝就是走法尽量从边边走,然后是往中间靠。

2)第三点的剪枝,每次都从棋盘的中间点开始出发,然后求出一条合法路径后再平移映射回待求路径。

怎么理解呢?所谓马周游棋盘,最后还要回到起点。也就是在棋盘中找到一条哈密顿回路。那么不管你是从哪里开始的,最后都是会在这个哈密顿回路中的,那么选取的中点的位置也肯定是在这个回路上的。

最后,找到这个这个以中点为起点的哈密顿回路后,根据设定起点在这个回路中的序号,映射回以这个位置为起点的马周游路线即可。

  3、有一些变量上的细节问题。比如board数组因为只需用到两个值(0,1),所以可以为bool型,更节省空间。还有就是存储邻居节点的时候的数组也可以用bool型。

参考资料:

http://www.haogongju.net/art/2430132

http://huzhihang1103.blog.163.com/blog/static/19779176920135221340255/

https://class.coursera.org/ml/lecture/2

http://bbs.csdn.net/topics/370229313


© 著作权归作者所有

__August__
粉丝 13
博文 25
码字总数 27477
作品 0
广州
程序员
私信 提问
用Java如何实现:马踏棋盘算法(递归与分治策略)?

问题描述: 8×8的国际象棋棋盘上的一支马,恰好走过除起点外的其他63个位置各一次,最后回到起点。这条路线称为马的一条Hamilton算法。现将马放在国际象棋的8×8棋盘Board[0~7][0~7]的起点...

浅诉别辞
2017/05/19
295
0
二叉树的遍历,深度优先遍历和广度优先遍历

原文:http://www.cnblogs.com/joyang/p/4860441.html 二叉树的遍历: D:访问根结点,L:遍历根结点的左子树,R:遍历根结点的右子树。 给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一...

not_in_mountain
2017/09/29
0
0
数学、物理、网络、计算机等学科交叉创新(2)

> 信息论(香农) 香农第一定律:对于信源发出的所有信息设计一种编码,那么编码的平均长度一定大于该信息的信息熵,但同时香农指出,一定存在一种编码方式,似的编码的平均长度无限接近于它...

shareus
2017/10/10
0
0
GIS矢量数据化简:一种改进的道格拉斯-普克算法以及C++实现

既然今天有时间,就多写几篇博文算了,也为了明天出去玩好好放松一下。 GIS领域的同志都知道,传统的道格拉斯-普克算法都是递归实现。然而有时候递归的层次太深的话会出现栈溢出的情况。在此...

长平狐
2013/12/25
223
0
深度优先遍历 (DFS) 与广度优先遍历 (BFS)

前端小兵,不吝赐教 背景 看了很多前辈的分享后,笔者今天想整理下所理解的图的遍历算法。 图的遍历算法分为深度优先遍历与广度优先遍历,这两种算法从字面上了解的话,可以很清楚的知道。 ...

Wenson_Jay
07/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
28分钟前
3
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
今天
6
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
今天
4
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
今天
6
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部