扫雷是 NP 完全问题

作者: , 共 427 字

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

结果于 2000 年发表在Mathematical Intelligencer上,论文题目是 Minesweeper is NP-complete ,这里有作者的简单的问题和证明介绍。证明方法是证明扫雷问题可以编码任何逻辑电路,包括 NP-hard 的 3SAT 问题。作者还有一个非常直观的 PPT演示证明过程,比如下图展示如何编码 AND 逻辑门:\( t=u\wedge v\)

扫雷的AND逻辑门

它是 NP 完全问题说明如果程序要想完全正确,所费的时间最坏情况下将是指数的。不过我猜测对于大部分的扫雷的实例还是很容易的,而且 NPC 所用的规约实例特别大,所以编一个能较快速度解决大部分 windows 自带的那个高级难度的扫雷问题还是可行的,不知道是否已经有这方面的程序。

Q. E. D.

类似文章:
上篇文章扫雷是 NP 完全问题之后,You Xu提到"不光扫雷是 NP 完全问题,空当接龙问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌"。他说对了,不光扫雷, Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷,还有空当接龙和蜘蛛纸牌。
相似度: 0.162
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本On the graph isomorphism problem
Game Theory 即博弈论,目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年,理论计算机界对它的研究也很热。
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
Xie Xie 给我看了一个链接性能调优--永远超乎想象,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的。
给定\( n\times n\) 的实数矩阵,每行和每列都是递增的,求这\( n^2\) 个数的中位数。
上篇文章扫雷是 NP 完全问题之后,You Xu提到"不光扫雷是 NP 完全问题,空当接龙问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌"。他说对了,不光扫雷, Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷,还有空当接龙和蜘蛛纸牌。