I am conducting a stateful search of a large graph in an effort to find some solutions of minimal cost. With an admissible heuristic for estimated time to completion from a given state (as in A*), I would be able to drop states out of the search queue to improve runtime, otherwise I need a good heuristic that can advance better states with some variety (or even a better search function altogether). What would be a good heuristic to use, when there are multiple target points to reach, in any order?
Some of my thoughts on generating a heuristic (of estimated time to goal):
Since we want to underestimate in all cases, I can drop most of the stateful details and just express the graph like so:
- A strongly connected directed graph $G$ on $V$ vertices and $E$ edges with positive integer costs, with $L$ leaf nodes not counted in $V$. The problem is to visit a subset $S \subseteq L$ of the leaf nodes in minimum time.
(Also, the search space includes "wormholes" that also have time costs, but I'd rather not represent them as edges, since the search space can traverse a wormhole from anywhere to: a) specific previously visited vertices, or b) a previously visited vertex with a certain action performed. If I generate a minimum directed spanning tree, the total cost of the tree essentially implicitly assumes wormholes can be used at any time to a previously visited vertex for 0 cost... which I'm fine with, as it underestimates by ignoring the costs and limitations.)
- The MDST can be generated using some variety of the Chu-Liu/Edmonds/etc algorithm, and I've found some decent notes on generating one from every vertex. However, I only need to visit a subset $S$ of the leaf nodes (I can easily remove the rest), and I don't care how many other vertices are included, which turns the problem into an NP-hard Directed Steiner Tree problem. It seems overkill to solve for this, but at least there are usable approximations.
- I can generate the all-pairs shortest path table using Floyd-Warshall in $O(V^3)$ or learn one of the faster solutions. Presumably, I could make a graph $G'$ by taking all the shortest paths from the root to $S$, add all the nodes included in those paths, take the shortest paths from those nodes to $S$, etc., and generate an MDST on that, in something like $O(EV + V^2log\ log\ V + V^2 S^2 + E\ log\ V)$, but that might just not be worth the effort.
So the options I'm thinking of at the moment are:
- Use an approximation algorithm for the Steiner Tree. These come with proofs of being within $2 - 2/|S|$ of the cost of the true optimum, so I could just divide the total cost of the generated tree by 2 to guarantee an underestimate.
- Use the full MDST but only count the edges used to reach the remaining nodes of $S$. This potentially overestimates but might be a good heuristic to pick states to search from.
- Do something with the shortest pairs? While I could divide the shortest paths by $|S|$ and sort of guarantee that it underestimates that way, I think it would tend to encourage moving towards clumps of leaves, rather than toward the nearest leaf.
Do any of these sound reasonable, or are there other options I'm overlooking that could be better?
