俄罗斯方块的数学秘密

Python与开源GIS

俄罗斯方块的数学秘密

2016-11-08 作者: xuzhiping 浏览: 3056 次

摘要: 15年来,有超过百万人把他们宝贵的时间浪费在计算机游戏俄罗斯方块上。玩游戏的人必须把屏幕上方落下的各式砖块安置在下方版面上,而游戏的最终目标是通过砖块的左右移动及旋转,把版面铺满,尽量不要留下空格,直到砖块铺至屏幕最顶端为止。 然而,一群麻省理工学院的计算机科...

15年来,有超过百万人把他们宝贵的时间浪费在计算机游戏俄罗斯方块上。玩游戏的人必须把屏幕上方落下的各式砖块安置在下方版面上,而游戏的最终目标是通过砖块的左右移动及旋转,把版面铺满,尽量不要留下空格,直到砖块铺至屏幕最顶端为止。

然而,一群麻省理工学院的计算机科学家发现,俄罗斯方块远远不只是迷人的计算机游戏。2002年10月,德迈纳、霍恩贝格尔及利本一诺埃尔指出,俄罗斯方块属于一类著名的问题,它的解需要大量计算机运算时间。这类问题中最著名的是“旅行推销员问题”: “有个推销员希望以最短的路径造访几个城市,而且每个城市都只到访一次。” 这个问题可以用计算机来解答,但所需的运算时间,将随着城市数目的增加而呈指数增长。因此,这个问题被归类为所谓NP问题。NP问题与P问题不同,P问题所需的计算机时间递增速度慢得多。如果一个问题解答所需的时间与多项式成正比,即是多项式级的,就称其为P问题(多项式的英文第一个字母是P)。

理论上,NP问题也可以在多项式级时间内解出,但需要一部所谓的非确定性机器,NP——词来自非确定性多项式来协助完成。然而诸如此类的机器现在并不存在(例如量子计算机),也可能永远不会出现。因此,计算机科学家仍在寻找能在多项式级的时间内解出NP问题的算法,(我们只能猜想这种算法是否可能已经存在,只是尚未被发现。或者美国中情局(CIA)、英国军情五处(MI5)、以色列莫萨德情报局早就用它来破解密码,只是不肯泄漏机密?)

不过还是有一些让人欣慰的事,就是研究NP问题时,至少可以在多项式级的时间内验证可能的解答。举例来说,寻找829348951的素因子就属于NP问题,但验证7919为其素因子之一则属于P问题。你必须做的是,把较大的数字除以较小的数字,然后验证它们可以整除,这点在多项式级的时间内可以做到。

1971年,上述问题的解答首次有了理论上的进展,多伦多大学计算机科学家库克证明,所有NP问题在数学上都是互相等价的。这表示只要有一个NP问题可以在多项式级的时间内解出,那么所有NP问题都可以在多项式级的时间内解出。个中隐含的意义是,所有NP问题都属于P问题。计算机科学家以一个简单的式子来表达这种关系: P=NP,而该等式是否成立尚未有解答。许多科学家已经着手处理这个问题,克雷基金会也提供了100万美元奖金给正确解答出这个问题的人。

今日的计算机科学家距解出P=NP问题还有一大段距离,同时他们也得分出一些精力来解决其他问题,如俄罗斯方块。麻省理工学院研究人员发现俄罗斯方块是一个NP问题。他们的证明方法是将俄罗斯方块简化为所谓的三分问题,后者是自1979年来广为人知的NP问题。

在三分问题中,必须将一组数字分为三群,每群数字的总和都相等。德迈纳、霍恩贝格尔及利本诺埃尔的证明由一个非常复杂的俄罗斯方块状态着手,先证明从这个状态开始,填满游戏界面就等于是解出三分问题,由此,俄罗斯方块也就名列NP问题的长串清单之中。此外,微软窗口操作系统中的游戏“踩地雷”也属于NP问题,2000年,英国伯明翰大学的凯曾证明,踩地雷属于NP问题。

然而,这并不能让我们更接近基本问题的解。只有找到一种算法,能在多项式级的时间内在踩地雷游戏中探出地雷、或者填满俄罗斯方块界面,才能得到100万美元的奖金。现在,这个问题依然存在:P=NP?

关注“开源集思”公众号
获取免费资源

随机推荐


Copyright © from 2014. 开源地理空间基金会中文分会 吉ICP备05002032号

Powered by TorCMS

OSGeo 中国中心 邮件列表

问题讨论 : 要订阅或者退订列表,请点击 订阅

发言 : 请写信给: osgeo-china@lists.osgeo.org