基于A星算法解决8数码
问题的编程实现
一、问题描述
8数码问题又称9宫问题。在给定的3?3棋格的9个格子内分别放从1到8互不相等的八个数，剩下的一格即为空格，此程序中空格我们用0来表示。通常把8个符号在棋格上的排列顺序称作8数码的状态。开始时，规则给定一个初始状态和一个目标状态，并要求被试者对棋格内的数字经过若干次移动由初始状态达到目标状态，这个过程中只有空格向附近的棋格移动，且每次只能移动一次。
如我们给定8数码的初始状态和目标状态分别如图1、2所示。
2
1 0 5 6 8 3 1 8 7 2 0 6 3 4 5 4 7
图1 初始状态 图2 目标状态
则要求以图1为初始状态，通过交换0和0的上、下、左、右四个方位的数字（每次只能和其中一个交换），达到图2所示目标状态。
二、算法说明
根据任务要求，本文采用A*搜索算法。
1. 状态的表示
在A*算法中，需要用到open表和closed表，在open表中，待扩展节点间有很严格的扩展顺序。因此在表示当前状态的变量中，必须要有能指向下一个扩展节点的指针，以完成对open表中元素的索引。从这一点上看，open表中的元素相互间即构成了一个线性表，因此初步选定使用结构体表示问题的状态。
如图3所示，表示问题的结构体包括表示当前节点状态的DATA和指向open表中下一个待扩展节点的指针NEXT。
图3 结构体
现在进一步考虑DATA中包括的内容：
如图1、2所示，8数码问题的提出是以一个3?3数表表示的，因此本文中采用一个3?3的二维数组s[3][3]表示当前状态的具体信息。
另一方面，A*搜索算法是通过考察节点的代价值来决定open表的排序的，
因此在表示当前状态的DATA中还应该有对当前节点代价值的描述。
根据A*算法的定义，当前节点的代价值由估价函数给出，即：
f(n)?d(n)?h(n)
其中：d(n)表示当前节点n在搜索树中的深度；
h(n)是启发函数。
本例h(n)=p(n)+w(n)
其中：p(n)表示每个将牌与其目标位置之间最短距离的总和； w(n)表示不在位的将牌个数。
因此，在DATA还应包括表示当前节点代价、深度和启发信息的f、d、h。 综上所述，问题状态的表示如下图所示。 Eight:
int s[3][3]; //三行三列数组 char direction; //移动方向 int fn; //fn为dep+h（n） struct Eight *next; //下个节点指针 int dep;
图4 问题的状态表示
2．启发函数的设计
根据A*算法的定义，启发函数应满足：h(n)?h*(n)。
其中：h*(n)表示从当前节点currentchess到目标节点aim的最优路径的实际代价。
并且，在满足h(n)?h*(n)的条件下，h(n)的值越大它所携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。
在8数码问题中，常用的启发函数为： “不在位”将牌个数，或数码“不在位”的最短距离和。此程序中我采用数码“不在位”的将牌个数与每个将牌与
其目标位置之间最短距离的总和的和作为启发函数。
3. 程序流程
主程序流程图：
开始
N初始化s_0，把s_0送入open表open表为空?Y失败，退出
把open表的首节点（节点n）从open表移出，放入closed表节点n为目标节点？成功，退出扩展节点n：将有效子节点加入open表，无效子节点删除
其中，扩展节点n的具体步骤如下：
a) 首先判断其是否在open表中带扩展, 如果出现过，则删除该节点；如果没有出现过，则转b。
b) 判断其是否已经存在于closed表中已经出现过，如果出现过，则删除该节点；如果没有出现过，则说明该节点为一个全新的节点，转c。
c) 将该节点加入open表。其中加入open表顺序按f（n）值从小到大排列，并且当f（n）相等时，按深度depth由大到小。
三、重点代码
节点结构体 struct Eight{ public:
int s[3][3]; //三行三列数组 char direction; //移动方向 int fn; //fn为dep+h（n）
struct Eight *next; //下个节点指针 int dep; //节点深度 };
执行类Execute.h方法
void exeEight(Eight *eight); //执行八数码问题
bool arrcmp(int s1[3][3],int s2[3][3]); //复制节点从而生成新节点 bool arrequ(int s1[3][3],int s2[3][3]); //判断两个九宫格内数码位置是否相同
bool Insertopen(Eight *list, Eight *item); //将节点插入open表 bool ifIncludeopen(Eight *list, Eight *item); //判断节点是否已经在open表中
bool ifIncludeclosed(Eight *list, Eight *item); //判断节点是否已经在closed表中
节点类EightPuyzzle.h方法
int final_s[3][3]; //最终状态的八数码 bool setStart(int s[3][3]); //输入初始状态 bool outPut(int s[3][3]); //输出节点状态 int f_w(int s[3][3]); //w(n)函数 int f_p(int s[3][3]); //p(n)函数每个将牌与其目标位置之间最短距离的总和
int f_h(int s[3][3]); //h(n)函数在此等于p（n）+w（n）
int move_up(int s1[3][3],int i,int j,char dir); //上移 int move_down(int s1[3][3],int i,int j,char dir); //下移 int move_left(int s1[3][3],int i,int j,char dir); //左移 int move_right(int s1[3][3],int i,int j,char dir); //右移
bool j_s(int s[3][3]); //判断是否是八数码问题
重点函数代码： （1）A*主函数
void Execute::exeEight(Eight *eight)