Variable Elimination
A Bayesian Network Inference algorithm that avoids
- repeated computation
- irrelevant computation
- Hidden variables in the form of leave nodes can be dropped as they will be equal to via Marginalization.
On Polytrees it can even run in Polynomial Time 1 which is quite a lot faster than the exact Inference. For non-polytrees however it is P-hard which is harder than NP. For these cases one can use various sampling techniques to get approximations that are mostly good enough but way faster.