Restartes aléatoires pour des instances insatisfaisantes

Question

Dans le pire des cas, la satisfabilité booléenne (en supposant p! = Np) prend du temps exponentiel. Néanmoins, les solveurs SAT modernes utilisant des variantes de DPLL sont capables de résoudre suffisamment d'instances pour être utile dans la pratique.

Une technique utilisée, qui a montré de bons résultats dans la pratique, est le redémarrage aléatoire. Intuitivement, redémarrer au hasard signifie qu'il y a une chance de devenir plus chanceux pour deviner les bonnes affectations variables qui conduiraient à une solution rapide.

La même intuition suggère que cela devrait être beaucoup plus efficace lorsque l'instance de problème est en fait satisfaisable (vous n'avez donc qu'à deviner un ensemble d'affectations variables qui constituent une solution) que si ce n'est pas (donc en principe, vous devez vérifier tout le possible Affectations Quoi qu'il en soit, des sections modulo de l'espace de recherche qui peuvent être ignorées via des techniques comme la propagation de l'unité et le retour de retour non chronologique, qui ne sont pas évidemment évidemment sensibles aux suppositions initiales).

La deuxième intuition est-elle correcte? Les redémarrages aléatoires sont-ils en fait beaucoup plus efficaces, en moyenne, dans les cas où l'instance de problème est en fait satisfaisable?