这是人工智能中的经典难题之一 ， 问题是在3×3方格棋盘中，放8格数，剩下的没有放到的为空，每次移动只能是和相邻的空格交换数 。程序自动产生问题的初始状态，通过一系列交换动作将其转换成目标排列（如下图1－2到图1－3的转换） 。
（图1－2）（图1－3）
该问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列 。可以把一个随机排列的数组从左到右从上到下用一个一维数组表示，如上图1－2我们就可以表示成｛8，7，1，5，2 ， 6，3，4，0｝其中0代表空格 。
在这个数组中我们首先计算它能够重排列出来的结果，公式就是：
∑（F（X））＝Y，其中F（X）
是一个数前面比这个数小的数的个数,Y为奇数和偶数时各有一种解法 。（八数码问题是否有解的判定 ）
上面的数组可以解出它的结果 。
F（8）＝0；
F（7）＝0；
F（1）＝0；
F（5）＝1；
F（2）＝1；
F（6）＝3；
F（3）＝2；
F（4）＝3；
Y＝0＋0＋0＋1＋1＋3＋2＋3＝10
Y＝10是偶数，所以其重排列就是如图1－3的结果，如果加起来的结果是奇数重排的结果就是如图1－1最右边的排法 。
三、算法分析
求解方法就是交换空格（0）位置，直至到达目标位置为止 。图形表示就是：
（图3－1）
要想得到最优的就需要使用广度优先搜索，九宫的所以排列有9！种，也就是362880种排法，数据量是非常大的 ， 使用广度搜索 ， 需要记住每一个结点的排列形式，要是用数组记录的话会占用很多的内存，可以把数据进行适当的压缩 。使用DWORD形式保存，压缩形式是每个数字用3位表示，这样就是3×9＝27个字节 ， 由于8的二进制表示形式1000，不能用3位表示，使用了一个小技巧就是将8表示为000，然后用多出来的5个字表示8所在的位置，就可以用DWORD表示了 。用移位和或操作将数据逐个移入，比乘法速度要快点 。定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径 。
类结构如下：
class CNineGird
{
public:
struct PlaceList
{
DWORD Place;
PlaceList* Left;
PlaceList* Right;
};
struct Scanbuf
{
DWORD Place;
int ScanID;
};
struct PathList
{
unsigned char Path[9];
};
private:
PlaceList *m_pPlaceList;
Scanbuf *m_pScanbuf;
RECT m_rResetButton;
RECT m_rAutoButton;
public:
int m_iPathsize;
clock_t m_iTime;
UINT m_iStepCount;
unsigned char m_iTargetChess[9];
unsigned char m_iChess[9];
HWND m_hClientWin;
PathList *m_pPathList;
bool m_bAutoRun;
private:
inline bool AddTree(DWORD place , PlaceList* parent);
void FreeTree(PlaceList* parent);
inline void ArrayToDword(unsigned char *array , DWORDdata);
inline void DwordToArray(DWORD data , unsigned char *array);
inline bool MoveChess(unsigned char *array , int way);
bool EstimateUncoil(unsigned char *array);
void GetPath(UINT depth);
public:
void MoveChess(int way);
bool ComputeFeel();
void ActiveShaw(HWND hView);
void DrawGird(HDC hDC , RECT clientrect);
void DrawChess(HDC hDC , RECT clientrect);
void Reset();
void OnButton(POINT pnt , HWND hView);
public:
CNineGird();
~CNineGird();
};
计算随机随机数组使用了vector模板用random_shuffle（，）函数来打乱数组数据，并计算目标结果是什么 。代码：
void CNineGird::Reset()
{
if(m_bAutoRun) return;
推荐阅读
- html5具有那些优势，html5有哪些新特性和优点
- 电脑显卡怎么检查新旧，电脑显卡怎么看新旧
- c语言时间比较的函数 c语言时间比较的函数怎么写
- 表单提价必填的提示jquery，表单提交是什么意思
- 歪歪怎么直播视频号，歪歪如何直播游戏
- php分页获取不同数据库 php通用分页类
- linux筛选文件夹命令，筛选Linux进程的命令
- ppt怎么制作坐标，ppt怎么制作坐标图表
- 母婴科普直播视频素材，母婴直播主题吸引人话题