/ POJ

POJ1077 Eight

这道题是去年暑假就开始做的题,但是去年结构体实现的优先队列没写好,所以一直没AC。半年时光,我的代码风格也从结构体+指针逐步转变为数组模拟,只为提高那一点点效率。这样在使用Dev C++调试的时候也会更方便一些。

搜索

这道题使用启发式的A*搜索。A*的本质是广搜,但是对于只需要出一个可行解的问题会比广搜快。

在广搜的时候,将队列改为优先队列,优先采用最靠近答案的状态来拓展。计算是否更优一般取两部分函数的,一部分是记录已经走的步数,另一部分是估计还要走的步数。这也就是A*算法算启发式算法的地方,因为估计函数一般没有办法获得准确值,估计的很小不代表实际很小。

对于这道题来说,我认为不必要记录已经走的步数。因为我们只需要尽可能快的出答案,不需要答案最短。我使用了int est[]数组来储存估计还需要的步数,估计函数用了曼哈顿距离,即

xixj+yiyj\left |x_ i-x_ j\right |+\left |y_ i-y_ j\right |

康托展开

状态的储存需要压缩。对于这些全排列的哈希有一个特别的方法叫做康托展开。这一看就是组合数学的内容,但是之前没怎么好好用心去思考,所以一直没学懂。网上也没有详细的教程来解释。

个人感觉康托展开和数位DP很相似。求一个全排列的在所有全排列中排第几,也就是求有几个全排列比目标全排列的字典序要小。

就拿这道题n=9n=9作例子吧,设该全排列为a1a2a3a4a5a6a7a8a9a_ 1a_ 2a_ 3a_ 4a_ 5a_ 6a_ 7a_ 8a_ 9,当前考虑的全排列为b1b2b3b4b5b6b7b8b9b_ 1b_ 2b_ 3b_ 4b_ 5b_ 6b_ 7b_ 8b_ 9

  • b1<a1b_ 1<a_ 1,则b1b_ 1a11a_ 1-1种可能,后面的八个数字是全排列,这种情况总共有(a11)×8!(a_ 1-1)\times 8!种可能。
  • b1=a1b_ 1=a_ 1
    • b2<a2b_ 2<a_ 2,考察剩余的数(排除a1a_ 1)有几个数比a2a_ 2小,乘上7!7!就是这种情况的可能数。
    • b2=a2b_ 2=a_ 2,……

哈希的解码原理也是差不多的,但是这个函数花了我半个小时才写对。

其他错了的地方

题目还是没看清楚,rlud的含义搞反了,导致第一次提交WA。