马走日问题的解决--贪心算法

问题描述：

在8×8方格（国际象棋）的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径

问题分析：

首先这是一个搜索问题，运用深度优先搜索进行求解是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。
怎么才能快速地得到部分解呢？

其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，如:
马当前的位置在(i,j)只有三个出口，它们的位置是(i+2,j+1)、(i-2,j+1)和(i-1,j-2)，如分别走到这三个位置，这三个位置又分别会有不同的出口，假定这三个位置的出口个数分别为4、2、3，则程序就选择让走向出口个数最少的(i-2,j+1)位置。
该过程没有回溯，但对于某些开始位置实际上有解，而该算法不能找到解，对于这种情况，只要改变八种可能出口的选择顺序就能找到解

为什么要这样选取？

这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法。

算法思想步骤概括为下面的几点：
①找到一个位置的各个方向的出口（OUT1）。
②对各个方向的出口进行二次出口（OUT2）的搜索。
③记录每个方向上出口（OUT1）的二次出口（OUT2),(OUT2）最小的的那个（OUT1）即为接下来要访问的位置。
④将每次访问过的位置放入容器。
⑤如果不能够正常找到，则回退一步，改变出口顺序。
代码如下(C/C++)：

#include <stdlib.h>
#define N 8 //棋盘的规模
#define M 8 //棋子有8个方向可以走

/*采用贪心算法
 *每一次选择的时候选择当前节点可走方向中出口最少的那一个
 *这样走的步数越多，剩下的节点中可走的方向越多，能够遍历所有点的可能性越大
 *但是这存在一个问题，就是可能这个点本来是可以走过所有点的，但是由于选择
 *导致没有走出，这时只要遍历8个方向就一定能够走出来
*/

int VISITED[N][N];//记录已经走过的点

/*
*node结构体:path中每个元素的结构
*x:int,记录横坐标
*y:int,记录纵坐标
*dir:int,记录处于该点时行走的方向
*/
struct node
{
    int x;
    int y;
    int dir;
};
/*
*stack结构体：记录行走路径的结构体
*point:int,栈顶指针
*/
struct Stack
{
    node path[N * N];
    int point;
};
/*
*Dir:记录行走的的坐标变化单位量
*x:int,x的变化量
*y:int,y的变化量
*/
struct Dir
{
    int x;
    int y;
};

//记录每个点八个方向中哪些可以走完全部的点，默认全部都可以
//主要用于回退
int nodeCanDir[N][N][M];

Dir direction[M] = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}}; //记录某个方向的坐标变化值

/*
*eBound:检查坐标是否越界
*input: 
* x:int,横坐标
* y:int,纵坐标
*return:
*bool，越界返回false，否则返回true
*/
bool eBound(int x, int y)
{
    if (x < 0 || x >= N)
    {
        return false;
    }
    else if (y < 0 || y >= N)
    {
        return false;
    }
    return true;
}

/*
*cDir:算出某点可走的方向数
*input: 
* x:int,横坐标
* y:int,纵坐标
*return:
*int,该点可走的方向数
*/
int cDire(int x, int y)
{
    int number = 0;
    int temp_x;
    int temp_y;
    for (int i = 0; i < M; i++)
    {   //按照i方向更新坐标
        temp_x = x + direction[i].x;
        temp_y = y + direction[i].y;
        //判断这个方向是否可走，可走的话number加1
        if (eBound(temp_x, temp_y) && VISITED[temp_x][temp_y] == 0)
        {
            number++;
        }
    }
    return number;
}

/*
*selDir:选择行走方向（这个方向是a的话，那么走到a后可行走的方向数最少）
*input: 
* x:int,横坐标
* y:int,纵坐标
*return:
*dire:行走方向
*int,所选方向拥有的可走方向数
*/
int selDir(int x, int y, int *dire)
{
    int minDir = 0;     //可走方向最少的方向
    int minNum = M + 1; //可走方向最少的那个方向有多少可以走的
    int temp;
    int temp_x;
    int temp_y;
    for (int i = 0; i < M; i++)
    {
        temp_x = x + direction[i].x;
        temp_y = y + direction[i].y;
        //如果这个方向是出口，走到这个出口时下一步有多少个出口
        if (eBound(temp_x, temp_y) && nodeCanDir[x][y][i] == 0 && VISITED[temp_x][temp_y] == 0)
        {
            temp = cDire(x + direction[i].x, y + direction[i].y);
            //更新具有最小出口点的坐标
            minDir = (minNum >= temp) ? i : minDir;
            minNum = (minNum >= temp) ? temp : minNum;
        }
    }
    *dire = minDir;
    return minNum;
}
/*
*push:进栈函数
* x:int,横坐标
* y:int,纵坐标
* dire:行走方向
*/
void push(Stack *p, int x, int y, int dire)
{
    int point = p->point;
    p->path[point].x = x;
    p->path[point].y = y;
    p->path[point].dir = dire;
    p->point++;
}
/*
*pop:出栈函数
*p:栈顶指针
*f:存储出栈点信息
*return：
*是否出栈成功
*/
bool pop(Stack *p,node *f){
    //如果栈空,则无法出栈
    if(p->point==0){
        return false;
    }
    else{
        f->x=p->path[p->point].x;
        f->y=p->path[p->point].y;
        f->dir=p->path[p->point].dir;
        p->point--;
        return true;
    }
}
/*
*jump：行走函数
*p:栈顶指针
* x:int,横坐标
* y:int,纵坐标
*/
bool jump(Stack *p, int x, int y)
{
    if (p->point == N * N)
    {
        return true;
    }
    else
    {
        int minDir;
        int minNum;
        minNum = selDir(x, y, &minDir);
        //如果selDir过程中没有任何可走的方向
        if (minNum == M + 1)
        {
            node *f=(node*)malloc(sizeof(node));
            //如果是最后一个点
            if (p->point == N * N - 1)
            {
                push(p, x, y, minDir);
                free(f);
                return true;
            }//出栈后没有空，则回溯
            else if(pop(p,f)){
                x=f->x;
                y=f->y;
                VISITED[x][y]=0;
                nodeCanDir[x][y][f->dir]=1;//此路不通
                free(f);
                return jump(p,x,y);
            }else{
                printf("Sorry! Path don't exist.");
                free(f);
                return false;
            }
        }
        else
        {   //如果是正常找到一个方向，将当前节点进栈，继续递归寻找
            //将当前点入栈
            push(p, x, y, minDir);
            VISITED[x][y] = 1;
            //更新点坐标
            x = x + direction[minDir].x;
            y = y + direction[minDir].y;
            //继续下一步
            return jump(p, x, y);
        }
    }
}

int main()
{
    Stack *p = (Stack *)malloc(sizeof(Stack));
    p->point = 0; //堆栈初始化
    printf("Please input start position between (0,0) and (8,8):\n");
    int startX = 2;
    int startY = 5;
    printf("x:");
    scanf("%d",&startX);
    printf("y:");
    scanf("%d",&startY);
    if (jump(p, startX, startY))
    {
        for (int i = 0; i < p->point; i++)
        {
            printf("(%d,%d)--", p->path[i].x, p->path[i].y);
            if(i!=0&&i%6==0){
                printf("\n");
            }
        }
    }
    printf("\n");
    free(p);
    system("pause");
    return 0;
}

结果：

参考文章：
主要参考了这篇文章关于回溯的处理
用C语言解决棋盘上马遍历问题
和这篇文章对贪心算法用于马踏棋盘的讲解
马踏棋盘（马的遍历问题)