问题描述： 算法程序: 设计一个启发函数,利用A算法求解15数码问题。 要求: 尽可能用与A算法一致的思路实现算法, 力求简单明了地给出一个解.
一、A*算法 A算法是一种常用的启发式搜索算法。 在A算法中，一个结点位置的好坏用估价函数来对它进行评估。 A*算法的估价函数可表示为： f’(n) = g’(n) + h’(n) 这里，f’(n) 是估价函数， g’(n) 是起点到终点的最短路径值，h’(n)是n到目标的最短路经的启发值。由于这个 f’(n) 无法预先知道，所以实际上使用的是下面的估价函数： f(n) = g(n) + h(n)。其中 g(n) 是从初始结点到节点 n 的实际代价， h(n)是从结点n到目标结点的最 佳路径的估计代价。在这里主要是 h(n) 体现了搜索的启发信息，因为 g(n) 是已 知的。用 f(n) 作为 f’(n) 的近似，也就是用 g(n) 代替 g’(n) ，h(n) 代替 h’(n) 。 这样必须满足两个条件： （1）g(n)>=g’(n)且f必须保持单调递增。 （2）h 必须小于等于实际的从当前节点到达目标节点的最小耗费 h(n)<=h’(n)
二、算法实现步骤（结合本题代码）
根据已知的起两个15数码表建立初始状态结点start和目标状态结点end，计算初始状态结点的评价函数值
创建open表和close表，将初始状态结点start加入open表中。
如果open表为空，则查询失败并退出程序，否则进入步骤4
在open表中找到评价函数值最小的点（取open表的首个结点），判断是否为目标结点，如果是则代表查询成功并退出循环（程序），否则将当前结点作为待拓展结点，进入步骤5
对于待拓展结点，通过上下左右四个方向移动空格位置来拓展新状态结点，同时更新各个新状态节点的评价函数估计值，并且新状态结点记录下前一个结点下标index（为了打印最终状态路径）。
对于新拓展的结点： ①若新拓展的结点不在open表和close表中，则加入到open表中； ②若新拓展的结点在open表，如果新节点的评价函数估计值小于原有结点的评价函数估计值，则用新节点替换掉open表的旧结点 ③若新拓展的结点在close表，如果新节点的评价函数估计值小于原有结点的评价函数估计值，则用新节点替换掉close表的旧结点
将当前拓展结点从open表中删除，加入close表中，并且对open表依据评价函数估计值进行排序，跳转到步骤3.
实现代码：
#include
#include
#include
#include
using namespace std;
#define ROW 4
#define COL 4
#define N 0 //north
#define S 1 //south
#define W 2
#define E 3
class state{
public:
int status = 0;
int d = 0; //当前深度值
int p = 0; //与目标状态的总距离
int f = 0; //函数估算值
int direction = 0; // 记录方向
int index; //下标
int pre; //记录前一状态
int matrix[ROW][COL];
state(){}
state(int matrix[