I am developing an algorithm that, in certain moment, must explore an exponential number of objects derived from a graph:
for o in my_graph.getDerivedObjects(): if hasPropertyX(o): process(o) break;
If one of the derived objects has property $X$, then the algorithm process it and then stops. The theory ensures that at least one of these derived objects has property $X$. Now, I strongly suspect that there is a strong correlation between some topological aspects of the graph, and which derived objects actually have property $X$. I want to predict some of the derived objects that have property $X$ using Machine Learning. So, the idea is:
Predict a derived object $o$ that supposedly has property $X$ - or maybe predict $n$ of them for some number $n$.
If any of them is useful, I use them. If not, I run the exponential algorithm.
Of course, this isn't an optimization in the worst-case complexity of the algorithm. Also, I suppose I should also develop some statistical tests in order to show that the prediction algorithm actually works.
Is this type of optimizations common? Could you please provide some examples? The literature on the subject would also be greatly appreciated.