浙江龙网

  1. 首页 > 生活百科 > >

玩扫雷还有什么技巧？ 扫雷怎么玩( 二 )

玩游戏想不到科学家问题


图中黄色部分是典型的扫雷问题，需要猜测 。根据角落里的数字，我们只能知道12的黄色部分肯定只有一个雷，但不知道哪个是雷 。如果没有其他信息，我们努力了大半个棋盘，最终通过这个雷区的概率还是只有1/8 。
这个简单的判断还行，有时候会有一些比较隐晦的猜测 。
扫雷判断问题
假设我们在扫雷过程中遇到这样的模式，真的是欲哭无泪的事情 。如果你不知道怎么哭，你可以先准备好眼泪，边肖会马上告诉你为什么要哭 。。。从左边开始，假设第一个空位有雷，那么第二个空位没有雷，因为空位中间的1存在，第三个空位有雷，以此类推 。但是如果第一个空位没有打雷，第二个空位有打雷，也是有道理的 。我要踩一个地雷，还有这么复杂的问题，至于吗 。。。
别担心，后面还有更复杂的事情 。这里的X和下面的*上是否有雷的情况总是一样的，所以这个雷区就像一根传输信号的电线 。在扫雷地图上，我们不仅可以制作这种简单的信号传输线，还可以实现所有电子电路中逻辑门的操作 。[4,5]
非门电路
或门电路
这是两个“简单”的逻辑门，分别实现翻转信号的“非”门和“或”运算两个信号的“或”门 。在另一款知名沙盒游戏《《我的世界》》中，玩家也可以利用游戏中的素材——红石(其实在此之前每年Windows 10操作系统的更新代码都是以红石命名的)来实现各种复杂的逻辑运算，还有一些玩家已经利用红石在《我的世界》打造了一台真正可操作的电脑 。。。
带有完整寄存器、加法器和其他组件的红石计算机[6]
算了，我无法想象扫雷会变成什么样 。。。
很难判断是否有解决办法 。
找答案
回到文章的开头，如果我们解决了一个扫雷问题，我们将很容易死去 。如果我们把这个问题交给计算机呢？遗憾的是，在正常情况下，计算机仍然无力解决扫雷问题 。。。
困难的
好在在我们平时玩的比较小的棋盘下，电脑也可以通过搜索得到答案 。
为了理解计算机在处理问题时的几个困难程度，有必要先了解一个概念——多项式时间 。对于相同的算法，根据问题的大小，计算机一般需要不同的时间来计算 。用最直观的例子，小明要去洗衣服 。他洗一件衣服需要2分钟，洗五件衣服需要10分钟，洗十件衣服需要20分钟 。处理问题的时间随着问题的规模线性变化，并且是线性多项式 。现在假设小明还得洗衣服，但是现在的衣服挺特别的 。他洗一件这种衣服需要2分钟，但是洗五件的时间变成了32分钟，洗十件的时间变成了1024分钟 。这个时间是指数的而不是多项式的 。评价一个算法是一个非常重要的指标 。随着问题规模的增大，如何增加计算时间 。
在计算机中，我们仍然认为多项式时间非常快 。如果把问题按照解决难度分类，P指的是多项式时间可以解决的问题，俗话说是可以快速解决的问题 。NP指的是一个计算起来不一定很快的问题，但是我们可以很快地检查任何答案 。完全NP问题是一个比所有NP问题都难的NP问题 。虽然人们有一个奇妙的想法，他们总是认为计算会很快，他们应该能找到一种方法让他快速计算，但这仍然是未知的 。。。[7]
不幸的是，解决扫雷游戏的解决方案恰好是一个NP完全问题——这是可以轻松验证结果是否正确的问题中最困难的一个 。到目前为止，人们还没有找到解决这类问题的多项式时间算法，通常只有指数甚至阶乘搜索算法才能解决 。
显示液晶数字的逻辑电路 。我们可以很容易地逐个尝试，但反过来就很难了，尤其是逻辑电路很大的时候 。
扫雷游戏就是这样一个难题，因为正如上一章提到的，扫雷游戏可以看作是一个用逻辑门进行运算的逻辑电路 。给定一个逻辑电路，当输出结果已知时，能否确定每个输入的值？这个问题叫做SAT问题，是世界上第一个被证明是NP完全的问题 。[8]这类问题很容易验证 。你只需要把结果代入逻辑电路，就可以马上知道是否符合要求 。但是反过来计算满足结果的输入是极其麻烦的 。
使用那些构造好的逻辑门来解决扫雷游戏的结果，就相当于解决了SAT问题 。[9]
扫雷也与渗透有关 。
预编码
液体，图片来自迈克尔·希灵堡的吉菲
事实上，我们发现玩扫雷游戏很难 。其实还有一个原因 。这个原因和物理学中的渗透有关 。
20世纪60年代，科学家[10]发现，当流体流经多孔介质时，空介质中的孔洞总是会被堵塞，有时会影响流体的流出 。奇怪的是，当这些多孔介质中随机堵塞的孔隙比例逐渐增加到一定值时，开始时一直能够流动的流体突然被完全堵塞 。当孔洞被随机堵塞的概率发生变化时，液体的流速也会发生突变 。

推荐阅读


上一篇：梦溪笔谈是谁写的？ 梦溪笔谈的作者

下一篇：【养生知识】过量食用荔枝会怎么样 荔枝一天吃多少合适!