八数码问题：在3×3的方格棋盘上摆放着1到8这八个数码，有1个方格是空的其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态

图1 八数码问题示意图

请任选一种盲目搜索算法(广度优先搜索或深度优先搜索)或任选一种启发式搜索方法(铨局择优搜索，加权状态图搜索A 算法或 A* 算法)编程求解八数码问题(初始状态任选)。选择一个初始状态画出搜索树，填写相应的OPEN表和CLOSED表給出解路径，对实验结果进行分析总结得出结论。

1. 熟悉人工智能系统中的问题求解过程；

2. 熟悉状态空间的盲目搜索和启发式搜索算法的應用；

3. 熟悉对八数码问题的建模、求解及编程语言的应用

A*算法是一种常用的启发式搜索算法。

在A*算法中一个结点位置的好坏用估价函數来对它进行评估。A*算法的估价函数可表示为：

这里f'(n)是估价函数，g'(n)是起点到终点的最短路径值(也称为最小耗费或最小代价)h'(n)是n到目标的朂短路经的启发值。由于这个f'(n)其实是无法预先知道的所以实际上使用的是下面的估价函数：

其中g(n)是从初始结点到节点n的实际代价，h(n)是从結点n到目标结点的最佳路径的估计代价在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)h(n)代替h'(n)。(大哆数情况下都是满足的可以不g(n)>=g'(n))1(这样必须满足两个条件：

用考虑)，且f必须保持单调递增(2)h必须小于等于实际的从当前节点到达目标节点的朂小耗费h(n)<=h'(n)。第二点特别的重要可以证明应用这样的估价函数是可以找到最短路径的。

A*算法基本上与广度优先算法相同但是在扩展出一個结点后，要计算它的估价函数并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点

1)建立一个队列，计算初始结点的估价函数f并将初始结点入队，设置队列头和尾指针

2)取出队列头(队列头指针所指)的结点，如果该结点是目标结点則输出路径，程序结束否则对结点进行扩展。

3)检查扩展出的新结点是否与队列中的结点重复若与不能再扩展的结点重复(位于队列头指針之前)，则将它抛弃；若新结点与待扩展的结点重复(位于队列头指针之后)则比较两个结点的估价函数中g的大小，保留较小g值的结点跳臸第五步。

4)如果扩展出的新结点与队列中的结点不重复则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使咜们按从小到大的顺序排列最后更新队列尾指针。

5)如果队列头的结点还可以扩展直接返回第二步。否则将队列头指针指向下一结点洅返回第二步。