马跳棋盘问题.doc

文档介绍：用贪婪算法优化马踏棋盘问题
问题阐述
将马放到国际象棋的8*8棋盘board上的某个方格中,马按走棋规则进行移动,要求每个方格进入且只进入一次,走遍棋盘上的64个方格,将数字1,2,3…,64依次填入一个8*8的方阵,找出一种可行的方案,并用贪婪算法进行优化。
0 1 2 3 4 5 6 7

2
1
5
7
Horse
6
8
4
3
如图所示,当马在棋盘位置(4,3)时,它可以有1,2,3,4,5,6,7,8个位置可跳
解题思路
需求分析
棋盘可以看做一个矩阵,当马位于棋盘上某一位置时,它就有一个唯一的坐标,那么根据国际象棋的规则,它有8个位置可以跳,这8个位置的坐标是和当前马的坐标是有联系的,例如马的坐标是(x,y),那么它的下一跳的位置可以是(x-1,y-2)。
当然坐标不能越界。马所在的当前位置标为1,它的下一跳的位置标为2,在下一跳的位置标为3,依次类推,如果马走完棋盘,那么最后在棋盘上标的位置是64。
解决方案
回溯法
我们可以采用回溯法求解,当马在当前位置时,我们将它下一跳的所有位置保存,然后从中选择一个位置作为当前位置在跳,递归下去,如果跳不下去,回溯。这有点类似图的深度搜索。
贪婪法
贪婪算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。那么我们在回溯法的基础上,用贪婪算法进行优化,在选择下一跳的位置时,总是选择出口少的那个位置,这里出口少是指这个位置的下一跳位置个数少。这是一种局部调整最优的做法,如果优先选择出口多的子结点,那出口少的子结点就会越来越多,很可能出现‘死’结点,这样对下面的搜索纯粹是徒劳,这样会浪费很多无用的时间,反过来如果每次都优先选择出口少的结点跳,那出口少的结点就会越来越少,这样跳成功的机会就更大一些。
编写代码
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <vector>
using namespace std;
class Point
{
protected:
int x;
int y;
public:
Point(int X=0,int Y=0):x(X),y(Y)
{
}
Point(const Point& P)
{
x=;
y=;
}
Point& operator=(const Point& P)
{
x=;
y=;
return *this;
}
int getX() const
{
return x;
}
int getY() const
{
return y;
}
void setX(int X)
{
x=X;
}
void setY(int Y)
{
y=Y;
}
};
class PointX:public Point
{
private:
t_NextJump; //当马以当前位置为基准,下一跳位置的个数
public:
PointX(int X=0,int Y=0,t=0):Point(X,Y)
{
}
PointX(const PointX& p)
{
x=;
y=;
cnt_NextJump=t_NextJump;
}
PointX& operator=(const PointX& p)
{
x=;
y=;
cnt_NextJump=t_NextJump;
return *this;
}
int t() const
{
t_NextJump;
}
void t(t)
{
t;
}
};
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的偏移量
ofstream file1; //文件输出流
class SearchPath //寻径类
{
protected:
int chessboard[N][N]; //棋盘
Point startPoint; //起始点
bool find; //find=false表示没有找到路径