Windows 游戏中的 NP 完全问题

作者: , 共 495 字

上篇文章扫雷是 NP 完全问题之后,You Xu提到"不光扫雷是 NP 完全问题,空当接龙问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌"。他说对了,不光扫雷, Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷,还有空当接龙和蜘蛛纸牌。

1. 空当接龙是 NP 完全问题

论文: Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.

2. 蜘蛛纸牌是 NP 完全问题

论文: Springer Berlin, Heidelberg, The Complexity of Solitaire, Mathematical Foundations of Computer Science 2007: 182-193, 2007

顺便提一下蜘蛛纸牌的可以获胜的概率高达 82-91.5%。而我平时自己玩的时候 20%都不到。差距啊。

Q. E. D.

类似文章:
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是NP 完全的...
空当接龙可说是最耐玩的 Windows 小游戏之一,尤其在办公一族中长盛不衰。Win98 中的空当接龙有 32000 局,在 XP 里面则增加到了 1000000 关,不过前 32000 关与 Win98 的是一样的。在空当接龙的帮助文件中,作者 Jim Horne 称:「虽然未经证明,但请您相信:所有的牌局最终都能移开。」事实究竟如何,是一个非常有趣的话题。
相似度: 0.107
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本On the graph isomorphism problem
Game Theory 即博弈论,目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年,理论计算机界对它的研究也很热。
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
相似度: 0.052
这个题目听说是 MSRA 的面试题。
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是NP 完全的...
"Good mathematics" could refer (in no particular order) to