Les modèles graphiques probabilistes unifient la théorie des probabilités et les modèles graphiques via des variables aléatoires reliées entre elles par une distribution de loi jointe décomposable. L’objectif étudié ici est connu sous le nom de Maximum A Posteriori dans les champs aléatoires de Markov et de Most Probable Explanation dans les réseaux bayésiens, consiste à trouver une affectation globale de toutes les variables ayant une probabilité maximale ou de manière équivalente une énergie minimale. Les méthodes de résolution MAP/MPE sont qualifiées habituellement de complète ou incomplète, selon leur capacité à prouver l’optimalité ou non. Alors que la plupart des méthodes complètes reposent sur la recherche arborescente, les méthodes incomplètes reposent, quant à elles, sur la recherche locale. Dans cet article, nous proposons une approche itérative potentiellement complète au-dessus d’une recherche à voisinages variables qui utilise la recherche arborescente partielle dans son exploration locale des voisinages. La méthode hybride qui en résulte a été evaluée sur un large éventail de benchmarks issus de l’analyse d’images, la reconnaissance de formes, l’allocation de ressources, la bio-informatique, la bio-physique. . . Les résultats montrent que comparée aux méthodes de recherche arborescente existantes, notre méthode offre un meilleur compromis entre le comportement anytime et la preuve d’optimalité. Enfin, l’expérimentation de notre version parallèle sur des instances difficiles issues de la conception de protéines a mis en évidence l’efficacité de la version parallèle pour trouver des bonnes solutions. Le solveur est librement téléchargeable sur https:/ / github.com/ toulbar2/ toulbar2.