3
Windows 游戏中的 NP 完全问题
source link: https://zhiqiang.org/cs/most-windows-game-are-np-complete.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Windows 游戏中的 NP 完全问题
上篇文章扫雷是 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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK