引言 高级的最大IOE记录在多年前就被刷到3.372。 只是多年以后才由朱耀宇证明,IOE的上限为3.4。本文是对《扫雷中IOE的最大可能值及其证明》的内容的梳理,以及补充其中省略的步骤。采用严谨但是通俗的语言,力求使得更多的人能够容易地理解这个证明,了解为什么是这样。 原文的证明本身是正确的,其技巧是值得称赞的,同时本文也有一些改进。
下面给出证明的全部过程。
第一部分 定义一:鼠标左击、右击或双击均称为操作,分别记为L、R、D。
定义二:扫完一张图采用的步骤,删去其中的废操,其余的操作的序列称为操作序列,记为A=a1, a2,…, an,i=1,2,…,n,n为步骤数。 ai是一个二元组,记录了操作和坐标信息。比如(1,1)起手记为a1={L,(1,1)}。
定义三:雷图中若干cell的集合称为空间,操作ai导致若干cell的状态的改变,称改变状态的cell的集合为基于ai的空间单元,空间单元的cell个数称为空间大小。
定义四:将操作序列A,按照如下步骤分为若干个组: 1.首先将R操作分为不同的组,即每组中最多有一个R。 2.对于每一个D操作,任选一个相邻的R操作,归入该组。 3.对于一个L操作,若所在的cell上还有D操作,那么将这个L分到对应的D那组。 4.其余的L分到各自单独的组中。 则每组称为一个时间单元,时间单元的操作个数称为时间长度。因此时间单元共有三种,分别是只包含一个R,但是有若干个L和D的时间单元,称为第一类时间单元;只包含一个R,但是有若干个D的时间单元,称为第二类时间单元;只包含一个L操作的时间单元,称为第三类时间单元;只包含一个R的时间单元,称为第四类时间单元。
定义五:时间单元与基于该时间单元中每个操作的空间单元的总和,称为时空单元,时空单元的空间大小与时间长度之比称为时空单元的IOE,区别于总IOE,加上下标后记为IOEi。
第二部分 定理一:IOE≤max{IOEi}。 定理一的证明:由定义四,扫雷游戏的整个时空能够被严格划分为四类时空单元,因此总的IOE就是IOEi的加权平均,故得证。
此时,雷图的IOE上限问题化成了时空单元的IOE上限问题。 定理二:第三类时空单元的IOE=1<3.4。 定理二也是显然的。 引理:第三类时空单元对局面造成的影响,是降低或不改变其他时空单元的IOE。 引理的证明:首先要注意第三类时空单元的位置是不能双击的。然后这一类时空单元会减少其他D操作获得的cell,本身也无助于D操作的进行,故得证。
定理三:第四类时空单元的IOE=0<3.4。 这是显然的。 引理:第四类时空单元对局面造成的影响,是降低或不改变其他时空单元的IOE。 引理的证明:第四类时空单元就是一个已经标好的雷,这个单元的存在只会使得与其相邻的其他单元的D操作发生时,少打开一个cell。并且仅基于第四类时空单元的D操作是不允许的,因为这样就会使这个第四类时空单元变成一、二类,从而产生矛盾。综上,第四类时空单元会使得一个相邻的基于这个时空单元的R和另一个时空单元的R的D获得的cell减少1,故得证。
定理四:时空单元的空间单元的大小有限,必然限制在一个5*5区域内。 这是易证得的。
所以问题就化成了求第一、第二类的时空单元的IOE上限问题。 要考虑这个问题,由定理一和定理四,只需要在一个5*5区域内的情况。 另一方面,由定理二和定理三,可以不考虑单独的L、R对初始5*5区域状态造成的影响,只需要考虑第一、第二类的时空单元相互之间的影响。也就是说,直观地讲,初始5*5区域中既不存在由L(而不是LD)造成的支离破碎的边缘,也不存在除中心处的雷以外,任何其他被标出或未被标出的雷;而是只存在被D或Op制造出的边缘。由于Op的本质是对数字0的双击,所以只需要考虑D操作制造出的边缘对初始5*5区域状态造成的影响。
首先分析第一类时空单元的IOE上限。 定理五:第一类时空单元的IOEmax=3.4。 证明:第一类时空单元包含一个有D的L,这样的优势是,它可以在一个完整的5*5局部直接启动。无需详细的分析,我们可以直接用枚举法得到这一类时空单元的最大IOE,其步骤如图所示。 打开了17个3BV,操作为5,所以局部最大IOE为3.4。 随后,假设初始5*5区域不完整,有D操作造成的边缘,那么显然局部最大IOE达不到3.4。 因此定理五得证。
接下来分析第二类时空单元的IOE上限。 定理六:第二类时空单元的IOEmax=3.25。 证明:第二类时空单元利用且必须利用已有“地形”,省去了一个L。而初始5*5区域的“地形”,必须是能够仅用D操作生成的。所以,我们只需要枚举分析各类“地形”下,第二类时空单元能够达到的最大IOE。 可以分为以下三种情况,且它们严格优于其他情况,或者与其他情况对称。 (1)IOEmax=16/5=3.2 (2)IOEmax=13/4=3.25 (3)IOEmax=12/4=3 具体操作步骤省略,读者可以很容易地自行验证。
因此定理六得证。 (注:原证明中“D1与组内所标雷相邻”的情况可以由上述三类情况包括,此处不再赘述,读者自行思考就能明白。)
因此,根据定理一、定理二、定理三、定理五、定理六,得出IOE≤3.4。
最后,让我们来构造一张IOE=3.4的图,如图所示:
同理可以构造任意大小的IOE=3.4的图,只要四周布满雷。
综上,得
定理七:对于面积足够大、且有限的雷图,不论其中包含几个雷,以何种方式排布;且不论何人,以何种方式扫,都有IOE≤3.4;取等号的条件与图中雷的数量有关,而与图的大小无关。
|
|