Best-First AND/OR Search for Most Probable Explanations
  The paper evaluates the power of best-first search over AND/OR search spaces
for solving the Most Probable Explanation (MPE) task in Bayesian networks. The
main virtue of the AND/OR representation of the search space is its sensitivity
to the structure of the problem, which can translate into significant time
savings. In recent years depth-first AND/OR Branch-and- Bound algorithms were
shown to be very effective when exploring such search spaces, especially when
using caching. Since best-first strategies are known to be superior to
depth-first when memory is utilized, exploring the best-first control strategy
is called for. The main contribution of this paper is in showing that a recent
extension of AND/OR search algorithms from depth-first Branch-and-Bound to
best-first is indeed very effective for computing the MPE in Bayesian networks.
We demonstrate empirically the superiority of the best-first search approach on
various probabilistic networks.
