See [0] for a method combining branch and prune with Markovian probabilities. I did a hacky version of my interpretation of this work at [1].

[0] https://link.springer.com/article/10.1007/s10601-010-9101-4

[1] https://github.com/kastnerkyle/pachet_experiments