Matériel pédagogique sur SAT (Boolean Satisfiability problème) [fermé]

Question

Quels sont les bons documents à lire sur SAT (problème Boolean satisfiability) solveurs. Je ne l'ai pas été en mesure de trouver du bon matériel via Google. Les documents que je trouvais étaient les yeux des oiseaux vue aussi des fichiers PDF avancés ou corrompus ...

Quels sont les papiers / documents recommandez-vous pour en apprendre davantage sur les algorithmes dans les solveurs SAT modernes et pratiques?

Answer 1

Le la page Davis-Putnam-Logemann-Loveland sur Wikipédia a une bonne vue d'ensemble.

Ensuite, vous devriez être en mesure de suivre le papier minisat "Un Extensible SAT-solveur" .

Vous devriez également lire "GRASP - Une nouvelle algorithme de recherche pour satisfiabilité " pour comprendre l'algorithme d'apprentissage axée sur les conflits utilisés dans minisat.

Je suis capable d'écrire un solveur en Python assez facilement en utilisant ces ressources. Mon sat.py Code est disponible (LGPL 2.1 actuellement), mais il est tout récent donc peut encore contenir des bogues. Il manque quelques Optimisations de la conception de minisat; si vous voulez utiliser la vitesse brute du code minisat; -)

Mise à jour: Je l'ai aussi fait une version OCaml, sat.ml , ce qui pourrait le rendre plus facile de voir les types.

Answer 2

Un bon livre est: Uwe Schöning; Jacobo Torán - Le problème Satisfiabilité