1

我遇到了问题，想知道是否可以预测最终结果。

这是图（有向无环图）上的一对一（交替移动）游戏。
从起点或节点开始，玩家 1 选择到节点 v1 的边。从节点 v1，玩家 2 选择一条到节点 v3 的边，依此类推。

如何获胜：到达没有出边的节点的玩家输了。

是否有可能提出一种算法，无论其他玩家做什么，它都能保证获胜？

所以，起始节点是s。玩家 1 可以选择 C ​​或 A。所以基本上，我有没有办法根据某种可以保证我获胜的算法做出决定？

在这种情况下，如果我在节点 D 或 B 并选择通往节点 E 的边，我会赢，因此玩家 2 会卡在节点 E。

*距离无关紧要

4

2 回答 2

5

您需要将图形的节点分为两种类型：获胜节点和失败节点。获胜节点是当前玩家在该节点上具有获胜策略的节点，而失败节点是当前玩家无论他如何玩都会输的节点（假设他的对手正确玩）。由于这是一个有向无环图，所有节点要么赢要么输（因为最终将到达一个没有出边的节点）。

没有出边的节点显然正在丢失节点。对于另一个节点 N：

  • 如果从 N 到失败节点有一条边，则 N 是获胜节点。
  • 否则，N 为失败节点。

要对所有节点进行分类，请以反向拓扑顺序遍历节点。根据上述规则对每个节点进行分类。反向拓扑顺序可确保您在对 N 进行分类之前对所有可以从 N 到达的节点进行了分类。

完成后，如果起始节点是获胜节点，则有一个获胜策略：始终选择失败节点的边缘。

于 2012-11-05T12:39:29.750 回答
0

一般来说，没有。这将取决于您的图表。假设您有一个奇数节点的简单树/链（= n 个节点和 n-1 个边的图）。然后玩家二将永远获胜，因为您无法强制获胜。

您可以查看一些最小-最大算法来指导您的游戏策略。有了这些，您可以通过从最后开始并往回走，确定 DAG 的每个子 DAG 的获胜者，从而递归地确定谁将获胜。

于 2012-11-05T11:59:17.717 回答