用于解决具有重叠卡的游戏的结构/算法

Question

考虑一下沿着Tower Solitaire,Tripeaks或Fairway Solitaire线路的纸牌游戏:桌子上有一些可立即使用的牌,每张牌都可以覆盖下面的其他牌(阻止他们玩牌).你有一张"基础"牌,你可以从桌子上取出一张牌,如果它只是你的基础牌之上或之下的一个等级,那么它就成了你的新基础牌.当您无法从牌桌上打牌时,您可以使用有限数量的替换牌进行抽牌,因此您通常希望尽可能打出最长的牌.

首先,您如何代表董事会以便寻找解决方案？其次,你会用什么算法来找到最长的可玩序列？

例:

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

底部卡片卡在顶部被移除:你不能删除4a,直到3和2都消失.假设您的起始牌是王牌,这里的最佳游戏将是2,3,4b,5,4a.(你可以玩2,3,4a,但那不太好.)

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

Answer 1

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