Windows 游戏中的 NP 完全问题

作者: 张志强 , 2008-06-13 , 共 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.

类似文章：

扫雷是 NP 完全问题相似度: 0.233

2008-06-11, 计算机科学 » 算法复杂度, 扫雷

本科时有同学扫雷最快可以在 60 多秒完成高级难度，让我这种最快 130 秒的人非常惭愧，当时就想着编一个全自动的扫雷程序，不过一直也没写。今天才知道，原来扫雷问题是NP 完全的...

空当接龙中最难的关相似度: 0.191

2006-06-02, 资源 » 游戏, 空当接龙工具

空当接龙可说是最耐玩的 Windows 小游戏之一，尤其在办公一族中长盛不衰。Win98 中的空当接龙有 32000 局，在 XP 里面则增加到了 1000000 关，不过前 32000 关与 Win98 的是一样的。在空当接龙的帮助文件中，作者 Jim Horne 称：「虽然未经证明，但请您相信：所有的牌局最终都能移开。」事实究竟如何，是一个非常有趣的话题。

数据库查询是 NP-Hard 问题相似度: 0.129

2009-12-23, 计算机科学 » 数据库, 算法复杂度

问题来自美人他爹和Wangjianshuo's blog

TCS：NP-hard 相似度: 0.108

2007-11-28, 计算机科学 » NP hard, NP vs P, NP complete, 算法复杂度

很多人一看到 NP-hard ，就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话，这个论断是不正确的。从算法角度来看， NP-hard 问题的确比 NP 难，但比 NP 还难（指花费时间更多）的问题却不见得是 NP-hard 的。

加入扫雷网相似度: 0.107

2021-07-01, 碎碎念 » 扫雷

昨天刚加入了扫雷网：http://saolei.wang/Player/Index.asp?Id=24185。

图同构问题属于 P？相似度: 0.092

2008-01-04, 计算机科学 » 图同构, 算法复杂度

更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本On the graph isomorphism problem。

TCS: Game Theory & 纳什均衡的计算相似度: 0.089

2007-12-14, 计算机科学 » 博弈论, 算法复杂度

Game Theory 即博弈论，目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年，理论计算机界对它的研究也很热。

理论计算机初步：P vs NP - 问题概述相似度: 0.070

2006-08-23, 计算机科学 » NP, NP Complete, P vs NP, 理论计算机初步

P = NP?

理论计算机初步：P vs NP - 历史，现状和未来相似度: 0.061

2006-08-24, 计算机科学 » P vs NP, 理论计算机初步

上篇文章已经提到， P vs NP 是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术领域中， NP-完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。