在保存点有限的多分支游戏中最小化完成所有结局的时间的算法

Question

在多分支游戏中，有𝑛可能的结局。您可以将其视为具有 𝑛 叶节点的有向树，其中每条边的权重为 1。您不必玩整个游戏以达到所有可能的结局，这非常耗时，您可以拥有 𝑘 保存点。什么算法可以最大限度地利用这些𝑘保存点在最短的时间内完成所有结局？

我曾经考虑过使用贪心算法，计算每个点的增益成本比。然而，我发现点建立的顺序是相互影响的。如果先建立上游保存点，则建立下游保存点的成本会降低，但从中获得的额外收益也会变小。这让我怀疑贪心算法的正确性。我想知道是否有更好的算法。

让我举个例子。假设我们有一个如下的树结构：

A————B————C
     |
     B1——-C1————D
          |
          C2————D1

如果我们不使用任何保存点，从A到C的路径需要2步。到达C后，我们需要返回A。从A到D的路径需要4步，从A到D1的路径需要5步。因此，总成本为：

2(A to C)+4(A to D)+5(A to D1)=11

但是，如果我们在 B 处有保存点，则设置保存点的成本为 1 步（因为您需要从 A 移动到 B）。从那里，我们可以从 B 重新出发，访问 C、D 和 D1。总成本降低为：

1(A to B)+1(B to C)+3(B to D)+4(B to D1)=9

如果我们可以在C1处设置另一个保存点，那么设置保存点的成本是2步（因为我们不需要从A一路走到C1；我们已经在B处有了一个保存点，并且路径从 B 到 C1 需要 2 个步骤）。从那里，我们可以从B开始，到C，然后从C1到D和D1。总成本降低为：

1(A to B)+2(B to C1)+1(B to C)+1(C1 to D)+2(C1 to D1)=7

。这是最短时间。

Answer 1

对于每个节点，您可以轻松计算出通过将其设为 O(n) 的保存点可以节省多少：

1. 进行深度优先搜索并在每个节点中存储其深度和可以到达的叶节点数。在示例树中，节点 B 的深度为 1，并且有 3 个叶节点。

2. 使节点n成为保存节点的节省是深度（n）*（leaf_nodes（n）-1）（-1因为你必须第一次到达n）。在示例中，将保存点放置在 B 可以节省 2 次跳转。

这意味着您可以在 O(n) 中找到最佳的单保存点决策 - 一次通过。

如果您还有更多可用的保存点，您可以对先前保存节点的子节点重新运行此决策，并选择保存最多的那个。在这种情况下，仅考虑以 B 为根的子树，您会选择 C1，这会再次保存 2 - 无论是在该特定子树中还是在全局中。

这为您提供了一个优于 O(n * k) 的算法，用于在大小为 n 的树中查找 k 个最佳保存节点——因为您只需要在每棵树中计算一次最佳保存节点（您可以将其存储起来）稍后如果有更好的选择可用），并且如果全局树是平衡的，您期望子树的大小只是其父树大小的一小部分。特别是，如果 k = 树的深度，并且树是二叉树，则全局成本将为 O(n)。