自编的 可以看看试试 结合人工智能课本P57页

A*算法解决八数码问题，内含可执行程序、报告、源代码及注释。 程序执行效率高，占用资源较少。

用A*算法实现八数码（java实现），有图形化界面，且输出最优路径

数据结构课程设计八数码（九宫）问题求解。报告+源码。采用了A*算法 题目8:九宫问题 问题描述: 在一个3*3的九宫中，有1-8这8个数及一个空格随机的摆放在其中的格 子里。如下面左图所示。要求实现这样的问题:将九宫问题调整为如右图所示的 形式。每次只能将与空格(上、下或左、右)相邻的一个数字平移到空格中。 基本要求: 问你通过移动中间的空格是否能达到右图所示的状态，如果能，则输出所走 的路径，如果不能，则输出: unsolvable。最好能画出九宫的图形形式，并在其 上动态的演示移动过程。

以A*算法作为本程序的算法，利用f=g+h;其中g代表每个结点的深度，h代表该结点与目标结点相差的位置。利用open，close表作为辅助。把每个同一层次的结点放进open表中，再选取最小代价放入close表中。close表中的结点即为最优路径中的一个结点。直到找出目标的结点，然后打印。 ① 判断OPEN表是否为空的函数 ② 求OPEN表中估价函数值最小的结点的函数 ③ 判断初始状态是否可到达目标状态的函数 ④ 求估价函数值p(n)-曼哈顿距离 ⑤ 产生新状态的函数，共四个，空格上/下/左/右移动 ⑥ 判重函数，判断新节点在OPEN,CLOSE表中是否已经有了 ⑦ 单链表的逆置 ⑧ 输出路径 ⑨ 将结点添加到OPEN或CLOSE表中函数

A*算法求解八数码问题 1、A*算法基本思想： 1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。 2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。 3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。 4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。 5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。 2、程序运行基本环境： 源程序所使用编程语言：C# 编译环境：VS2010，.net framework 4.0 运行环境：.net framework 4.0 3、程序运行界面 可使用程序中的test来随机生成源状态与目标状态 此停顿过程中按Enter即可使程序开始运行W（n）部分； 此停顿部分按Enter后程序退出； 4、无解问题运行情况 这里源程序中是先计算源状态与目标状态的逆序对的奇偶性是否一致来判断是否有解的。下面是无解时的运行画面： 输入无解的一组源状态到目标状态，例如： 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 8 7 0 运行画面如下： 5、性能比较 对于任一给定可解初始状态，状态空间有9!/2=181440个状态；当采用不在位棋子数作为启发函数时，深度超过20时，算法求解速度较慢； 其中启发函数P(n)与W(n)的含义如下： P(n): 任意节点与目标结点之间的距离； W(n): 不在位的将牌数； 源状态 目标状态 P(n) 生成节点数 W(n) 生成节点数 P(n) 扩展节点数 W(n) 扩展节点数 2 8 3 1 6 4 7 0 5 1 2 3 8 0 4 7 6 5 11 13 5 6 1 2 3 8 0 4 7 6 5 0 1 3 8 2 4 7 6 5 6 6 2 2 4 8 2 5 1 6 7 0 3 7 4 2 8 5 6 1 3 0 41 79 22 46 6 2 5 8 7 0 3 1 4 0 3 6 7 1 8 4 5 2 359 10530 220 6769 7 6 3 1 0 4 8 5 2 2 8 7 1 3 4 6 5 0 486 8138 312 5295 下图是解决随机生成的100中状态中，P(n)生成函数的生成节点与扩展节点统计图： 由上图可知，P(n)作为启发函数，平均生成节点数大约在1000左右，平均扩展节点数大约在600左右； 下图是解决随机生成的100中状态中，W(n)生成函数的生成节点与扩展节点统计图： 由上图可知，W (n)作为启发函数，平均生成节点数大约在15000左右,是P(n)作为启发函数时的平均生成节点的15倍；W (n)作为启发函数，平均扩展节点数大约在10000左右，是P(n)作为启发函数时的平均扩展节点的15倍； 下图是解决随机生成的100中状态中，两个生成函数的生成节点与扩展节点统计图： 由上述图表可以看到，将P(n)作为启发函数比将W(n)作为启发函数时，生成节点数与扩展节点数更稳定，相比较来说，采用P(n)作为启发函数的性能比采用W(n)作为启发函数的性能好。 6、源代码说明 1）AStar-EightDigital-Statistics文件夹：用来随机生成100个状态，并对这100个状态分别用P(n)与W(n)分别作为启发函数算出生成节点以及扩展节点，以供生成图表使用；运行界面如下： 2）Test文件夹：将0-8这9个数字随机排序，用来随机生成源状态以

人工智能：基于A星算法的八数码问题C程序源代码

基于状态空间表示法的A*算法求解八数码难题

八数码游戏转换为拼图游戏 八数码游戏转换为拼图游戏 八数码游戏转换为拼图游戏

这是人工智能的一个实验，可能比较简单，没有界面显示，宽度优先算法