Windows 游戏中的 NP 完全问题

作者: , 共 518 字

上篇文章 扫雷是 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.104
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本 On the graph isomorphism problem
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是 NP 完全的 ...
"Good mathematics" could refer (in no particular order) to