[转] http://bbs.byr.cn/wForum/disparticle.php?boardName=ACM_ICPC&ID=28668&pos=6&page=1

　　

贪食蛇的进化之路

　　

此题是要求计算贪食蛇从一个初始位置把头移动到（0，0）位置需要最少移动的步数。

　　

以下是我的优化过程。

　　

Run id   user id  problem result   memory time  language codelength   submit time

4981334      Accepted     244K  16MS        5548B        2009-04-15 11:04:24

3445390      Accepted     592K  188MS         3546B      2008-05-22 21:24:22

3422325      Accepted     3628K  1672MS       3173B      2008-05-16 16:36:26

3422019      Accepted     13488K 2500MS      2955B      2008-05-16 15:25:00

　　

这几次提交可以说记录我的每一次优化策略的效果。

　　

关键字： bfs   hash   位运算   A*   估价函数   队列  状态

　　

　　

第一次提交（3422019）：这个代码里用的是最传统的BFS思路以及最简单的数据结构

对蛇的状态存储：存下蛇的头的位置，然后记录蛇身每段相对于前一段的位置进行存储。这样一个整数就能搞定

  State = s * R * C + r * C + c;(s 为相对位置，(r,c)为舌头位置)

占用的状态空间为 4^7 * 20 *20 + 20 * 20 + 20

然后就是普通的BFS了，每次从队列头取出节点。利用state算出蛇的头部以及以后每段的位置。然后向四个方向进行扩展。判重开一个很大的bool数组。

总结：这种方法是最容易想到的一种，也是最直接的方法。简单可行。但是消耗的时间多.用来判重需要的空间比较大，消耗的空间也不少。

　　

第一次改进（3422325）：对于上次提交所消耗的时间和空间很是不满意：

   空间主要是消耗：对蛇的状态进行用的bool数组。

时间主要是消耗：每次初始化这么大的数组需要的时间以及状态的扩展。

怎么降低时间和空间的消耗？？？

空间上那就得压缩一下，原来一个bool 8个位只能存一个状态，而我在查询时只要知道这个状态是否存在就行，所以就想到了2进制位，一位一个0/1就能表打我需要的信息了，这个在空间上节省到了第一次提交的1/8了。所以在提交后的效果是时间上优化减少了1000MS空间到了1/4.

         在空间上其实还有一个改进。其实在队列上也用了不少空间。所以可以采用循环队列来处理，这样空间能用的更少。只是我没有这么写。

    总结：在这一步优化当中没有减少对状态的判断以及存储。那么要在时间和空间上有一个质的飞跃就需要减少对状态的扩展——这才是减少空间和时间的关键所在。

　　

第二次改进（3445390）：其实第一次改进，只是利用了一些小的技巧。在算法本质上没有什么改进。要想把时间有一个质的飞跃，就必须在算法上有一个很好的优化。我记得应该是在第一次优化后的第2天，记得还是在晚上睡觉前刷牙的时候，大脑灵光一现想到了一个比较好的优化方法。A star。

     用到Astar 那么首先想到的是估价函数，因为同样的一个问题可能存在着很多估价函数，而且在收敛效果上也存在这很大的差别，所以能选择一个好的估价函数也能给解题带来不错的效果。我这里采用的是：利用一次BFS 计算出（0,0）到各个点的距离，这个距离乘以10 作为我的股价函数。为什么要乘以10呢？这里就是为了扩大我对估计值的影响，更快的向结果收敛，从而减少对状态的扩展。

实践证明这个函数的效果还是不错的。

这一次对蛇的存储也做了些改变，完全利用位运算。

题目范围是20x20 那么存在蛇头位置需要10 bit 而还有7段蛇身又需要14bit。蛇走过的步数用另外一个int存下来。

去重策略，为了简化代码的书写，我直接用了stl里的set来进行状态去重。

众所周知用到Astar就需要一个高级的点的队列——优先队列。同样也是为了代码的书写方便我直接用了stl的priority_queue。。。。。。。stl真是太好用了。

在进行了上述处理后，发现时间上确实有了实质性的改变，缩小到了188MS。

做到这里，其实我知道时间上还存在优化空间，因为这个程序里有两个耗时的东东存在一个set 一个queue。Stl——耗时的魔鬼啊。

优化总结：A* 的实质是减少了状态的扩展，从而在时间和空间上有了较大的优化

　　

第三次改进：这个改进距离上次改进有一年的时间差，最近又有人提起了这题。想想还是继续优化下吧。

   改进点1：自己用c++实现了一个优先队列的模版。

   改进点2：利用位存储来进行hash对状态判重。

改进后的效果变成了244K  16MS

总结：没有最好，只有更好

基本也算满意了。

 　　

 心得： 每一次需要质的飞跃，就需要在算法上或者说在思想上有质的改变。小的技巧只是在小范围超越了别人，优势太过于微小。所以大家在平时还是把精力多多的放在算法的学习上，小的技巧在平时敲代码的过程中慢慢体会掌握，慢慢积累就行了。

希望这个分享能给大家一点点帮助

 　　　　

PS：大家可以考虑写一个perfect 的代码，组织如下：

        A*；

    蛇的存储： 10bit 存下蛇头　14bit 存下蛇身 8bit存下蛇走的步数。我用程序测过步数不会超过255.这样一个int就搞定了，所以这么存进一步减少内存。

    优先队列 自己实现

    Hash 位判重

    估价函数的乘数因子应该还可以更合理。

其实最后蛇的状态不会超过2048 这个也是我用程序测出来的。

 　　

如果这样实现了，我想离〇MS就远了。不过这么做的成本比较高。时间消耗比较多。意义不是很大。不过这样对位运算和A*有一个更深刻的认识。也能锻炼下自己的代码能力哈。