连连看的A*搜索 VS 深度优先搜索

这周在测试连连看的时候发现了严重的搜索算法错误问题。原先我用的A*只是比较两个节点的转弯次数，使用的hash标记就是遍历过的节点不能再走。但是在这样的情况下就不能保证走出正确的路径。如图1所示。S为起点，E为终点，黑色表示墙壁。从S开始遍历的时候路径1和2走到红色位置的转弯次数是相同的，然而在往下走一步1就永远走不到终点了（转弯次数超过了两次）。所以这样的hash标记是行不通的。不能一棒子打死走过的地方就不让走。

既然设置了转弯次数，hash标记可以使用转弯次数来设定。如图2所示。图中的数字表示从起点到该节点的转弯次数。在遍历的时候通过判断之前到达该节点的时候转弯次数是否大于等于当前节点的转弯次数。这样上面所说的路径2就可以顺利通过红色位置。到了下一个节点通过判断路径2的转弯次数少于路径1那么只需要保留路径2走到终点即可。

注意：此时已经没必要再用转弯次数作为A*搜索的启发函数了。

图 2.

虽然这样做避免了搜索不到终点的致命错误，但是效率上并不可观。因为遍历到某个点转弯次数相同的情况很多，所以这样的搜索带来了大量的不必要的遍历。后来我加了一个当前节点到终点的步数记录。将步数这个条件作为启发函数。这样做可以将最可能打到终点的节点优先搜索。效率有显著的提高。

但是我又想用这A*算法浪费了那么多的内存用来记录各种中间值，深搜的话会不会更加快。因为只要超过2次转弯就不必继续遍历。于是我写了个深搜试了一下，的确比之前我个人认为已经不能再优化的A*算法要快的多。当然我测试的地图是15*15的，并且A*算法搜索的路径还可以将步数控制在最短。而深搜的递归会大量调用函数堆栈。但是……在这个问题上A*的优势并没有体现出来，1.连连看是不管距离远近的 2.转弯次数不超过两次深搜的递归次数并不多。

综上所述A*可以解决大多数拥有各种条件的搜索问题，但是对于连连看的搜索在15*15的地图规模下深搜的确优于A*，内存和时间都比较省，时间几乎每次都是0的。

最后我保留了两个算法函数。可能有人会看不懂什么A*啊，什么启发式搜索啊，什么hash…。其实A*就是广搜加一个比较函数，那个比较函数就是启发函数，通过它来排列队列中节点的先后顺序决定哪些节点应该先搜索。上文提到的hash标记，即最简单的hash。举个例子就是搜索地图的时候标记已走过的地方防止重复遍历。其实这些东西以前ACM的时候都用过，一直到不知道专业名词….

顺便提一下，杭电上的那道连连看数据太弱了，测试数据没有包含我以上提到的情况。

蛋疼的差事

我表哥现在在浦江做婚纱摄影，叫我给他做个网站，为什么…为什么会这样。我真的不会做网站，但是第一次和他说的时候我说你要的那点屁功能随便写写就是了，你只要把图片资料什么的弄来就好了。结果他发给我一个excel写的都是写什么…居然还写了一个网址www.pjhssy.com 我顿时无语，在他眼里这域名也是程序员写出来的。他的原话是这样的：反正你全部帮我搞定，写好了买什么空间什么的都弄好，除了买空间的钱你其他的想都别想（我还没想这事他倒是事先说明了，好像我欠他钱一样- -）。硬的不行他又说难道你忘了以前我在杭州的时候我是怎么对你的，每次来我这里玩都是热情接待，上厕所我都让你先去…。还有一大堆切扁的废话，很无奈。

触动

参观了几个同事的住处，房间惨不忍睹…..人全部在玩游戏…..，两个用iphone的同事房间就和卫生间一样大，只有一张床和一个放电脑的小桌子，衣服就挂在一根长度最多一米的木条上，iphone放在破桌子的隔层，这样的场景很不协调，感觉就像倾家荡产买了个手机…。对于工作生活他们似乎没有目标，对于这份工作似乎并不是自己的兴趣，反而像读书是自己不得不做的事情。人生怎能如此无聊！

也看了我即将要搬进去的地方，一个字“大”，两个字“豪华”！哈哈，阳台、独立卫生间，good。650/月very good。

既然要做这个行业绝对不能停止学习，绝对不能满足现状，不然仅仅在公司的框架上填空，毫无创造性一点激情也没有。

我留在这里工作的目标，要自己写一个完完全全的网络游戏，可以很小，但是要包括多线程、数据库、安全性考虑等。游戏模块要尽可能多的使用C++的特性，将书上看过但是没用过的东西都试试。到时候再换工作也不必要担心自己的能力问题。

吃了晚饭之后走在学源街上，由于是暑假学生比较少，黄昏夕阳，安静的街道很美。

陈元杰

2012/7/22