http://www.cr173.com/html/18295_1.html
第一种、第二种模型
分析右上角的的2，其周围的未知块a,b两块，等于其周围雷数，故可判断出a,b都是雷；接下来，分析下面的2，其周围共有3个未显示的块a,b,c，其中a,b已判断出为雷，即周围已判断的雷数等于其雷数时，则可判断剩下的块都不是雷，即c块不是雷。
这两种模型，一种是判断出雷、一种是判断出没有雷，这是地球人都知道的扫雷方法。而接下来的模型或许只有扫雷高手或者数学高手才知道~~
第三种模型
我先做一个大胆的判断，c块没有雷！！且听我慢慢道来~
根据两个显示为1的块，可得如下的式子：
a+b=1 (1)
d+e=1 (2)
表示a,b中有且只有一个雷，d,e有且只有一个雷，
根据显示为2的块，可得：
a+b+c+d+e=2 (3)
表示abcde中有且只有两个雷
根据(1)(3)，可得
c+d+e=1 (4)
根据(2)(4)可得， c=0 ，所以c块肯定无雷，可放心地揭开。
这种模型可以说在扫雷中应用得最精妙，看似无法判断的情况，通过这样的计算就可确定出哪里是雷或者哪里不是雷。
第四种模型 - 数学概率
上面三种模型都属于可确定判断的范畴，而在扫雷中经常会遇到无法确定判断的死局。这时就得用到数学工具——概率，来进行最优判断。
如图所示显示为3周围有雷的概率很容易计算出：3/8（这是比较简单的情况）。再看下面的图
当点开两个"8邻接"距离小于等于2的块时，它们周围有雷的概率就不那么容易判断了（上面a,b,c有雷的概率分别是多少）
先看游戏界面，如下：
在游戏开始时，如何出现这样的情况，我们可以认为游戏中未显示块按概率相等可分为四个区域，其中a,b,c是其中的三个区域（a区域指上面的5个块，b区域指中间的3个块，c区域指下面的5个块），再加上不与已揭开块相邻的所有块构成一个区域d（d区域含有465块）。那么这四个区域中哪个区域有雷的概率最小呢？
这里直接说明所使用的数学方法叫做——条件概率和全概率公式。
条件概率可以说是计算机领域的一个功臣，由其发展而来的“统计语言模型”实现了机器翻译、语音识别、汉字识别等一系列的用传统方法很难解决的问题。而以其为基础的“贝叶斯公式”在图像处理、决策支持系统和博弈论中有着广泛的应用。
维基百科中给的定义是：条件概率就是事件A在另外一个事件B已经发生条件下的发生概率。条件概率表示为P（A|B），读作“在B条件下A的概率”。
而全概率为：
假设{ Bn : n = 1, 2, 3, ... } 是一个概率空间的有限或者可数无限的分割，且每个集合Bn是一个可测集合，则对任意事件A有全概率公式：
又因为
此处Pr(A | B)是B发生后A的条件概率，所以全概率公式又可写作：
用自己的话说，条件概率是在某件事发生的情况下，另一件事的概率；全概率是将所有情况的概率加起来。
而在扫雷游戏中有什么“所有情况”呢？
看上面的游戏场景，a,b,c所占的13个块，如果仅仅根据上面所显示的"1","2"，可以说这13个块中，雷的总数可以有2个，也可以有3个！！并且有2个或者3个的概率分别是1/2。
那么其情况如下：
上表说明当雷数为2时，abc有雷的概率分别为0,1/3,1/5；当雷数为3时，abc有雷的概率分别为1/5,0,2/5。
可算出
a区域有雷的概率为0*1/2+(1/5)*(1/2)=1/10
b区域有雷的概率为(1/2)*(1/3)+0*1/2=1/6
c区域有雷的概率为(1/2)*(1/5)+(1/2)*(2/5)=3/10
而d区域的概率同理也算出为(1/2)*(97/465)+(1/2)*(96/465)=193/930
可知，a区域有雷的概率最小，故可以在此5块中随机选一块点击了，然后一切就交给上苍了~~（在不用类似查看内存的方法的情况下，人做的就只有这么多了）
到此，数学原理已介绍完毕，用一句话总结，即，先找出按区域划分的未显示块，然后分类讨论这些区域中雷的总个数。接下来的一篇博文（也是本系列最后一篇），将介绍如何将上面的数学运算用程序代码实现。
No comments:
Post a Comment