Optimisations du solveur SAT de DPLL pour des formules insatisfaisantes [Duplicate

Question

Cette question a déjà une réponse ici:

• Meilleures améliorations à faire à l'algorithme DPLL SAT 2 réponses

J'implémente un solveur SAT basé sur l'algorithme DPLL, et il fonctionne bien sur de petites formules et des problèmes satisfaisables plus importants. Ma division de cas est basée sur une structure de type arbre, où chaque branche est essayée un par une jusqu'à ce que la solution pour le problème soit trouvée ou jusqu'à ce que chaque branche soit essayée.

Donc, mon problème est maintenant que l'approche décrite ci-dessus ne se termine pas lorsque vous essayez de trouver une solution sur de gros problèmes non-sateaux (il ne devrait donc pas y avoir de solution), donc mon programme essaie toutes les possibilités de 2 $ ^ n $, lui donnant un Heure des années pour résoudre le problème non-satel avec des variables de 50 $ + (elle finirait par se terminer en des années car je n'ai aucun problème de mémoire, etc.).

Ma question est: quels sujets / implémentations voudrais-je envisager d'accélérer le traitement des arbres ou ce processus de partage de cas sur des problèmes insatisfaisants. Merci.