连连看寻路算法

1、主题：讨论连连看寻路算法/全程求解算法 作者：华山论剑 发表时间：2007-11-28 17:51:00 楼主遇到一个算法问题，希望朋友们多给些意见。最近SDK写了个连连看游戏，其中的两点间寻路的算法基本上是用网上的一段代码，全路径求解算法则是自己写的，遇到容易的矩阵可以秒杀，但遇到复杂的则速度就很慢了。希望大家给些意见，改善一下效率。先说全程求解部分。说明：1、如果有解，找出解法；2、如果无解，给出相对最佳路径；3、如果有多解，找到一个就退出；4、连连看的矩阵为10*12(10行，每行12张牌)，加上上下左右要各留一空行以便寻路，矩阵为12*14；5、矩阵中某点值为0表示无牌，否则有牌；6、

2、矩阵不一定是初始状态，因为有时我们玩到一半可能用软件来求解。例子数组：m1214=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,29,3,18,26,9,2,6,33,10,9,4,15,0,0,19,18,29,7,14,9,10,23,34,16,21,15,0,0,21,27,26,2,26,11,30,17,25,14,10,5,0,0,19,12,33,33,31,34,15,11,28,7,8,23,0,0,12,16,27,4,5,21,27,8,1,6,23,4,0,0,19,34,25,1,6,26,25,15,17,12,6,31,0,0,10,4,16,17

3、,31,8,8,7,28,28,34,30,0,0,3,21,5,14,18,2,12,20,20,2,25,1,0,0,30,20,19,31,3,9,14,16,5,29,33,3,0,0,1,20,11,27,28,17,30,18,7,29,11,23,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0这个数组也许是无解的，如果无解，则给出相对最好的解法。基本流程：1、复制矩阵和路径数组为m和way；2、先找一个有牌点p1；3、然后找其它几个配对的点sameN；4、依次检查p1和sameN中的元素是否相通；5、若相通则消去两张牌，若消完则返回；6、没消完再递归寻路。作者：雨中飞

4、燕 发表时间：2007-11-28 17:54:00 第1楼那个叫回溯嘛。 作者：华山论剑 发表时间：2007-11-28 17:56:00 第2楼下面是代码：typedefstructintm1214;pointway604;llk;intleast_left;/最少剩牌数，用于无解时保存最好解法pointshortest_way604;/相对最好解法路径intfind_same(pointp,pointsame,constintm14)/找相同的点inti,j;intnum=0;for(i=1;irow-1;+i)for(j=1;jcol-1;+j)if(mij=mp.xp.y&(i!=p

5、.x|j!=p.y)samenum.x=i;samenum+.y=j;returnnum;BOOLfind_way(llk*v,/llk结构intleft,/剩下牌张constintin14,/矩阵pointwayin4);/全程求解路径inti,j,k;/循环变量intm1214;/矩阵复制品intnum,idx;/对于一个点，有几个相同的intold;/保存旧值pointway604,same10;/路径，相同点的坐标数组pointp;/要找配对的点if(least_left=0)returnTRUE;idx=(120-left)/2;/路径中要更新的位置索引memcpy(m,in,siz

6、eof(m);/矩阵复制品memcpy(way,wayin,sizeof(way);/路径复制品for(i=1;irow-1&least_left;+i)for(j=1;jcol-1&least_left;+j)/缩进太多，将之提前-num1if(mij&least_left)/找到有牌点p.x=i;p.y=j;num=find_same(p,same,m);/缩进太多，将之提前-num2for(k=0;knum&least_left;+k)/找路wayidx0.x=i;wayidx0.y=j;wayidx3.x=samek.x;wayidx3.y=samek.y;if(check_way(w

7、ayidx,m)/check_way是两点间寻路函数if(left=2)/最后的牌清空了least_left=0;save_sol(v,way);returnTRUE;elseif(left-2least_left)/保存最短路径least_left=left-2;memcpy(shortest_way,way,sizeof(way);old=mij;/保存旧值mij=msamek.xsamek.y=0;/消去2张牌find_way(v,left-2,m,way);/递归寻路if(least_left=0)/只要找到一个，从所有的递归中退出returnTRUE;mij=msamek.xsame

8、k.y=old;/恢复2张牌ZeroMemory(void*)&wayidx,sizeof(way0);/恢复路径最后一维(置0)/-num2结束/-num1结束returnFALSE;但是配合两点间的寻路函数，效率不高，像上面的例子数组，算一个晚上也没结果。希望朋友们参考参考，能不能优化优化，最好代码也能简化些，解决了外层的，再来解决两点寻路算法。 作者：华山论剑 发表时间：2007-11-29 8:59:00 第3楼发贴后想到可以有个小改动：find_way(v,left-2,m,way);/递归寻路if(least_left=0)/只要找到一个，从所有的递归中退出returnTRUE;改

9、为：if(find_way(v,left-2,m,way)returnTRUE;虽然意义不大，能简短些且少一个判断总是好事。 作者：华山论剑 发表时间：2007-11-29 15:31:00 第4楼没人再给点意见吗？关于两点寻路的算法也可以啊，我见过有的连连看程序能很快判断有解无解，不至于这么慢啊！ 作者：nyra 发表时间：2007-11-29 21:35:00 第5楼不求最优解的情况下可以这么简化:1.不复制地图,只记录上次消去的牌对2.一次递归消去所有可能的牌对,如果有多种消去方案,可以进栈,也可以任选其一(这个优化可能导致无解,但概率很小)3.提高检查连通的效率.(这个影响很大) 作者

10、：华山论剑 发表时间：2007-11-30 9:18:00 第6楼多谢nyra的建设性意见!1、2可能极大幅度提高效率，但若是解法有限的时候，无解的情况会较多。因为在解法很少甚至是华山一条路的情况下，消牌顺序不同，结果会完全不同。但nyra的建议还是有用，比如对于较难的地图，在两点寻路时，只求找到通路即可，不求最短路径：-|XX比如上面这个，从第一行搜寻，找到路就退出，而不必求最优解：-|XX作者：rickone 发表时间：2007-11-30 16:51:00 第7楼你说的全程求解,是说,让计算机从第一步一直做完吗? 作者：华山论剑 发表时间：2007-11-30 17:53:00 第8楼引

11、用： 你说的全程求解,是说,让计算机从第一步一直做完吗?是的，如果有解且方案很少时，就可能要穷尽所有可能性测试，这时会很慢，还有些可能就无解，则求最佳路径，像上面给的例子地图数组，睡觉前放在电脑里跑，第二天早晨起来还没结果（8个钟左右），只好中断。但对于解法方案多的，就不用反复回溯回去，现有的代码对付就可以秒杀。连连看的复杂度主要来源于同花色牌的重复数量。像这里提到的120张牌的矩阵，如果每种花色重复8次（15种不同花色）和时间90秒以上(消牌后还可以加20秒)，就相当简单，随意连都很少失败。重复6次(20种花色)60秒属于中等，一般可以连过8次以上，再减时间就会更难些。前面这两种用软件求全解

12、几乎不需要什么时间，鼠标按下后马上给出全路径解法。如果每种花色重复4次（30种花色）就绝难，给几小时也难过几关，有30左右的初始矩阵根本就无解，所以要提供几次重新洗牌机会或者直接cut牌功能，但洗牌cut牌也尽量要到最后关头才能用，这样才能得高分。这就是无解时求最短路径的用意。连连看游戏简单又有趣，还是有不少人玩的，我研究连连看兴趣在程序而不在玩，是想做一个连连看外挂，当然网上已经有人做过QQ连连看之类的外挂，所以对于我当然还有拿这个程序练手的成分。 作者：华山论剑 发表时间：2007-11-30 18:14:00 第9楼经过两天时间，发现外层的代码还可以做些优化，主要是取消find_same

13、函数及相关数组。typedefstructintm1214;pointway604;llk;intleast_left;/最少剩牌数，用于无解时保存最好解法pointshortest_way604;/相对最好解法路径BOOLfind_way(llk*v,/llk结构intleft,/剩下牌张constintin14,/矩阵pointwayin4);/全程求解路径inti,j,a,b;/循环变量intm1214;/矩阵复制品intidx;/路径末尾的索引intold;/保存旧值pointway604;/路径idx=(120-left)/2;/路径中要更新的位置索引memcpy(m,in,size

14、of(m);/矩阵复制品memcpy(way,wayin,sizeof(way);/路径复制品/这两个数组还是要复制，不然困难数组有很多无解情况for(i=1;irow-1&least_left;+i)for(j=1;jcol-1&least_left;+j)/缩进太多，将之提前-num1if(mij)/找到有牌点wayidx0.x=i;wayidx0.y=j;/缩进太多，将之提前-forfor(a=1;arow-1;+a)for(b=1;bcol-1;+b)wayidx3.x=a;wayidx3.y=b;if(!(i=a&j=b)&/不是本身点mij=mab&/花色相同check_way(w

15、ayidx,m)/-if1if(left=2)/最后的牌清空了least_left=0;save_sol(v,way);returnTRUE;elseif(left-2least_left)/保存最短路径least_left=left-2;memcpy(shortest_way,way,sizeof(way);old=mij;/保存旧值mij=msamek.xsamek.y=0;/消去2张牌if(find_way(v,left-2,m,way)returnTRUE;/递归寻路，找到一个就退出mij=msamek.xsamek.y=old;/恢复2张牌ZeroMemory(void*)&wayi

16、dx,sizeof(way0);/恢复路径最后一维(置0)/-if1结束/-for结束/-num1结束returnFALSE;上面有消去牌的恢复和路径的恢复，是因为不同的消牌顺序对于结果是大不同的，尤其是复杂的矩阵。简单矩阵可能很少会用到恢复，因为方案很多，大致一条线走下去就解了。复杂矩阵需要反复回溯寻路，计算量极大，所以很慢。rickone兄，你的贴子为什么总比别人的宽很多啊？周末一般不上网，有答复和跟帖的朋友下周一再回复你们及给分，谢谢！ 作者：rickone 发表时间：2007-12-1 14:01:00 第10楼单纯的判断两点是否相连用回溯，全局搜索就显得太不实际了，高手玩的时候也不可

17、能保证不会遇到死锁的情况，然后用道具重新生成，但是高手可能会有一些经验，这些经验可以做为启发式判断依据，或者换个思路，从最基本的什么原因会造成死锁入手，做出快速的判断无解的方法，我觉得如果有解的case，搜起来应该不会很费时。PS：我的帖子宽吗，不觉得啊 作者：华山论剑 发表时间：2007-12-3 8:47:00 第11楼不知是否有误解。这里的全局搜索不是为了搜寻两点间是否相连的，而是组合不同的消牌顺序以找到解法，因为消牌顺序不同，结果大相径庭，比如：A-BAA-AB先消上面两个A，OK。但如果先消左边两个A，就无解了。如果不回溯，只是单线递归下去，就会非常快且简单，但它的意义也基本上没有了

18、，因为它解不了什么难题。 作者：华山论剑 发表时间：2007-12-3 8:58:00 第12楼关于5楼nyra的建议。nyra提出的问题因为之前我也想过，一直以为是需要复制地图的，所以当他提出时也没太细想。可是在随后的调试中，这个念头便浮现出来，在步步跟踪中思考和平时的感觉又不一样，猛然发现地图复制完全不需要！因为在find_way过程中我已经用old保存了值：old=mij;/保存旧值mij=mab=0;/已消去2张牌if(find_way(v,left-2,way)returnTRUE;/递归找路mij=mab=old;/恢复2张牌ZeroMemory(void*)&wayidx,siz

19、eof(way0);/恢复路径，最后一维置为0所以在寻路前只用保留map初值一次以便存盘时用，而在寻路过程中只需要一份就行，值的恢复只需要intold压栈就行了，程序的运行不受任何影响。既然这层想透，路径数组way同样不需要复制，因为递归前的函数就有路径恢复，这样一来，内存的节省将是巨大的：地图数组：m1214=12*14*sizeof(int)=672路径数组：way604=60*4*2(point中的x、y)*sizeof(int)=1920Total：672+1920=2592如果压栈100次(复杂地图有时达几百次)，那么内存占用就是：2592*100=259，200/1024=253M

20、取消两个数组复制后就只有一个intold的压栈，4bytes，就算压栈1000次也只有4K，太小case了。如果设计中隐藏了如此重大的缺陷，就算用汇编，也快不起来。再次谢谢nyra!而且，取消地图和路径数组的复制后，并不影响最优解的寻找。作者：华山论剑 发表时间：2007-12-3 9:10:00 第13楼上面问题修改掉后，很快又发现了另外一个非常重大的改进！之前每次找第一点有个i、j循环，然后第二点是a、b循环，都要遍历整个地图：for(i=1;irow-1;+i)for(j=1;jcol-1;+j)if(val=mij)!=0)/找到有牌点，第一点for(a=1;arow-1;+a)/这里

21、内层循环，i/j共120次for(b=1;bcol-1;+b)if(mab=mij)/找到相同牌点，第二点.a、b的内层循环就是找第二个相同点的循环，假如整个地图搜寻一次(单次循环完为120，复杂地图反复回溯递归，计算要以十亿为基本单位)，那么内层循环就是：120*120=14,400其实，地图就120个点，为什么要次次都重复搜寻呢？能否只搜寻1次呢？无数次的相同重复运算，这是我们程序员不能视若无睹的！改进的方法就是搜寻之前建一个hash表，因为图片用的是麻将，一共只有34种花色，为了方便，0位不用，那么建一个35个元素的hash表就行了：hPath*htab35;hash表中的元素hPath

22、为一链表，存放坐标点和下一链的指针。建链表时为了简单，采用头插法，如果想hash表中的顺序从前面开始，循环时倒过来就行了。那么前面的循环就变成了：intval;hPath*p;for(i=1;irow-1;+i)for(j=1;jnext)/这里循环4次.120次对比就变成花色重复数量的对比了。连连看是同花色牌越少越复杂，这里的比较却是越复杂的比较越少。最复杂的情况是每种花色只有4张牌的情况，这种情况只需要搜寻4次，和120次比较，提高30倍！这两个改进实施以后，速度和以前已有天壤之别，运算结果也完全正确。之前有个变量来限制最大搜寻，这时候改为_int64的最大值也1、2秒就过了，不得不改为用时间来限制。此时心中真是充满了喜悦！之前之所以没有提两点寻路算法，是觉得外层还有很大改进空间。最初为了界面的方便，是用VB来做的，求解一个有解地图要20分钟左右。后来改为用C写的非MFC标准DLL给VB调用，求解一个有解地图速度从1秒以内到1分钟不等，现在，只要是有解地图，基本上都是鼠标一抬起来，解就出来了。这里说的求解都是从第1张自动到最后清完，不是指点两张牌的求解。作者：华山论剑 发表时间：2007-12-4 10:11:00 第14楼上面的代码还隐藏了个逻辑错误，昨天晚上调试了两个多钟才找出问题，其实是个很初级的错误。我有一个地图，最佳解法本来只能解36步(全程1