多分支游戏有限存档点下全结局最短耗时优化算法问询

我们有一款多分支游戏，存在𝑛种可能结局，可将其抽象为包含𝑛个叶节点的有向树，每条边权重为1。现在我们拥有𝑘个存档点，需要找到最优的存档点设置方案，以最短时间完成所有结局。

我曾考虑采用贪心算法，计算每个节点的收益成本比，但发现存档点的设置顺序会相互影响：若先设置上游存档点，下游存档点的设置成本会降低，但额外收益也会减少，这让我质疑贪心算法的正确性，想了解是否存在更优算法。

示例树结构 #

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

不同存档策略的耗时计算 #

• 不使用存档点：A到C路径耗时2步，返回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
• 在B和C1处设置存档点：设置C1的成本为2步（从已有的B存档点到C1），此后从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，这即为最短耗时。

内容的提问来源于stack exchange，提问作者SuohTheBest L