5

In a multi-branch game, there are 𝑛 possible endings. You can think of it as a directed tree with 𝑛 leaf nodes, where each edge has a weight of 1. Instead of playing through the entire game to reach all possible endings, which is time-consuming, you have 𝑘 save points. What algorithm can maximize the use of these 𝑘 save points to complete all endings in the shortest possible time?

I once considered using a greedy algorithm, calculating the gain-cost ratio for each point. However, I found that the order in which the points are established affects each other. If an upstream save point is established first, the cost of establishing downstream save points decreases, but the additional gain from them also becomes smaller. This made me doubt the correctness of the greedy algorithm. And I want to know if there is a better algorithm.

Let me provide an example. Assume we have a tree structure as follows:

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

If we don't use any save points, the path from A to C costs 2 steps. After reaching C, we would need to return to A. The path from A to D costs 4 steps, and the path from A to D1 costs 5 steps. Therefore, the total cost is:2(A to C)+4(A to D)+5(A to D1)=11

However, if we have a save point at B, the cost to set the save point is 1 step (since you need to move from A to B). From there, we can start again at B and visit C, D, and D1. The total cost is reduced to:1(A to B)+1(B to C)+3(B to D)+4(B to D1)=9

If we can set another save point at C1, the cost of setting the save point is 2 steps (because we don't need to go all the way from A to C1; we already have a save point at B, and the path from B to C1 is 2 steps). From there, we can start at B, go to C, then from C1 to D and D1. The total cost is reduced to:1(A to B)+2(B to C1)+1(B to C)+1(C1 to D)+2(C1 to D1)=7. And this is the minimum time .

Improve this question
9
  • "the shortest possible time" Time? Do you mean you want to minimize the number non-leaf nodes visited in order to reach any leaf node? i.e. the minimum depth of the tree. Commented Nov 18, 2024 at 17:01
  • If my guess of what you are trying to minimize is correct, then a topological sort is probably what your are looking for. Commented Nov 18, 2024 at 17:04
  • 1
    What do you mean by the cost of a savepoint? It sounds like something important has been left out. Commented Nov 18, 2024 at 17:38
  • The answer to your question really depends on how much you know about the tree ahead of time. If you know the entire tree, then you can find the optimal solution. If you have to choose your save points while you explore and you don't know anything at all about the tree except what you discover as you move through it, then you have a much different problem. How much do you know about the tree? Commented Nov 19, 2024 at 4:55
  • 1
    In the example the optimal choice for one save point seems to be C1 not B (giving a cost of 8) instead of 9. (The second save point will then instead be at B giving the same result with two save points.) Is that a correct understanding? Commented Nov 20, 2024 at 8:04

2 Answers 2

Reset to default
0

For each node, you can easily calculate how much you can save by making it a savepoint in O(n):

  1. do a depth-first search and store, in each node, its depth and the number of leaf-nodes it can reach. In the example tree, node B would have depth 1, and it has 3 leaf-nodes.

  2. the savings for making node n a save-node is depth(n)*(leaf_nodes(n)-1) (-1 because you have to reach n a first time). In the example, placing the save-point at B saves you 2 jumps.

This means that you can find the optimal single-savepoint decision in O(n) - a single pass.

At this point, I hoped that we could repeat this algorithm for each of the children, leading to a straightforward greedy approach. However, Xellos proved that this does not work with a counter-example:

            10
           /
      4-5-6-11
     /     
1-2-3       12
     \     /
      7-8-9-13

If there is only 1 save-point, then it should be node 3, as per the above algorithm (saves 2*3=6). But if there are 2, they should be nodes 6 and 9, which save 5 each. Therefore, I would use a backtracking approach, and the cost is harder to calculate.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I see whaf you're trying, but I don't quite see how to implement it in O(n). Can you offer an implementation demonstrating that theee isn't something like a log(k) factor in there as well?
The k=1 case is correct but if you want to find multiple save points by greedily picking the best, that doesn't work. Consider a 13-node tree with 4 leaves constructed from paths 1-2-3, 3-4-5-6, 3-7-8-9, 6-10, 6-11, 9-12, 9-13. The optimal solution for k=1 is node 3 (saves 2*3), but for k=2 we should pick nodes 6 and 9 (saves 5+5, picking node 3 and another saves at most 2*3+3*1).
@btilly given N nodes, and assuming for a binary tree, N + N/2 + ... = 2N, which is in O(N). You only have to re-evaluate the children of savepoints, which should be fractions of the size of their containing trees. A more conservative estimate is O(NK).
@Xellos great counter-example. Added it, and now propose backtracking instead.
0

There's a O(N^3) dynamic programming solution. I doubt we can do much better since tree problems where cost is determined not by pure ancestry info, but by branching info, tend to have quadratic time complexity at best.

First off, let's treat the root and leaves as existing save points. We're just adding up to K more. The cost of a non-root save point is its distance to its nearest save point ancestor.

The DP states are: if we're considering a subtree of v (inclusive) and the nearest save point on the path from root to v (inclusive) is at depth d, what's the minimum summed cost of save points in the subtree that can be achieved by adding k of them to the subtree? Note that the savepointness of v is determined by d; we're only considering how to add save points to other vertices in the subtree.

To calculate the states for any v, first calculate all states for direct children of v. Then for each d, add child subtrees one by one and recalculate the minimum costs for all choices of total number of save points k1 added to previous child subtrees and number of save points k2 added to currently added child subtree. When adding any subtree of a child u, we consider 3 options:

  • u is a leaf, k2 = 0 and cost is dep(u) - d
  • u is a non-leaf save point, so it adds cost[u][0][k2] + dep(u) - d
  • u isn't a save point, so it adds cost[u][d][k2]

Pseudocode for each v, d:

tmp = [inf for k in 0...subtree_size(v)]
tmp[1 if d = 0 and v not leaf, else 0] = dep(u) - d if d = 0, else 0
for u in children(v):
    tmp_next = [inf for k in 0...subtree_size(v)]
    for k1 in 0...subtree_size(v):
        for k2 in 0...subtree_size(u):
            tmp_next[k1 + k2] = min(tmp_next[k1 + k2], tmp[k1] + dp[u][0][k2] + dep(u) - d)
            tmp_next[k1 + k2] = min(tmp_next[k1 + k2], tmp[k1] + dp[u][d][k2])
    tmp = tmp_next
dp[v][d] = tmp

The answer is dp[root][0][min(K, number of non-leaf non-root vertices)].

Why is this not O(N^4)? For each d and each child subtree of v, we loop over the size of that subtree x size of all previous child subtrees of v. This is as much as looping over all pairs of vertices which have v as their LCA. Since LCA is unique, there are only O(N^2) pairs of vertices and for each pair and all possible d, we perform O(1) operations, which gives O(N^3) amortized time, even though we're calculating a DP table with size O(N^3) using nested loops.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.