澳门金沙网站开户网址

马里奥很难,这在数学上是正式的

作者:羿钫    发布时间:2019-01-26 07:17:06    

雅各布·阿隆(Jacob Aron)如果你曾经努力完成经典的任天堂游戏,那就不要感觉不好 - 他们是正式的难度对电子游戏计算复杂性的分析,包括马里奥和塞尔达传说系列中的计算复杂性,证明其中许多属于一类称为NP-hard的数学问题这意味着对于给定的游戏级别,可能很难确定玩家是否有可能达到目的结果表明,通过玩游戏可以解决一些难题当然,商业版游戏的设计是可行的,但麻省理工学院的Erik Demaine及其同事研究了没有这种约束的版本 “我们在同样的规则下工作,但我们可以自由设计我们喜欢的水平,”他说该团队将每个游戏转换为一种称为布尔可满足性问题的逻辑谜题这会询问是否可以选择逻辑语句集合中的变量以使所有语句成立,或者语句是否不可避免地相互矛盾对于每个游戏,团队构建了一个级别的部分,迫使玩家选择两个路径中的一个 - 相当于在布尔可满足性问题中分配变量敌人和能量提升的安排等同于逻辑陈述如果它们允许完成一个级别,那相当于布尔问题中的所有语句都是真的;如果他们使这个级别不可能,那就相当于一个矛盾马里奥,大金刚,塞尔达传说,银河战士和神奇宝贝系列中的许多游戏都证明是NP难的这意味着决定玩家是否可以完成它们至少与NP中最难的问题一样困难,NP是一个涉及P与NP的诱人问题的复杂性类(参见“百万美元证据”)并非每个系列中的每个游戏都包含在证明中,因为它们遵循不同的规则很多游戏都是NP难的,这意味着很难弄清楚玩家是否可以完成它们对于马里奥来说,该团队还证明了这些游戏是NP完整的,这是一个具有重要影响的附加属性许多难题可以转化为NP完全类别中的任何问题然后,如果你能解决NP完全问题 - 比如说,通过完成马里奥的水平 - 你也解决了原来的问题这包括旅行商问题 - 找到一系列点之间的最短路线 - 这是物流领域真正感兴趣的,以及用于决定如何分配资源的背包问题所以理论上你可以将一个问题的例子转换成马里奥级别,然后玩游戏来解决它 Demaine说,这种方法很有趣,但直接解决可满足性问题可能更简单意大利比萨大学的计算机科学家Giovanni Viglietta说,这些结果为游戏设计师提供了混合新闻,他没有参与这项研究如果确定某个级别是否可以成功导航是一个NP难问题,那么设计师就没有简单的方法来检查这个问题但它确实确保玩游戏很有趣,因为玩家无法轻易确定他们是朝着正确的方向前进,还是潜入了无法通行的区域 “游戏需要一些创造力和独创性,”Viglietta说阅读更多:点击此处阅读本期故事的更长版本计算机科学中最大的问题仍未得到解决,但民意调查显示,研究人员比以往任何时候都更有信心答案应该是什么 P与NP问题的解决方案将解决有关计算的基本问题 - 并赚取100万美元 - 但是何时是另一回事计算机科学家根据他们需要花费多少时间来解决问题 P是一类“简单”问题,可以通过算法相对快速地解决 NP是一类易于检查的问题 - 如果给出答案,您可以在短时间内验证 P类中的所有问题也都在NP中,但是不知道是否所有NP问题都在P中如果是,那么正确的算法可以快速解决所有NP问题如果不是,P≠NP并且许多问题从根本上难以解决来自马萨诸塞州剑桥的克莱数学研究所的证明无论如何价值100万美元 2002年,马里兰大学帕克分校的计算机科学家威廉·加斯塔克(William Gasarch)对100名研究人员进行了调查,其中61%认为P≠NP现在,Gasarch已经与超过150名受访者重新进行了调查,并发现P≠NP支持率高达81%不过,证据可能是很长一段时间只有53%的人表示会在2100年之前出现答案,

 

Copyright © 网站地图