DRMacIver's Notebook

Using unsound A* search to improve a greedy algorithm

Published

2019-01-03

I figured out something quite neat today, which is that you can use improper \(A^*\) search to find a good set of test-case reduction pass orderings.

The basic idea is that you have some set of interesting test cases \(X\) a number of reduction passes \(f_i: X \to (\mathbb{N}^+, X)\) with \(f(x)_1 \leq x\). The pass returns a shrink (possibly the same value) and a cost (i.e. number of test evaluations) of getting there. We’re looking for a minimum cost sequence of applications of the \(f_i\) until we get to a fixed point.

This can be viewed as a graph search problem. Each \(f_i\) defines an edge of weight \(f_i(x)_0\) from \(x\) to \(f_i(x)_1\). You can run Dijsktra’s algorithm to find an exact shortest path to a fixed point, but this takes basically forever.

\(A^*\) is an algorithm that speeds up Dijsktra by using a lower bound on the possible path length to preferentially select good directions. There’s no way to run a proper version of \(A^*\) because the problem is not well enough posed to get a good lower bound on the cost of reduction, but you can run an improper one by setting that lower bound heuristic to whatever you like. Depending on how close it is to being a true lower bound you may still get a good path which may or may not be optimal (in my experiments it seems to be within about 10-20% of optimal, which is pretty good).

The trick for test-case reduciton is that greedy search works pretty well but not brilliantly. You can set the lower bound heuristic to be the cost of running a greedy search (I’m using one which always selects the lowest cost edge that makes progress). This then ensures that your lower bound always corresponds to the cost of some path, even if it’s not the optimal one. In particular if you wanted it to be this could become an any time algorithm.

I suspect this trick generalises but I haven’t quite figured out its essential characteristics yet.