Windows 游戏中的 NP 完全问题

作者: , 共 495 字 , 共阅读 0

上篇文章扫雷是 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.

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