连连看寻路算法

主题：[讨论]连连看寻路算法/全程求解算法作者：华山论剑发表时间：2007-11-2817:51:00楼主遇到一个算法问题，希望朋友们多给些意见。最近SDK写了个连连看游戏，其中的两点间寻路的算法基本上是用网上的一段代码，全路径求解算法则是自己写的，遇到容易的矩阵可以秒杀，但遇到复杂的则速度就很慢了。希望大家给些意见，改善一下效率。先说全程求解部分。说明：1、如果有解，找出解法；2、如果无解，给出相对最佳路径；3、如果有多解，找到一个就退出；4、连连看的矩阵为10*12(10行，每行12张牌)，加上上下左右要各留一空行以便寻路，矩阵为12*14；5、矩阵中某点值为0表示无牌，否则有牌；6、矩阵不一定是初始状态，因为有时我们玩到一半可能用软件来求解。例子数组：m[12][14]={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,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、然后找其它几个配对的点same[N]；4、依次检查p1和same[N]中的元素是否相通；5、若相通则消去两张牌，若消完则返回；6、没消完再递归寻路。作者：雨中飞燕发表时间：2007-11-2817:54:00第1楼那个叫回溯嘛。。。。作者：华山论剑发表时间：2007-11-2817:56:00第2楼下面是代码：typedefstruct{intm[12][14];pointway[60][4];}llk;intleast_left;//最少剩牌数，用于无解时保存最好解法pointshortest_way[60][4];//相对最好解法路径intfind_same(pointp,pointsame[],constintm[][14]){//找相同的点inti,j;intnum=0;for(i=1;irow-1;++i)for(j=1;jcol-1;++j){if(m[i][j]==m[p.x][p.y]&&(i!=p.x||j!=p.y)){same[num].x=i;same[num++].y=j;}}returnnum;}BOOLfind_way(llk*v,//llk结构intleft,//剩下牌张constintin[][14],//矩阵pointwayin[][4]);//全程求解路径{inti,j,k;//循环变量intm[12][14];//矩阵复制品intnum,idx;//对于一个点，有几个相同的intold;//保存旧值pointway[60][4],same[10];//路径，相同点的坐标数组pointp;//要找配对的点if(least_left==0)returnTRUE;idx=(120-left)/2;//路径中要更新的位置索引memcpy(m,in,sizeof(m));//矩阵复制品memcpy(way,wayin,sizeof(way));//路径复制品for(i=1;irow-1&&least_left;++i)for(j=1;jcol-1&&least_left;++j)//缩进太多，将之提前------------num1if(m[i][j]&&least_left)//找到有牌点{p.x=i;p.y=j;num=find_same(p,same,m);//缩进太多，将之提前------------num2for(k=0;knum&&least_left;++k)//找路{way[idx][0].x=i;way[idx][0].y=j;way[idx][3].x=same[k].x;way[idx][3].y=same[k].y;if(check_way(way[idx],m))//check_way是两点间寻路函数{if(left==2)//最后的牌清空了{least_left=0;save_sol(v,way);returnTRUE;}else{if(left-2least_left)//保存最短路径{least_left=left-2;memcpy(shortest_way,way,sizeof(way));}old=m[i][j];//保存旧值m[i][j]=m[same[k].x][same[k].y]=0;//消去2张牌find_way(v,left-2,m,way);//递归寻路if(least_left==0)//只要找到一个，从所有的递归中退出returnTRUE;m[i][j]=m[same[k].x][same[k].y]=old;//恢复2张牌ZeroMemory((void*)&way[idx],sizeof(way[0]));//恢复路径最后一维(置0)}}}//-----------------------------num2结束}//-----------------------------num1结束returnFALSE;}但是配合两点间的寻路函数，效率不高，像上面的例子数组，算一个晚上也没结果。希望朋友们参考参考，能不能优化优化，最好代码也能简化些，解决了外层的，再来解决两点寻路算法。作者：华山论剑发表时间：2007-11-298:59:00第3楼发贴后想到可以有个小改动：find_way(v,left-2,m,way);//递归寻路if(least_left==0)//只要找到一个，从所有的递归中退出returnTRUE;改为：if(find_way(v,left-2,m,way))returnTRUE;虽然意义不大，能简短些且少一个判断总是好事。作者：华山论剑发表时间：2007-11-2915:31:00第4楼没人再给点意见吗？关于两点寻路的算法也可以啊，我见过有的连连看程序能很快判断有解无解，不至于这么慢啊！作者：nyra发表时间：2007-11-2921:35:00第5楼不求最优解的情况下可以这么简化:1.不复制地图,只记录上次消去的牌对2.一次递归消去所有可能的牌对,如果有多种消去方案,可以进栈,也可以任选其一(这个优化可能导致无解,但概率很小)3.提高检查连通的效率.(这个影响很大)作者：华山论剑发表时间：2007-11-309:18:00第6楼多谢nyra的建设性意见!1、2可能极大幅度提高效率，但若是解法有限的时候，无解的情况会较多。因为在解法很少甚至是华山一条路的情况下，消牌顺序不同，结果会完全不同。但nyra的建议还是有用，比如对于较难的地图，在两点寻路时，只求找到通路即可，不求最短路径：------||||||XＺＺＺX比如上面这个，从第一行搜寻，找到路就退出，而不必求最优解：------||XＺＺＺX作者：rickone发表时间：2007-11-3016:51:00第7楼你说的'全程求解',是说,让计算机从第一步一直做完吗?作者：华山论剑发表时间：2007-11-3017:53:00第8楼引用：你说的'全程求解',是说,让计算机从第一步一直做完吗?是的，如果有解且方案很少时，就可能要穷尽所有可能性测试，这时会很慢，还有些可能就无解，则求最佳路径，像上面给的例子地图数组，睡觉前放在电脑里跑，第二天早晨起来还没结果（8个钟左右），只好中断。但对于解法方案多的，就不用反复回溯回去，现有的代码对付就可以秒杀。连连看的复杂度主要来源于同花色牌的重复数量。像这里提到的120张牌的矩阵，如果每种花色重复8次（15种不同花色）和时间90秒以上(消牌后还可以加20秒)，就相当简单，随意连都很少失败。重复6次(20种花色)60秒属于中等，一般可以连过8次以上，再减时间就会更难些。前面这两种用软件求全解几乎不需要什么时间，鼠标按下后马上给出全路径解法。如果每种花色重复4次（30种花色）就绝难，给几小时也难过几关，有30％左右的初始矩阵根本就无解，所以要提供几次重新洗牌机会或者直接cut牌功能，但洗牌cut牌也尽量要到最后关头才能用，这样才能得高分。这就是无解时求最短路径的用意。连连看游戏简单又有趣，还是有不少人玩的，我研究连连看兴趣在程序而不在玩，是想做一个连连看外挂，当然网上已经有人做过QQ连连看之类的外挂，所以对于我当然还有拿这个程序练手的成分。作者：华山论剑发表时间：2007-11-3018:14:00第9楼经过两天时间，发现外层的代码还可以做些优化，主要是取消find_same函数及相关数组。typedefstruct{intm[12][14];pointway[60][4];}llk;intleast_left;//最少剩牌数，用于无解时保存最好解法pointshortest_way[60][4];//相对最好解法路径BOOLfind_way(llk*v,//llk结构intleft,//剩下牌张constintin[][14],//矩阵pointwayin[][4]);//全程求解路径{inti,j,a,b;//循环变量intm[12][14];//矩阵复制品intidx;//路径末尾的索引intold;//保存旧值pointway[60][4];//路径idx=(120-left)/2;//路径中要更新的位置索引memcpy(m,in,sizeof(m));//矩阵复制品memcpy(way,wayin,sizeof(way));//路径复制品//这两个数组还是要复制，不然困难数组有很多无解情况for(i=1;irow-1&&least_left;++i)for(j=1;jcol-1&&least_left;++j)//缩进太多，将之提前------------num1if(m[i][j])//找到有牌点{way[idx][0].x=i;way[idx][0].y=j;//缩进太多，将之提前----------------forfor(a=1;arow-1;++a)for(b=1;bcol-1;++b){way[idx][3].x=a;way[idx][3].y=b;if(!(i==a&&j==b)&&//不是本身点m[i][j]==m[a][b]&&//花色相同check_way(way[idx],m)){//-----------------------------if1if(left==2)//最后的牌清空了{least_left=0;save_sol(v,way);returnTRUE;}else{if(left-2least_left)//保存最短路径{least_left=left-2;memcpy(shortest_way,way,sizeof(way));}old=m[i][j];//保存旧值m[i][j]=m[same[k].x][same[k].y]=0;//消去2张牌if(find_way(v,left-2,m,way))returnTRUE;//递归寻路，找到一个就退出m[i][j]=m[same[k].x][same[k].y]=old;//恢复2张牌ZeroMemory((void*)&way[idx],sizeof(way[0]));//恢复