连连看寻路算法Word文档格式.docx
- 文档编号:4916121
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:15
- 大小:24.55KB
连连看寻路算法Word文档格式.docx
《连连看寻路算法Word文档格式.docx》由会员分享,可在线阅读,更多相关《连连看寻路算法Word文档格式.docx(15页珍藏版)》请在冰点文库上搜索。
10,
4,
15,
19,
7,
14,
23,
34,
16,
21,
27,
11,
30,
17,
25,
5,
12,
31,
28,
8,
1,
20,
0
}
这个数组也许是无解的,如果无解,则给出相对最好的解法。
基本流程:
1、
复制矩阵和路径数组为m和way;
2、
先找一个有牌点p1;
3、
然后找其它几个配对的点same[N];
4、
依次检查p1和same[N]中的元素是否相通;
5、
若相通则消去两张牌,若消完则返回;
6、
没消完再递归寻路。
雨中飞燕
54:
第1楼
那个叫回溯嘛。
。
56:
第2楼
下面是代码:
typedef
struct
int
m[12][14];
point
way[60][4];
}llk;
least_left;
//最少剩牌数,用于无解时保存最好解法
shortest_way[60][4];
//相对最好解法路径
find_same(point
p,
same[],
const
m[][14])
{
//找相同的点
i,
j;
num
0;
for
(i=1;
i<
row-1;
++i)
(j=1;
j<
col-1;
++j)
if
(
m[i][j]==m[p.x][p.y]
&
(i!
=p.x||j!
=p.y)
)
same[num].x
i;
same[num++].y
}
return
num;
BOOL
find_way(llk
*v,
//llk结构
left,
//剩下牌张
in[][14],
//矩阵
wayin[][4]);
//全程求解路径
j,
k;
//循环变量
//矩阵复制品
num,
idx;
//对于一个点,有几个相同的
old;
//保存旧值
way[60][4],
same[10];
//路径,相同点的坐标数组
p;
//要找配对的点
(least_left==0)
TRUE;
idx
(120
-
left)
/
2;
//路径中要更新的位置索引
memcpy(m,
in,
sizeof(m));
memcpy(way,
wayin,
sizeof(way));
//路径复制品
row-1
col-1
//缩进太多,将之提前------------num1
(m[i][j]
least_left)
//找到有牌点
p.x
p.y
find_same(p,
same,
m);
//缩进太多,将之提前------------num2
(k=0;
k<
++k)//找路
way[idx][0].x
way[idx][0].y
way[idx][3].x
same[k].x;
way[idx][3].y
same[k].y;
(check_way(way[idx],
m))//check_way是两点间寻路函数
(left==2)
//最后的牌清空了
least_left
save_sol(v,
way);
else
(left-2<
least_left)//保存最短路径
left
memcpy(shortest_way,
way,
old
m[i][j];
m[i][j]
m[same[k].x][same[k].y]
//消去2张牌
find_way(v,
m,
//递归寻路
(least_left==0)
//只要找到一个,从所有的递归中退出
//恢复2张牌
ZeroMemory((void*)&
way[idx],
sizeof(way[0]));
//恢复路径最后一维(置0)
}//-----------------------------num2结束
}//-----------------------------num1结束
FALSE;
但是配合两点间的寻路函数,效率不高,像上面的例子数组,算一个晚上也没结果。
希望朋友们参考参考,能不能优化优化,最好代码也能简化些,解决了外层的,再来解决两点寻路算法。
2007-11-298:
59:
第3楼
发贴后想到可以有个小改动:
改为:
(find_way(v,
way))
虽然意义不大,能简短些且少一个判断总是好事。
2007-11-2915:
31:
第4楼
没人再给点意见吗?
关于两点寻路的算法也可以啊,我见过有的连连看程序能很快判断有解无解,不至于这么慢啊!
nyra
2007-11-2921:
35:
第5楼
不求最优解的情况下可以这么简化:
1.不复制地图,只记录上次消去的牌对
2.一次递归消去所有可能的牌对,如果有多种消去方案,可以进栈,也可以任选其一
(这个优化可能导致无解,但概率很小)
3.提高检查连通的效率.(这个影响很大)
2007-11-309:
18:
第6楼
多谢nyra的建设性意见!
1、2可能极大幅度提高效率,但若是解法有限的时候,无解的情况会较多。
因为在解法很少甚至是华山一条路的情况下,消牌顺序不同,结果会完全不同。
但nyra的建议还是有用,比如对于较难的地图,在两点寻路时,只求找到通路即可,不求最短路径:
|
|
X
Z
X
比如上面这个,从第一行搜寻,找到路就退出,而不必求最优解:
rickone
2007-11-3016:
第7楼
你说的'
全程求解'
是说,让计算机从第一步一直做完吗?
2007-11-3017:
53:
第8楼
引用:
是的,如果有解且方案很少时,就可能要穷尽所有可能性测试,这时会很慢,还有些可能就无解,则求最佳路径,像上面给的例子地图数组,睡觉前放在电脑里跑,第二天早晨起来还没结果(8个钟左右),只好中断。
但对于解法方案多的,就不用反复回溯回去,现有的代码对付就可以秒杀。
连连看的复杂度主要来源于同花色牌的重复数量。
像这里提到的120张牌的矩阵,如果每种花色重复8次(15种不同花色)和时间90秒以上(消牌后还可以加20秒),就相当简单,随意连都很少失败。
重复6次(20种花色)60秒属于中等,一般可以连过8次以上,再减时间就会更难些。
前面这两种用软件求全解几乎不需要什么时间,鼠标按下后马上给出全路径解法。
如果每种花色重复4次(30种花色)就绝难,给几小时也难过几关,有30%左右的初始矩阵根本就无解,所以要提供几次重新洗牌机会或者直接cut牌功能,但洗牌cut牌也尽量要到最后关头才能用,这样才能得高分。
这就是无解时求最短路径的用意。
连连看游戏简单又有趣,还是有不少人玩的,我研究连连看兴趣在程序而不在玩,是想做一个连连看外挂,当然网上已经有人做过QQ连连看之类的外挂,所以对于我当然还有拿这个程序练手的成分。
2007-11-3018:
14:
第9楼
经过两天时间,发现外层的代码还可以做些优化,主要是取消find_same函数及相关数组。
a,
b;
//路径末尾的索引
//路径
//这两个数组还是要复制,不然困难数组有很多无解情况
(m[i][j])
//缩进太多,将之提前----------------for
(a=1;
a<
++a)
(b=1;
b<
++b)
a;
(!
(i==a
j==b)
//不是本身点
m[i][j]==m[a][b]
//花色相同
check_way(way[idx],
m)
{//-----------------------------if1
//递归寻路,找到一个就退出
}//-----------------------------if1
结束
}//------------------------------for
}//---------------------------------num1结束
上面有消去牌的恢复和路径的恢复,是因为不同的消牌顺序对于结果是大不同的,尤其是复杂的矩阵。
简单矩阵可能很少会用到恢复,因为方案很多,大致一条线走下去就解了。
复杂矩阵需要反复回溯寻路,计算量极大,所以很慢。
rickone兄,你的贴子为什么总比别人的宽很多啊?
周末一般不上网,有答复和跟帖的朋友下周一再回复你们及给分,谢谢!
2007-12-114:
01:
第10楼
单纯的判断两点是否‘相连’用回溯,全局搜索就显得太不实际了,高手玩的时候也不可能保证不会遇到‘死锁’的情况,然后用道具重新生成,但是高手可能会有一些经验,这些经验可以做为启发式判断依据,或者换个思路,从最基本的‘什么原因会造成死锁’入手,做出快速的判断‘无解’的方法,我觉得如果有解的case,搜起来应该不会很费时。
PS:
我的帖子宽吗,不觉得啊
2007-12-38:
47:
第11楼
不知是否有误解。
这里的全局搜索不是为了搜寻两点间是否相连的,而是组合不同的消牌顺序以找到解法,因为消牌顺序不同,结果大相径庭,比如:
A
B
A
B
先消上面两个A,OK。
但如果先消左边两个A,就无解了。
如果不回溯,只是单线递归下去,就会非常快且简单,但它的意义也基本上没有了,因为它解不了什么难题。
58:
第12楼
关于5楼nyra的建议。
nyra提出的问题因为之前我也想过,一直以为是需要复制地图的,所以当他提出时也没太细想。
可是在随后的调试中,这个念头便浮现出来,在步步跟踪中思考和平时的感觉又不一样,猛然发现地图复制完全不需要!
!
因为在find_way过程中我已经用old保存了值:
m[a][b]
//已消去2张牌
way))
//递归找路
//恢复路径,最后一维置为0
所以在寻路前只用保留map初值一次以便存盘时用,而在寻路过程中只需要一份就行,值的恢复只需要int
old压栈就行了,程序的运行不受任何影响。
既然这层想透,路径数组way同样不需要复制,因为递归前的函数就有路径恢复,这样一来,内存的节省将是巨大的:
地图数组:
12
*
14
sizeof(int)
672
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 连连 看寻路 算法