图－:
0,0,0,0,0,0,0,0,0,0
0,8,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,9,0
0,0,0,0,0,0,0,0,0,0
这是
张连连看
地图
假设标8和9部分是两张相同牌
在
矩阵中0表示没有牌大于1表示有牌至于是什么牌那是随机了 不要告诉我
你说“布局算法”是指如何把牌刚刚好放上去那个无所谓什么 算法
你只要首先在地图中准备好偶数个1在布牌时保证每种牌是偶数个 (区别种类
牌用大于1数来表示)相应地放入每个1位置上就可以了 、计算地图上这两张牌能不能连通(当然能了哈哈) 这是连连看寻路算法
第步 先定义
下两张牌能连充分条件: 1.两张牌是同
种 2.两张牌的间有
条全是0路可以连通 3.这
条路不能有两个以上拐角(corner) 满足这 3个条件
就可以认为这两张牌是可以连 首先
我们依据前两个条件来完成个基本寻路算法 我们
目是从8到9找出条可以连通路来 那么很明显从8到9
第步其有 4个方向可以选择分别是东南西北 (e,s,w,n以中国地图方向为标准) 4个方向
在第步中我们首先假设 4 个方面没有任何优劣
那么我可以任意选择个方向移动那就是东面吧 图 2:
0,0,0,0,0,0,0,0,0,0
0,8,－8,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,9,0
0,0,0,0,0,0,0,0,0,0
我从8向东移动了
步所以到达了-8位置我的所以可以移到-8位置很明显 是
-8位置上原来是个0表示没有牌阻挡 那么现在寻路
问题就变成了如何从－8找连通9路了！ [Page]说到这里应该明白了吧
好多费话有点像娘们在说话 所以目前
寻路算法归结为个递归算法基本问题 先从8到找到下
个结点－8再用同样规则从－8找到下个结点比如－88 图 3:
0,0,0,0,0,0,0,0,0,0
0,8,－8,－88,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,9,0
0,0,0,0,0,0,0,0,0,0
如果
直都能OK没有阻碍话最后找到了9就算成功以如要有步不能走下去了 就再退回上个结点
向别方向发展都不行就再退回上级结点再向别方向发展 这里
逻辑就是递归思想了 用这样
思路方法写出来算法已经能在最优情形下用了比如从8到－88哈哈 但在稍微复杂
情况下会产生奇多递归结点P4机也跑不动啊我试过哈哈 那么第 2步就是为(e,s,w,n) 4个方向加权
也就是让它们的间有个优先权说白了就 是先试哪
条路决定法则应该有好几个吧比如以9号位置来看它处于8号东南面 那试路时当然应当优先选择东面和南面
再比如9号如果牌8号正东面那当然是选择正东了 再比如
当走到－8位置时明显只能再走 3个方向它是不能回头 经过这样
处理递归算法生成结点数会明显变少会更快找到成功路但性能在最坏情况 下没有本质改变
接下来
第 3步我们把第 3个充分条件加进来来解决根本问题 3.这
条路不能有两个以上拐角(corner) 按照面向对象
思想很自然我给每个在递归算法中生成位置结点加上了个corner属性 来记录这条路到目前为止拐了几个角
这样
下子就好办了啊如果发现这个结点已经拐了两个弯时如果要再拐弯或者到达9的前注定 要再增加cornor时
就果断over返回上级结点 好
就说到这儿吧不能再多说了否则就是等于把代码公开了哈哈 注意
要把 2、 3两步条件综合起来详细规划个个可能性尽可能提早让不可能结点OVER 这就是提高性能
关键吧你算法预见性越强性能就越高吧 我们
算法在赛扬500256M机器上10万次平均结果是次运算花时不超过0.1毫秒,算得还不
精确
速度确实很快在很坏情形下产生最大结点数是690几个这样必然会很快 详细数据已经记不清了 说了这么多了
应当明白第步连通算法思路了吧我所知道都已经尽可能讲出来了 [Page]这个算法完全是自己按照连连看
特点度身定做是步步test出来所以我个人 觉得是很自然
没有任何高深地方完成后性能也很好这才觉得是如此简单相信大家 仔细看看就能写出自己
算法来吧 2、整个地图有没有解？？？可以连通
总牌数？ 这是
个问题 解决这个问题的前
我们先来解决提示功能(h
)就是为玩家提供提示哪对牌可以连 通
我
做法是先把整个地图中相同牌归到起用也好链表也好 像这样
4,4,4,4
5,5,5,5
6,6,6,6
......
然后计算比如4个4的间有哪两对可以连
至于如何判断能不能连第步算法已经实现了吧哈哈 发现有可以连牌就退出来告诉玩家这两张牌可以连啊！ 这就OK了
这完全是建立在第
步算法基础上实现 好
h功能可以了 那么
整个地图没有解算法是不是出来了？ 是
如果找不到可以h牌那当然就是没有解了！ 把所有可以h
对数记下来就是总可以连通数了 至此
和连连看所有算法有关问题解决完毕 第 2步算法
实现明显开销要大很多最坏情况应当会是单次连通算法计算量大约50倍以上 (和牌
总数量和摆位置有关)还好在般服务器上单次连通计算花时间实在太少了 实际运行中完全可以很流畅
以上数据都是我估计理论值实际测试时直没有问题 我也懒得计算出真正比较可靠
均值了 这
部分也是我认为可以有所改进部分公开出来也希望大家能提供些更好更巧妙 思路方法我觉得我计算连通数和有无解思路方法是比较笨思路方法几乎是仗着基本算法快 个
个算出来有没有更好思路方法呢？期待中我也会再想想太忙太懒主要是懒觉得 可以用就行了
最新评论