devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

马踏棋盘、骑士巡逻问题 - 深度优先搜索和贪心法_马踏棋盘背景

作者：我家小花儿 | 2024-05-15 15:10:58

赞

踩

马踏棋盘背景

【参考1：马踏棋盘问题 — 深搜和贪心算法】(http://blog.csdn.net/u011718609/article/details/60873403)
【参考2：Wiki百科-骑士巡逻】(https://zh.wikipedia.org/wiki/騎士巡邏)
【参考3：Wiki百科-贪心法】(https://zh.wikipedia.org/wiki/贪心法)
【参考4：贴吧某大神对马踏棋盘的见解】(http://tieba.baidu.com/p/2576982396?pn=1)
【参考5：油管Knight’s Tour - Numberphile】(https://www.☺youetuebe☺.com/watch?v=ab_dY3dZFHM)
###1.背景：
已知的最早的骑士巡逻问题可以追溯到九世纪的古印度恰图兰卡。
欧拉是最早研究骑士巡逻的数学家中的一员，而H. C. von Warnsdorff在1823年提出了第一个系统化解决骑士巡逻问题的方法–Warnsdorff规则。
在20世纪，一批乌力波的作家将这个问题用在了其它的地方。最明显的例子：乔治·佩雷克的小说Life: A User’s Manual的章节顺序就是按照10×10棋盘的骑士巡逻路径来编排的。在2010年国际象棋世界冠军对抗赛的第六场比赛中，棋手阿南德连续13次移动骑士（使用了两个骑士），在线评论员打趣地说阿南德试图在游戏过程中解决了骑士巡逻问题。
###2.条件：
马踏棋盘(骑士巡逻)是指在按照中国象棋马的规定走法(国际象棋中骑士的规定走法)走遍整个棋盘的每一个方格，而且每个网格只能够经过一次。马踏棋盘要求是所有位置都要走一遍，而骑士巡逻有两种情况，能够回到最初位置的叫做“封闭巡逻”，不能回到最初位置的称为“开巡逻”，开循环结果与马踏棋盘相同。
马可移动的位置：这里写图片描述
一种“开巡逻”情况：这里写图片描述一种“封闭巡逻”情况：这里写图片描述
###3.解法一 - DFS深度优先搜索：
此方法类似八皇后问题，采用回溯法，就是一遍一遍尝试，如果不行则回溯到上一次，继续进行其他尝试，当然这个算法时间复杂度很高，从Wiki百科知“对于8*8棋盘，一共有26,534,728,821,064种封闭巡逻，但是到底有多少种开巡逻仍然未知”，所以一般情况求出一个解即停止求解过程

#include <iostream>
#include <iomanip>
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "time.h"

using namespace std;

int count = 0;
void OutputToTxt(int (*chess)[8])
{
    FILE *fp = fopen("abc.txt","w");
    for(int i = 0; i<8; i++)
    {
        for(int j = 0; j<8; j++)
        {
            fprintf(fp,"%-2d ",chess[i][j]);
        }
        fprintf(fp,"\n");
    }
    fclose(fp);
}
void Horse_Chess(int (*chess)[8], int x, int y, int cnt)
{
    if(count >= 1) return; // 找到1种情况就退出
    if(x&0xFFFFFFF8 || y&0xFFFFFFF8) return; // 越界返回
    if(chess[x][y] == 0)
    {
        chess[x][y] = cnt; // 此位置设置走马的序号
        if(cnt >= 64)
        {
            OutputToTxt(chess); // 输出到文件
            count++; // 可能性+1
            return;
        }
        /* 以下是8种可能的情况： */
        Horse_Chess(chess,x+1,y+2,cnt+1);
        Horse_Chess(chess,x+2,y+1,cnt+1);
        Horse_Chess(chess,x+2,y-1,cnt+1);
        Horse_Chess(chess,x+1,y-2,cnt+1);
        Horse_Chess(chess,x-1,y-2,cnt+1);
        Horse_Chess(chess,x-2,y-1,cnt+1);
        Horse_Chess(chess,x-2,y+1,cnt+1);
        Horse_Chess(chess,x-1,y+2,cnt+1);
        chess[x][y] = 0; // 此位置清空，没有走马
    }
}
int main()
{
    clock_t start, end;
    int chess[8][8];
    memset(chess,0,64*sizeof(int));
    start = clock();
    Horse_Chess(chess,0,0,1);
    end = clock();
    printf("Time:%lfs\n",(double)(end-start)/CLOCKS_PER_SEC);  // 打印花费时间
    system("pause");
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

不同电脑硬件花费时间不相同，结果如下：
这里写图片描述
还要注意的一点就是，改变8种可能的尝试的顺序会极大改变花费时间

###4.解法二 - DFS深度优先搜索 + 贪心法优化：

  • 贪心法(摘自Wiki百科)：贪心法，又称贪心算法、贪婪算法、或称贪婪法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。[1]比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。
    贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
    贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
    贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
  • 算法分析：DFS算法虽然简单，但求第一个解的时间消耗太多，使用贪心法优化可以极大加快第一个解求解速度，贪心法要求的是局部最优解，而马踏棋盘的局部最优即优先走后续走法最少的那一个位置，因此需要计算并保存8个位置上的走法次数，然后选出走法最少的进行下一次递归，这样很快就能算出第一个解，当然也可以再回溯尝试其他次优解。
    正如【参考4】作者说的一样，贪心法只适合求最优解，但并不能加快求其他解速度
  • C++代码：
#include <iostream>
#include <iomanip>
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "time.h"

using namespace std;

#define IS_WITH_LIMITS(x,y) ((((x)&0xFFFFFFF8) == 0) &&(((y)&0xFFFFFF8) == 0)) // 判断是否越界

int count = 0;
void OutputToTxt(int (*chess)[8])
{
    FILE *fp = fopen("abc.txt","w");
    for(int i = 0; i<8; i++)
    {
        for(int j = 0; j<8; j++)
        {
            fprintf(fp,"%-2d ",chess[i][j]);
        }
        fprintf(fp,"\n");
    }
    fclose(fp);
}
const int step[][2] = {{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}}; // 8种走法x y变化的常量数组

int Count_Step(int (*chess)[8], int x, int y) // 计算位置(x,y)走法个数函数
{
    if(!IS_WITH_LIMITS(x,y) || chess[x][y] != 0) 
        return 8; // 此位置是否越界或是否走过了，是则返回8，用8因为不可能某个点还有8种走法，而且用8便于判断最小值
    int cnt = 0;
    for(int i = 0; i<8; i++)
    {
        if(IS_WITH_LIMITS(x+step[i][0],y+step[i][1]) && chess[x+step[i][0]][y+step[i][1]] == 0) 
            cnt++; // 判断此位置有几个可能走法
    }
    return cnt;
}

void Horse_Chess_Greedy(int (*chess)[8], int x, int y, int cnt)
{
    if(count >= 1) return;
    if(!IS_WITH_LIMITS(x,y)) return; // 越界返回
    if(chess[x][y] == 0)
    {
        chess[x][y] = cnt; // 此位置设置走马的序号
        if(cnt >= 64)
        {
            OutputToTxt(chess); // 输出到文件
            count++; // 可能性+1
            return;
        }

        /* 以下是通过贪心法计算的可能的情况： */
        int stepCnt[8];
        for(int i = 0; i<8; i++) 
            stepCnt[i] = Count_Step(chess,x+step[i][0],y+step[i][1]); // 此位置下8种位置的走法个数

        /* 理论上贪心法只判断最优情况，所以不需要尝试所有8个位置，这里还是加上了8种走法 */
        bool flag = false;
        for(int i = 0; i<8; i++)
        {
            int min = 9,next = 0;
            for(int j = 0; j<8; j++)
            {
                if(min > stepCnt[j]) // 判断最小，这里类似冒泡排序和选择排序
                {
                    flag = true;
                    min = stepCnt[j];
                    next = j;
                }
            }
            if(flag)
            {
                Horse_Chess_Greedy(chess,x+step[next][0],y+step[next][1],cnt+1); // 选择走法最少的位置进行下一趟递归
                stepCnt[next] = 8;  // 这个地方走过了，则设置为8，继续寻找次优解
                flag = false;
            }else{
                break;
            }
        }
        chess[x][y] = 0; // 此位置清空，没有走马
    }
}
int main()
{
    clock_t start, end;
    int chess[8][8];
    memset(chess,0,64*sizeof(int));
    start = clock();
    Horse_Chess_Greedy(chess,0,0,1);
    end = clock();
    printf("Process Time:%lfs\n",(double)(end-start)/CLOCKS_PER_SEC);  // 打印花费时间
    system("pause");
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97

代码运行结果及分步演示(代码没给)：
这里写图片描述

  • 扩展：
    【参考4】里面作者好像用已知判断无解的情况判断当前棋盘的状态，从而省略大部分无解的分支，进而减少递归深度缩短查找时间
    【参考5】里面介绍了一种很有意思的现象，如下图，有兴趣的可以看一下视频
    这里写图片描述这里写图片描述

我的个人主页

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/573496
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号