7

考虑一个类似于 Tower Solitaire、Tripeaks 或 Fairway Solitaire 的纸牌游戏：桌子由一些立即可用的牌组成，每张牌都可能覆盖它下面的其他牌（阻止它们被播放）。你有一张“基础”牌，如果这张牌正好在你的基础牌之上或之下一个等级，你可以从桌子上移除一张牌，此时它将成为你的新基础牌。当您无法从桌上打出一张牌时，您可以抽出的替换牌数量有限，因此您通常希望打出尽可能长的牌序列。

首先，您将如何代表董事会帮助寻找解决方案？其次，你会使用什么算法来找到最长的可播放序列？

例子：

  -4a- -5-
-3- -2- -4b-

底部的卡片阻止顶部的卡片被移除：在 3 和 2 都消失之前，您无法移除 4a。假设你的起手牌是一张 A，这里的最佳玩法是 2、3、4b、5、4a。（您可以改为玩 2、3、4a，但这不是那么好。）

我想这应该表示为某种有向图。你会有从 3 和 2 到 4a 以及从 2 和 4b 到 5 的边，但是你是否还会有 3 和 2 之间以及 4a 和 5 之间的边，因为一个接一个可以玩？如果是这样，它们可以按任意顺序播放（3 然后 2，或 2 然后 3）这一事实是否会在图中形成一个循环，从而阻止您使用有效的“最长路径”算法？（我相信如果图中包含循环，则在图中找到最长的路径是 NP 完全的。）

4

2 回答 2

2

如果您将其表示为游戏状态图（动态计算潜在的下一个状态）怎么办 - 这不会有循环，这意味着它是游戏潜在状态的直接 DFS（可能仍然很多）来自起点。

于 2010-01-05T03:44:02.487 回答
1

关键是构建一个尽可能少的节点的有向无环图，其节点将完全捕获问题的状态空间。然后你可以运行你常用的算法。

我建议根据桌上剩余牌的结构形状进行编码。

状态中的第一个数据可能是最左边 - 最上面卡片的唯一 ID。（例如 4a，在某种意义上它是唯一的，即只有一张卡 4a）。形状的其余部分可以用 -1,0,1 中的一个来表示每个可用卡片（准备好被拿走的卡片），描述左边的下一张卡片是在同一“级别”还是一个级别更深或更高。（这是利用一张牌只与其他两张牌重叠的假设，并且结构看起来像您在示例中给出的那个）。

于 2010-01-08T23:18:42.163 回答