Windows游戏中的NP完全问题

zhiqiang6月 13, 2008 计算机科学

上篇文章扫雷是NP完全问题之后，You Xu提到＂不光扫雷是NP 完全问题，空当接龙问题也极有可能是一个NP完全问题。目前最好的通用 planner只能解半副牌＂。他说对了，不光扫雷，Windows自带的游戏都是NP完全的。Windows自带的游戏除了扫雷，还有空当接龙和蜘蛛纸牌。

空当接龙是NP完全问题

论文：Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.

蜘蛛纸牌是NP完全问题

论文：Springer Berlin, Heidelberg, The Complexity of Solitaire, Mathematical Foundations of Computer Science 2007: 182-193, 2007

顺便提一下蜘蛛纸牌的可以获胜的概率高达82-91.5%。而我平时自己玩的时候20%都不到。差距啊。

查看更多关于, , , 的内容。

你可能感兴趣的
相关文章

3条留言 -> 跳到留言表格

  • At 2008.06.14 05:02, 哈哈哈 said:

    短短的

    [Reply]
    • At 2008.08.30 13:01, 严酷的魔王 said:

      蜘蛛纸牌很好获胜的吧……觉得没有怎么输
      也许我有50%+的胜率

      [Reply]
      • At 2008.12.28 17:16, CAQ said:

        The Complexity of Solitaire那篇文章说的是普通的Klondike纸牌把，就是所谓的“接龙”。看文章说有人提出胜率超过70%
        蜘蛛纸牌不知道高级（4花色）的胜率是多少……

        [Reply]
        (Required)
        (Required, not published)

          B | I | U | D | 添加链接 | 插入引用 | 插入代码 | 插入表情 | 甲 | + | ?
        « 扫雷是NP完全问题
        杂记-20080616 又到毕业时 »
        guest | 注册 | BBS | 管理 | English | 繁體 | https
        Loading...
        Loading...
        Loading...