15数码问题（A*算法）_十五数码难题

一、题目

 设计一个启发函数，利用A*算法求解15数码问题。

要求: 尽可能用与A*算法一致的思路实现算法, 力求简单明了地给出一个解.

二、问题描述

15数码问题其实就是棋盘移动问题，是人工智能中的一个经典案例。如上图所示，在一个4 X 4的16宫格棋盘上，有15个数字将牌（整数1~15），还有一个空格（为了方便操作用数字0表示）；空格周围四个方向的将牌允许向空格移动，通过移动将牌就可以改变将牌棋盘的格局。现在，我们要解决的问题就是如何移动将牌使初始状态成为目标状态。

三、算法描述

 在这里，我们将使用的是启发式搜索算法：A*算法。在使用A*算法之前，我们先来了解A算法。

启发式搜索算法A，一般简称为A算法，是一种典型的启发式搜索算法。其基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。

评价函数的形式如下：
                      f（n）＝g（n）＋h（n）

其中n是被评价的节点。

我们先来定义下面几个函数的含义，它们与f（n）、g（n）和h（n）的差别是都带有一个"*"号。

g*(n)：表示从初始节点s到节点n的最短路径的耗散值；

h*(n)：表示从节点n到目标节点g的最短路径的耗散值；

f*(n)=g*(n)+h*(n)：表示从初始节点s经过节点n到目标节点g的最短路径的耗散值。
　　   而f（n）、g（n）和h（n）则分别表示是对f*（n）、g*（n）和h*（n）三个函数值的的估计值。是一种预测。A算法就是利用这种预测，来达到有效搜索的目的的。它每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。

当在算法A的评价函数中，使用的启发函数h(n)是处在h*(n)的下界范围，即满足h(n)<=h*(n)时，把这个算法就称为A*算法。

四、具体步骤

(1).把起始结点放到OPEN表中。计算F（S），并把其值与结点S联系起来。

(2).如果OPEN表是个空表，则没有解，失败退出；否则继续。

(3).从OPEN表中选择一个F值最小的结点I。如果有几个结点合格，当其中有一个为目标结点时，则选择此目标结点，否则就选择其中任一个结点为结点I。

(4).把结点I从OPEN表中移出，并把它放入CLOSE的扩展结点表中。

(5).如果I是目标结点，则成功退出，求得一个解。

(6).扩展结点I，生成其全部后继结点。对于I的每一个后继结点J：

       (a).计算F(J).

       (b).如果J既不在OPEN表中，也不在CLOSE表中，则用估价函数F把它添入OPEN表中。从J加一指向其父辈结点I的指针，以便一旦找到目标结点时记住一个解答捷径。

       (c).如果J已在OPEN表或CLOSE表上，则比较刚刚对J计算过的F值和前面计算过的该结点在表中的F值。如果新的F值较小，则

             (i).以此新值代替旧值。

             (ii).从J指向I，而不是指向它的父辈结点。

             (iii).如果结点J在CLOSE表中，则把它移回OPEN表中。

(7).转向（2），即GOTO(2)

五、程序实现

首先，我们要建立一个结构体来存放信息：棋盘数据、移动规则、空格位置、是否遍历标志、f函数值、深度、父亲结点、儿子结点。