贪婪算法优化计算-马踏棋盘问题

一、     问题阐述

将马放到国际象棋的8*8棋盘board上的某个方格中，马按走棋规则进行移动，要求每个方格进入且只进入一次，走遍棋盘上的64个方格，将数字1,2,3…,64依次填入一个8*8的方阵，找出一种可行的方案，并用贪婪算法进行优化。

如图所示，当马在棋盘位置(4,3)时，它可以有1,2,3,4,5,6,7,8个位置可跳

二、     解题思路

1.    需求分析

棋盘可以看做一个矩阵，当马位于棋盘上某一位置时，它就有一个唯一的坐标，那么根据国际象棋的规则，它有8个位置可以跳，这8个位置的坐标是和当前马的坐标是有联系的，例如马的坐标是(x,y)，那么它的下一跳的位置可以是(x-1,y-2)。当然坐标不能越界。马所在的当前位置标为1，它的下一跳的位置标为2，在下一跳的位置标为3，依次类推，如果马走完棋盘，那么最后在棋盘上标的位置是64。

2.      解决方案

（1）回溯法

我们可以采用回溯法求解，当马在当前位置时，我们将它下一跳的所有位置保存，然后从中选择一个位置作为当前位置在跳，递归下去，如果跳不下去，回溯。这有点类似图的深度搜索。

（2）贪婪法

贪婪算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。那么我们在回溯法的基础上，用贪婪算法进行优化，在选择下一跳的位置时，总是选择出口少的那个位置，这里出口少是指这个位置的下一跳位置个数少。这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点，这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。

三、 编写代码

#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

const int N=8; //棋盘规模
int offsetX[N]={-1,1,-1,1,-2,-2,2,2}; //相对于当前点马的下一落脚点x的偏移量
int offsetY[N]={-2,-2,2,2,-1,1,-1,1}; //相对于当前点马的下一落脚点y的偏移量
int chessboard[N][N]; //棋盘,此时每个chessboard[i][j]=0
//程序运行后要对chessboard[i][j]进行编号,从1,2,...,N*N

ofstream log; //输出文件流,记录贪婪寻优结果

class ChessNode //马下一跳的位置--棋盘结点类
{
private:
    int x;  //此结点在棋盘的位置(x,y)
    int y;
    int wayout; //每个结点有8个出口,出口表示此结点的在棋盘下一跳的位置
    //wayout表示此位置的出口数,如果在某一个方向没有出口,那么wayout=0

public:
    ChessNode(int _x=0,int _y=0):x(_x),y(_y)
    {
        wayout=0;
    }
    int getX() const
    {
        return x;
    }
    int getY() const
    {
        return y;
    }
    int getwayout() const
    {
        return wayout;
    }
    void setX(int X)
    {
        x=X;
    }
    void setY(int Y)
    {
        y=Y;
    }
    bool IsCorrect() const 
    {
        //此时要保证(x,y)不能越界并且此时chessboard[x][y]=0
        //马才能跳到这一位置
        if(x<N && x>=0 && y<N && y>=0 && chessboard[x][y]==0)
        {
            return true;
        }
        else return false;
    }
    void SetWayout() //设置结点的出口
    {
        int direction;
        for(direction=0;direction<N;direction++) //依次检测8个方向
        {
            int nx=x+offsetX[direction]; //每一个方向的位置(nx,ny)
            int ny=y+offsetY[direction];
            ChessNode  node(nx,ny); //构造一个结点位置
            wayout+=node.IsCorrect(); //求出出口数
        }
    }
    void show() const
    {
        cout<<"("<<x<<","<<y<<")"<<endl;
        cout<<wayout<<endl;
    }
};

class LessThan //函数对象
{
public:
    bool operator()(const ChessNode& one,const ChessNode& other)
    {
        return one.getwayout()<other.getwayout();
    }
};

const int max=100000; //最大递归深度
class HourseJumpChessboard
{
private:
    int RDepth; //递归的深度
    int count; //棋盘的编号
    bool find;

    void Success()  //成功求解
    {
        int i,j;
        log<<"程序运行后棋盘编号:"<<endl;
        for(i=0;i<N;i++)
        {
            for(j=0;j<N;j++) log<<setw(4)<<chessboard[i][j]<<" ";
            log<<endl;
        }
        log<<"递归深度:"<<RDepth<<endl;
    }

    void DFS(ChessNode node,int count) //普通的寻径算法,类似于图的深度遍历
    {
        //此时的算法很难得到正确的解,原因是程序在遍历时解空间太大
        if(find==true || RDepth>max)
        {
            if(RDepth>max)
            {
                log<<"用普通寻径方式已经达到最大递归深度,无法得到正确的解!"<<endl;
            }
            return; //截断递归
        }
        if(count>N*N)
        {
            find=true;
            Success();
        }
        int direction;
        for(direction=0;direction<N;direction++) //依次搜寻8个方向
        {
            ChessNode node(node.getX()+offsetX[direction],node.getY()+offsetY[direction]);
            if(node.IsCorrect()) 
            {
                RDepth++;
                chessboard[node.getX()][node.getY()]=count;
                DFS(node,count+1);
            }
        }
        chessboard[node.getX()][node.getY()]=0; //此时node为死结点,即没有出口的结点
    }
    
    void GreedyDFS(ChessNode node,int count) //用贪婪算法优化
    {
        if(find==true) return; //截断递归
        if(count>N*N)
        {
            find=true;
            Success();
        }
        int direction;
        vector<ChessNode>v; //保存下一跳位置结点
        for(direction=0;direction<N;direction++) //依次搜寻8个方向
        {
            ChessNode node(node.getX()+offsetX[direction],node.getY()+offsetY[direction]);
            if(node.IsCorrect()) 
            {
                node.SetWayout();
                v.push_back(node);
            }
        }
        sort(v.begin(),v.end(),LessThan()); //对向量v进行升序排序
        vector<ChessNode>::iterator it;
        for(it=v.begin();it!=v.end();it++)
        {
            chessboard[it->getX()][it->getY()]=count;
            RDepth++;
            GreedyDFS(*it,count+1);
        }
        chessboard[node.getX()][node.getY()]=0;
    }
public:
    int getRecursiveDepth() const
    {
        return RDepth;
    }
    HourseJumpChessboard()
    {
        int i,j;
        for(i=0;i<N;i++) //初始化棋盘
        {
            for(j=0;j<N;j++) chessboard[i][j]=0;
        }
    }

    Walk(int x,int y) //初始位置(x,y)
    {
        ChessNode node(x,y);
        if(node.IsCorrect()==false)
        {
            cerr<<"初始位置不合法,程序退出!"<<endl;
            exit(1);
        }
        find=true;
        count=2;
        RDepth=1;
        chessboard[x][y]=1;
        DFS(node,count);
    }
    
    GreedyWalk(int x,int y) //初始位置(x,y)
    {
        ChessNode node(x,y);
        if(node.IsCorrect()==false)
        {
            cerr<<"初始位置不合法,程序退出!"<<endl;
            exit(1);
        }
        find=false;
        count=2;
        RDepth=1;
        chessboard[x][y]=1;
        GreedyDFS(node,count);
    }
};

void main()
{
    log.open("e:\\log.txt");
    if(!log)
    {
        cerr<<"不能写日志文件,程序退出!"<<endl;
        exit(1);
    }
    srand(unsigned(time(0)));
    int n=28; //随机产生28个位置进行测试
    int i;
    int x,y;
    for(i=0;i<n;i++)
    {
        HourseJumpChessboard horse;
        x=rand()%N;
        y=rand()%N;
        horse.Walk(x,y); //普通寻径方式
    
        HourseJumpChessboard Greedyhorse;
        Greedyhorse.GreedyWalk(x,y); //贪婪寻径方式
    }
    log.close();
}

四、

随机选取28个位置，用普通寻径算法和用贪婪法进行比较

从实验结果可以看出贪婪寻优起到了很大的作用

用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  61    2   35   18   51    4   37   20
  34   17   62    3   36   19   52    5
   1   60   33   50   63   54   21   38
  16   49   56   59   32   47    6   53
  57   12   31   48   55   64   39   22
  30   15   58   43   40   25   46    7
  11   42   13   28    9   44   23   26
  14   29   10   41   24   27    8   45
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
   5    8   23   38   57   10   25   28
  22   37    6    9   24   27   58   11
   7    4   39   56   45   60   29   26
  36   21   44   41   52   55   12   59
   3   40   51   46   61   42   53   30
  20   35   18   43   54   47   62   13
  17    2   33   50   15   64   31   48
  34   19   16    1   32   49   14   63
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  32   63   10    5   28   57   12    3
   9    6   31   64   11    4   27   58
  62   33    8   29   56   59    2   13
   7   30   61   42    1   52   55   26
  34   43   20   51   60   41   14   53
  19   50   35   44   47   54   25   40
  36   21   48   17   38   23   46   15
  49   18   37   22   45   16   39   24
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  44   25   42    7   48   23   60    5
  41    8   45   24   59    6   47   22
  26   43   52   49   46   57    4   61
   9   40   27   58   51   62   21   56
  28   53   50   39   34   55   64    3
  13   10   35   54   63   18   33   20
  36   29   12   15   38   31    2   17
  11   14   37   30    1   16   19   32
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
   4    1    6   21   40   25   16   23
   7   20    3   46   17   22   39   26
   2    5   18   41   38   47   24   15
  19    8   63   50   45   42   27   48
  62   51   44   37   64   49   14   31
   9   36   61   58   43   30   55   28
  52   59   34   11   54   57   32   13
  35   10   53   60   33   12   29   56
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  11   16   49   32    9   18   21   60
  48   31   10   17   50   61    8   19
  15   12   47   52   33   20   59   22
  30   53   14   45   62   51   34    7
  13   46   29   54   35   58   23   64
  28   39   36    1   44   63    6   57
  37    2   41   26   55    4   43   24
  40   27   38    3   42   25   56    5
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  23   20    3   32   25   10    5    8
   2   33   24   21    4    7   26   11
  19   22    1   54   31   28    9    6
  34   53   60   29   44   51   12   27
  61   18   45   52   55   30   43   50
  38   35   62   59   46   49   56   13
  17   64   37   40   15   58   47   42
  36   39   16   63   48   41   14   57
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  33   22   31    8   35   12   41   10
  30    7   34   23   40    9   36   13
  21   32   39   44   37   60   11   42
   6   29   24   57   46   43   14   59
  25   20   45   38   61   58   55   50
   2    5   28   47   56   51   62   15
  19   26    3   52   17   64   49   54
   4    1   18   27   48   53   16   63
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
   2   23    4   19   46   39   14   17
   5   20    1   40   15   18   51   38
  24    3   22   47   50   45   16   13
  21    6   63   44   41   48   37   52
  62   25   42   49   64   53   12   33
   7   28   61   58   43   34   55   36
  26   59   30    9   54   57   32   11
  29    8   27   60   31   10   35   56
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  13   36   15   46   11   34   29   56
  16   47   12   35   30   55   10   33
  37   14   45   48   51   32   57   28
  44   17   52   31   58   49   54    9
  21   38   43   50   53   60   27   64
  18   41   20   59   24   63    8    5
   1   22   39   42    3    6   61   26
  40   19    2   23   62   25    4    7
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  43   38   13   36   45   50   11   54
  14   35   44   51   12   55   46   49
  39   42   37   56   59   48   53   10
  34   15   64   41   52   17   58   47
  63   40   33   16   57   60    9   18
   4    1   30   61   32   21   26   23
  29   62    3    6   27   24   19    8
   2    5   28   31   20    7   22   25
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
   2    5   28   23   18    7   30   33
  27   24    3    6   29   32   19    8
   4    1   26   55   22   17   34   31
  25   42   47   16   59   56    9   20
  46   15   58   41   54   21   60   35
  43   40   45   48   57   62   53   10
  14   49   38   63   12   51   36   61
  39   44   13   50   37   64   11   52
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
   6   41    8   23    4   39   18   21
   9   24    5   40   19   22    3   38
  42    7   44   25   48   37   20   17
  33   10   57   36   45   26   49    2
  56   43   34   47   58    1   16   27
  11   32   55   62   35   46   59   50
  54   63   30   13   52   61   28   15
  31   12   53   64   29   14   51   60
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  16   31   12   41   26   29   10   59
  13   42   15   30   11   58   25   28
  32   17   40   43   54   27   60    9
  39   14   51   36   57   44   53   24
  18   33   38   55   52   61    8   45
   3   50   35   48   37   56   23   62
  34   19    2    5   64   21   46    7
   1    4   49   20   47    6   63   22
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
   3    6   33   22   11    8   43   64
  34   21    4    7   44   63   12    9
   5    2   55   32   23   10   61   42
  54   35   20    1   62   45   24   13
  19   56   53   48   31   60   41   46
  36   49   30   57   52   47   14   25
  29   18   51   38   27   16   59   40
  50   37   28   17   58   39   26   15
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  14   11   38   33   16    1   20   23
  39   32   15   12   37   22   17    2
  10   13   40   55   34   19   24   21
  31   42   47   36   59   56    3   18
  46    9   58   41   54   35   60   25
  43   30   45   48   57   62   53    4
   8   49   28   63    6   51   26   61
  29   44    7   50   27   64    5   52
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  19   16   33   28   21    6    1    4
  32   29   20   17   34    3   22    7
  15   18   31   44   27   24    5    2
  30   43   62   25   54   35    8   23
  63   14   45   42   61   26   53   36
  46   41   64   55   52   49   60    9
  13   56   39   48   11   58   37   50
  40   47   12   57   38   51   10   59
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
   8    5   10   25   32    3   20   23
  11   26    7    4   21   24   33    2
   6    9   28   31   60    1   22   19
  27   12   41   50   29   52   59   34
  40   49   30   61   42   57   18   53
  13   46   43   56   51   62   35   58
  44   39   48   15   64   37   54   17
  47   14   45   38   55   16   63   36
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
   7   10   25   40   59   12   27   30
  24   39    8   11   26   29   60   13
   9    6   41   58   47   62   31   28
  38   23   46   43   54   57   14   61
   5   42   53   48   63   44   55   32
  22   37   20   45   56   49   64   15
  19    4   35   52   17    2   33   50
  36   21   18    3   34   51   16    1
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  14   29   10   41   24   27    8   45
  11   42   13   28    9   44   23   26
  30   15   52   43   40   25   46    7
  53   12   31   48   51   62   39   22
  16   49   54   61   32   47    6   63
   1   60   33   50   55   64   21   38
  34   17   58    3   36   19   56    5
  59    2   35   18   57    4   37   20
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
   6   41    8   23    4   39   18   21
   9   24    5   40   19   22    3   38
  42    7   44   25   48   37   20   17
  33   10   57   36   45   26   49    2
  56   43   34   47   58    1   16   27
  11   32   55   62   35   46   59   50
  54   63   30   13   52   61   28   15
  31   12   53   64   29   14   51   60
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  11   52   13   54    9   60   23   56
  14   43   10   59   24   55    8   47
  51   12   53   44   61   48   57   22
  42   15   62   49   58   25   46    7
  37   50   41   30   45   64   21   26
  16   33   36   63   40   29    6    3
  35   38   31   18    1    4   27   20
  32   17   34   39   28   19    2    5
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
   7    4    9   24   31    2   19   22
  10   25    6    3   20   23   32    1
   5    8   27   30   55   34   21   18
  26   11   56   35   28   51   60   33
  57   36   29   54   59   62   17   52
  12   39   58   45   42   53   50   61
  37   46   41   14   63   48   43   16
  40   13   38   47   44   15   64   49
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  23   20    1   16   33   38   11   14
   2   17   22   37   12   15   32   39
  21   24   19   34   43   40   13   10
  18    3   42   59   36   49   44   31
  25   58   35   50   41   60    9   48
   4   51   62   57   54   47   30   45
  63   26   53    6   61   28   55    8
  52    5   64   27   56    7   46   29
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
   1    4   35   20   47    6   43   22
  34   19    2    5   42   21   46    7
   3   36   41   48   39   54   23   44
  18   33   38   53   50   45    8   55
  37   14   49   40   61   56   51   24
  32   17   60   57   52   27   62    9
  13   58   15   30   11   64   25   28
  16   31   12   59   26   29   10   63
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  45    8   27   24   41   10   29   14
  26   23   44    9   28   13   42   11
   7   46   25   40   43   52   15   30
  22   39   48   51   60   31   12   53
  47    6   59   32   49   54   61   16
  38   21   50   55   58   33   64    1
   5   56   19   36    3   62   17   34
  20   37    4   57   18   35    2   63
递归深度:74
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  33   28    3   26   51   10    5    8
   2   25   32   61    4    7   50   11
  29   34   27   52   49   62    9    6
  24    1   64   31   60   47   12   41
  35   30   53   48   63   42   59   46
  20   23   18   43   54   57   40   13
  17   36   21   56   15   38   45   58
  22   19   16   37   44   55   14   39
递归深度:64
用普通寻径方式已经达到最大递归深度,无法得到正确的解!
程序运行后棋盘编号:
  19   16   33   28   21    6    1    4
  32   29   20   17   34    3   22    7
  15   18   31   44   27   24    5    2
  30   43   62   25   54   35    8   23
  63   14   45   42   61   26   53   36
  46   41   64   55   52   49   60    9
  13   56   39   48   11   58   37   50
  40   47   12   57   38   51   10   59
递归深度:64