人生第一个A*算法~好激动……

八数码难题……又称八数码水题,首先要理解一些东西:

1.状态可以转化成整数,比如状态:
1 2 3
4 5 6
7 8 0

  可以转化成:123456780这个整数

2.看上去有9×9种不同状态,实际上只有9!种(即9×8×7×6×5×4×3×2×1)种状态,哈希表大小开成一个大素数即可,每次用这个大素数去对当前的状态(整数)取余获得哈希表的键值

3.移动一个数码到0这个位置可以理解成0这个数码移动到四周的数码的位置

我先用广搜水过,速度大约是20ms左右:

又用了双向广搜试了试,速度大概是10ms左右:

然后我一条路走到黑,研究起了A*算法……

A*算法我现在研究也不透彻……也是一种广搜,它通过一个估值函数,估算当前扩展出的新状态到目标状态的代价,再选中代价最小的新状态扩展,直到扩展到目标状态……

非常快,速度大概是0~1ms

先转发一个写A*算法很不错的博客:http://www.cnblogs.com/yanlingyin/archive/2012/01/15/2322640.html

再贴个代码: