一、八数码问题A*问题分析
1 问题的肢解和攻关
首先，八数码问题包括一个初始状态(START) 和 目标状态(END)，所谓解八数码问题就是在两个状态间寻找一系列可过渡状态（START->STATE1->STATE2->...->END）。这个状态是否存在就是我们要解决的第一个问题。
解决八数码问题，主要面临的问题有：Q1）开始状态S到目标状态D是否可解；Q2）扩展节点的选择；Q3）扩展待扩展节点 Q4）判断是否已达目标节点D
问题Q 1）通过逆序数的奇数偶数来判断。因为在空白移动过程中，数码的逆序数不改变。左右移动，数码序列不变。上下移动，数码序列中某个数字则移动了两位。问题的实质就是：如果是N*N的数码盘的话，左右移动，数码序列不变；上下移动则数码序列变动N-1位。若N为奇数则在变动过程中其逆序数不会改变。而八数码问题为3*3矩阵，3为奇数，故逆序数不作改变。故可通过判断当前状态S的逆序数以及目标状态SD的数字序列的逆序数的奇偶性是否相同来判断该问题是否可解。
问题Q3）扩展节点即为上下左右四个方向移动空格到没有扩展过的节点中去。这里涉及到几个问题：Q5该节点是否已扩展过 ；Q6扩展是否超过了地图
问题Q4）是否达到目标节点，将当前节点和目标节点进行比较
而在提及八数码问题的几种不同的解法的时候，我们是针对问题Q2提出的不同解法，即不同的扩展新节点的方法：譬如盲目搜索中的宽度优先搜索算法和深度优先搜索算法；譬如启发式搜索的A*算法。
1） A*算法
A*算法的核心思想参见教材搜索章节，对于A*算法有两大地方可以有不同的选择，Q7）启发函数的选择；Q8）OPEN表中取最优的选择
问题Q7）对于f(n)的考虑最简单的便是比较每个状态与目标状态相比错位的牌数。这个启发意味着如果其他条件相同，那么错位的牌数最少的状态可能最接近目标状态。然而这个启发没有使用从棋盘格局中可以得到的所有信息，因为它没有把牌必要的移动距离纳入考虑。一个“更好一点”的启发是对错位的牌必须要移动的距离求和，为了达到这个目的，每张牌必须要移动的每个方格算为一个距离单位。这两种启发都存在一种不足，就是没有认识到点到牌的难度。也就是说，如果两张牌是彼此相邻的，而且目标是要求互相颠倒它们的位置，那么要把它们放到适当的位置需要远不止两次的移动，因为各张牌必须相互绕来绕去。一种把这个问题纳入考虑的启发对每个直接颠倒（两张相邻的牌要满足目标顺序必须交换位置）乘以一个小的数字（比如2）。仅仅单独使用上面三种启发的一种显然是不可取的，对于前两种前面已经论述过，对于第三种也很显然，如果一个状态中没有直接颠倒的牌，那么评估函数就是0。所以现在综合上面三种（或者说是后两种）启发，得到第四种启发：把错位牌的距离和与直接颠倒数的二倍相加，这样就克服了单纯颠倒启发的不足。
问题Q8）全局最优：将Open表中的所有节点进行排序选择估价函数f(n)最优的进行扩展。第二种选择就是选择当前层扩展的节点中选择最优的f(n)进行扩展。
2） 小结
对于八数码问题的解决算法，在上面已经有了不同的讨论，而针对对扩展节点的选择方案上的A*算法，可以有很多种不同的选择，主要取决于f(n)估价函数的选择。
1） 数据结构
1.1）现有存储方式
节点的存储，采用3*3矩阵来实现，而实际上却用不了这么多。而对于矩阵中的每个数字都是不大于8的，对于原本的矩阵，存储空间耗费9个int类型的空间，即9*4个字节（80x86处理器），而实际一个int类型即可标识一个类型的状态矩阵。（但不可唯一标识）。
而对于这种数据结构除了节省空间外，在解决八数码问题中的一些操作上也可以节省时间。譬如问题：判断两个状态节点是否相同
现有解决方案：每个状态节点中存储的是一个3*3的矩阵（或大小为9的向量）
For循环判断，两个状态是否相同。
这种方案的缺点有：
缺点1）
实际使用不了这么多的空间，状态节点存储的唯一标识状态的节点是该状态下的矩阵，而对于矩阵中的每个数字都是不大于8的，对于原本的矩阵，存储空间耗费9个int类型的空间，而实际一个int类型即可标识一个类型的状态矩阵。（但不可唯一标识）。
缺点2）
针对判断两个状态节点中存储的矩阵是否相同，需要for这样的循环语句来进行判断（以及for循环中的if语句等），需要多次进行跳转分支的预测，会降低处理器中流水线的并行性，造成流水阻塞。
综上，无论是在空间消耗上，还是在cpu的执行上都存在着缺陷。
1.2）改进存储方式
评论