\qquad 八数码问题可以说得上是搜索问题中比较经典的，可以有很多种搜索策略，比如说有最常见的BFS，DFS，此外，A也是一个比较普遍的搜索算法。在八数码问题A往往可以得到最优的求解路径。（再也不用担心不会拼图了，哈哈哈

\qquad 可能还有很多没有对A很深的理解，以下是自己的一些小看法。 \qquad A算法作为启发式搜索的一种，第一个必不可少是启发式函数；同时作为A*算法的比较显著的一个特点就是对open表和close表的维护.

\qquad 启发式函数听起来很有学问，其实可以很简单的理解为从源点到目标的所需要消耗的总代价f(n)（和适应度函数比较相像），这个总代价可以分成两个部分从源点到中间节点（搜索的中间状态）已经消耗的实际代价g（n），另一个部分就是对从中间节点到目标的预测h(n)。 \qquad 通常来说，这里的代价一般是指各种距离，像欧式距离，曼哈顿距离等等，这个根据你所求解的实际问题决定。 \qquad 另一个值得指出的就是预测，预测值直接影响了问题求解的效率以及能否求得合理的解。这里给出一个结论：对于任意预测值h(n）均小于等于实际值的话，我们可以说最终解就是问题的最优解。

open表：先可以简单认为是一个未搜索节点的表 close表：先可以简单认为是一个已完成搜索的节点的表（即已经将下一个状态放入open表内） \qquad 为什么说是简单认为呢？理由很简单，因为open表与close表中的元素在一定规则下可以相互转化，最终实现搜到解。 \qquad 规则一：对于新添加的节点S（open表和close表中均没有这个状态），S直接添加到open表中 \qquad 规则二：对于已经添加的节点S（open表或者close表中已经有这个状态），若在open表中，与原来的状态 S 0 S_{0} S0​的f(n)比较，取最小的一个。若在close表中，那就分成两种情况，第一种,close表中的该状态 S 0 S_{0} S0​的f(n)大于S的，不做修改；第二种 S 0 S_{0} S0​的f(n)小于S的,那就要需要将close表中 S 0 S_{0} S0​的f(n)更新，同时将该状态移入到open表中。 \qquad 规则三：下一个搜索节点的选择问题，选取open表中f(n)的值最小的状态作为下一个待搜索节点 \qquad 规则四：每次需要将带搜索的节点下一个所有的状态按照规则一二更新open表,close表，搜索完该节点后，移到close表中。

按照上述规则我们来体验一次简单的A*算法

这里需要说明的A能找到的解是局部最优解，但是独特的启发式函数可以使得解为全局最优解，八数码问题就是一个能通过A求得最优解的问题。 像下图所示，通过将数字位向空格位移动直至将棋盘从初始状态变化到目标状态。