八数码的几解决.doc

《八数码的几解决.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、八数码的几种解决帖子关于是八数码的，是前段时间写的，为了给别人一些搜索的样例。 现在，事差不多完了，代码还留着，觉着放着浪费，又想自己水平过于欠缺，再加上看在C吧的初学者还是占主要，就觉得发在此处共他们学习还是不错的，仅此而已。如果有不知道八数码的问题的， 可以上网一搜，就什么都明白了。 在这里我只用了几种算法实现，其实还有其他方法，我并没有写（如果有人需要，可能我会重新完成）。首先分析下八数码的一些算法吧。1： 深度优先（DFS）：      这个方法起始对八数码非常不好，问题在于搜索过于盲目，搜

2、索深度如果没有限制，有些是根本没必要的（因为八数码的解，大部分集中在20~30步之间）。而且即使搜索到一个解，很可能不是最优解。  所以用DFS解决这个问题并不明智，不过为了显示其不好，我仍然实现，不过在程序中设置最大深度限制为100。2： 宽度优先搜索（BFS）     宽度优先搜索，解决的还不错，经过对hash函数的优化，能使一个20~30步的解在200~300MS内解决（不过其还可以做进一步的优化）。3： 迭代加深搜索     迭代加深搜索，可以说是吸取了宽搜和深搜的优点，同时避免了深搜搜到第

3、一个解的不最优性，和宽搜的使用较大的内存空间。      在这里我也用迭代加深搜索， 仔细一看的人就发现，起使他只是在深搜上稍微做点“手脚”就完毕，但是其思想，虽然显而易见，可我觉得并不容易想到（指当初提出这个算法的时候）。4： 爬山法    爬山法，经常在人工只能里面见得到，由于其高效，实现简单，所以其有时也是很有用的。但是爬山法，也有缺点，就是搜到的解只是局部最优解，而且有陷入“无解”的风险。 爬山法，顾名思意就是一直沿着“最好的方向走”直到“山顶”，就找到解。 爬山法，不像回溯， 在遍历节点时

4、不保存其他非当前最优节点，也就是说，一旦走错了，就不能再后头搜索其他方向。    所以在我写的爬山法中，对于一个解，虽然很多100多步，但是所需的时间确实0MS左右。5： 双向搜索   双向搜索，前后来搜，碰到头，然后一拼接就出了路径。其搜索的节点数要明显必宽搜少许多，所以在程序中，我并未对其做任何优化，他搜索一个解的时间基本上是0MS。6：A*算法   A*算法，不用说，解决这个问题很简单。速度也快，都是0MS。具体的可以参考网上的解释。7：DIA算法   DIA算法可以说是 A* 与 迭代搜索的

5、结合，思想来源于迭代搜索，其实简单的说就是，迭代搜索添加了估价函数。由于时间，当初我并未用该方法实现。 第一个贴的代码是宽搜，由于在hash上做了优化，所以对hash部分做下解释：******************************************对于一个状态，转换为 1 2 3 4 0 5 6 7 8 这样的序列，然后分别对应权值：0 : 8!  , 1 :7!  2 : 6! , .... ,  8:0 !然后用每个数的逆序数乘上权值的和即为改状态的hash表对应的下标。对于上序

6、列对应的hash下标为： 4 * 8! + 0 * 7! + 0 * 6! + 0 * 5! + 0 * 4! + 0 * 3! + 0 * 2! + 0 * 1! + 0 * 0! = 161280----------------------------------------------------------------------另外对于这种hash值计算外，还有一个由上一个状态来推到下一个状态的hash值的规律：假设，移动是有从空格的移动方向来看，并且设空格在序列中的位置为 i，并且是in

7、dex为上一个状态的hash值，则下一个状态的hash值为：               上移：index - 3*8! + a[i-3]! * ( a[i-1] > a[i-3] + a[i-2] > a[i-3] ) - a[i-2]! * ( a[i-2] < a[i-3] ) - a[i-1]! * ( a[i-1] < a[i-3] );                      下移：index + 3*8! - a[i+3]! * ( a[i+1] > a[i+3] + a[i+2] 

8、> a[i+3] ) + a[i+2]! * ( a[i+2] < a[i+3] ) + a[i+1]! * ( a[i+1] < a[i+3] );newindex =             左移：index - 8!           右移：index + 8!上移newindex值的计算程序如下计算(假设，Factorial[9]，分别记录了(8-i)!的值)：newindex -= 3*40320 ; newindex += ( p[ i - 2 ] >