求 ：八数码启发式搜索算法

《求 ：八数码启发式搜索算法》有 4 条评论

1. VC爱好者 说：

   2006 年 5 月 28 日下午 10:03

   八数码问题源程序   http://www.chinaoak.com/download/sources/arithmetic/winep_co de.zip  
2. VC爱好者 说：

   2006 年 5 月 28 日下午 10:06

   问题描述：

          有一个3×3的棋盘，其中有0~8九个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态到达目标状态步数最少的解。

          解决八数码问题的常用方法为图搜索法，可用广度优先、深度优先和A*算法实现，其中A*算法又因估价函数的不同而有着不同的搜索时间。

   程序说明：

          在本程序中，用广度优先、深度优先和A*算法分别实现了八数码问题，其中A*算法的估价函数选择的是“不在位”数和当前层数之和，初始状态和目标状态均可由用户设定，目标状态默认为：

   1 2 3
   4 5 6
   7 8 0

           这里是A*算法的可执行程序，由用户输入一组数码，如：

   8 3 5
   1 2 7
   4 6 0

           然后程序会询问用户是否要更改目标，输入N即可。等一会儿（几秒到几十秒）后便可得到结果以及消耗的时间和空间。程序中的Block是指生成的8数码块，以此来衡量空间消耗的多少。

           这里是广度优先的可执行程序，使用方法同上。广度优先算法当步数较多时消耗的时间可能会比A*算法少，但会消耗较多的空间，因此当计算很长一段时间后仍无结果时应按CTRL+C强行退出，谨防死机。

           深度优先算法当问题复杂时时间消耗很多，基本不能用，因此在这里就不给出可执行程序了，需要者可下载下面的源代码自行研究。

   算法简评：

          三种算法在一定条件下均可得到八数码问题的解。但是广度优先算法当目标的深度较深时，产生很多冗余节点，空间消耗很大（在运行中曾造成过死机）。有限深度优先算法在时间或空间复杂度上均没有明显的优势，但如果目标深度较深而且路径选择得当的话，可以较快地得到解答。A*算法可以消耗较少的空间解决问题，但是由于每次选择均需要寻找估价函数最小的节点，因此当深度增加相应的节点数目增加时，A*算法在时间上并不占优势。然而，A*算法总可以在有限的时间内得到问题的解。

   已知可解问题：

   8 3 5    4 3 2     2 0 3
   1 2 7    1 0 5     1 8 5
   4 6 0    6 7 8     4 7 6

           A*算法总可在有限时间内（曾试过75秒）解决文曲星中可解的数字拼图问题。

   源代码：

           这里是程序的源代码，有兴趣的同志可以下载研究，欢迎指教和提问。
3. 虫虫眼62 说：

   2006 年 5 月 29 日上午 10:09

   谢谢，大哥，可是没有源码呀！我是什么都不会的，555，麻烦你传个源码给我好吗？万分感谢！
4. cboy 说：

   2006 年 5 月 29 日下午 3:06

   http://www.chinaoak.com/download/sources/arithmetic/winep_co de.zip

   这是源码