Computation of the Most Probable Explanation (MPE)when probabilistic knowledge is expressed as a factored distribution is a classical AI reasoning problem: complete evidence is available about the values of some of the variables which are observed, and the problem consists in finding the most probable assignment of the remaining variables given the evidence. However, optimising the choice of the variables to observe (the sample) in order to maximise the MPE probability is a less classical and more difficult problem. In this article we tackle this question of optimal sampling in structured problems under limited budget, within the framework of Hidden Markov Random Fields (HMRF). The value of a sample (which we seek to optimise) is the expectation, over all possible sample outputs (observations), of the MPE probability. The contributions of this article are: i) an original probabilistic model for optimal sampling in HMRF ii) computational complexity results about this problem, leading in particular to approximability/inapproximability results and iii) an exact solution algorithm and two approximate solution algorithms of decreasing time complexity, which we empirically evaluate on a problem of spatial sampling for occurrence map restoration.