Precalculate or lazily calculate minimum arborescences for the given objective, for A*

[Zannick]

The minimum arborescence is a minimum spanning tree of a directed graph. There are basic algorithms out there: Chu-Liu/Edmonds and variants which offer improved performance with some modifications and also with some better priority queues (pairing or melding fibonacci heaps that implement efficient reduce_priority). The complexities are given as $O(E\ log V)$ or $O(E + V\ log V)$, though this appears to be based in part on the efficiency of the heap, as others have proven that it's possible to obtain $O(E \sqrt{log log V})$. Some lecture notes from one of the latter has a pretty good pseudocode implementation that we'll have to combine with a good pairing heap.

My claim here is that a minimum arborescence/MDST on n target nodes will underestimate the actual cost of traversal. Intuitively, an MDST will have some nodes that "branch" to two paths, and this represents warping from the end of one branch to that point. It doesn't materially matter in this case whether such a warp is possible, but if we want to factor in warps that go to fixed points (such as savewarps) then we'll need to add $N \times S$ new edges (1 per node per savepoint), and this still wouldn't account for manually set-up warp points (e.g. Farore's Wind, Drone Recall). If it's always possible to warp for free to any point we've already visited, then the MDST is an unordered route to every goal node.

Complexities:

1. We do not need every node in the game. I believe we can just trim the leaf nodes from the MDST, but we definitely can't trim nodes before calculating the MDST.
2. An objective does not correspond directly to a list of locations. Canonicalized locations are easily represented as multiple edges to the same canonical node, but identical items are not. However, if we make locations always be leaf nodes, then we can prune the hardest-to-reach subset of the identical items.

Graph construction:

1. Nodes. Because warps go to specific spots, and because we want branches to represent ideal warps, we will need every spot represented. Then we will want all of our item locations as nodes: 1 per canon id, and otherwise 1 per location.
2. Edges. Every local movement (of the optimum movement), every exit (including hybrids), and every action that moves position will be an edge between spot nodes. Every location generates 1 edge from its spot to its item. (Hybrid locations will have the location edge cost be the item time, and its exit edge cost be the exit time. This will underestimate also if the exit winds up trimmed.) We must omit all locations besides those in the objective (and any that take 0 time), otherwise we cannot be certain whether our MDST includes an unnecessary edge and thus increases our expected time.

How many MDSTs do we need?

• Since the MDST is not based on actually usable edges, we cannot constrain ourselves to just the chosen connections.
• Since we might wind up on spots not in the original MDST, we also need an MDST at other spots to properly calculate estimated remaining time.
• Since the search is stateful, we only care about the locations we still need, and thus we need smaller MDSTs as we continue.

Therefore, we need an MDST for every subset of objective locations, from every spot. This would take $O(S \times 2^L \times E \sqrt{log log (S+L)})$ time, which is ridiculous. Luckily, 1) we can do it lazily, as we don't need the majority of subsets (due to ordering requirements based on game logic), and 2) because locations are all leaf nodes, we can easily trim ones we don't need or have already visited. Hence we only need one full MDST per spot in $O(S \times E \sqrt{log log (S+L)})$ time (again, the last factor dependent on our priority queue), and any others can trim the remainder to show the minimum remaining time (similar to what I said above: the remaining MDST is an unordered route to the remaining goal nodes), in $O(L+S)$ time, with the ability to cache it.

[Zannick]

Ah, these lecture notes provide an implementation that takes $O(m\ log\ n + kn)$ to generate MDSTs for $k$ nodes, which I think for us would translate to $O(E\ log (S+L) + (S+L)^2)$.

[Zannick]

Never mind, I am wrong, it's not possible to shrink an MDST into a smaller minimum tree. Consider the counterexample:

flowchart LR
    A -->|1| B -->|1| C -->|1| D
    D -->|1| E
    B -->|2| E
    D -->|1| F

The MDST is all the $1$ edges, but an MDT with $E$ and as little as possible otherwise is $ABE$.

Finding a minimum tree for a directed graph on a specific subset of nodes with others as necessary is the Directed Steiner Tree problem, which is NP-complete.

[Zannick]

This works pretty great right now, and it's faster to construct the list of remaining locations to do the in-memory cache lookup rather than to read from the db state cache, so I'm going with that.

Unfortunately, the graph has no understanding of the pause menu and gives an estimated remaining time of 0 because it can't reach any of the locations. The menu stuff is implemented in a way specific to AV2 right now, so analyzer can't see the position we'd have after exitmenuwarping without attempting to find the specific warp. We could check all the available warp destinations, or we could require Context provides a menu_exit or real_position value.