Hispanopedia Wiki
Articulo de referencia

Algoritmo DPLL

O(2^n) "},"best-time":{"wt":" O(1) (constant)"},"space":{"wt":" O(n) (basic algorithm)"}},"i":0}}]}"> En lógica e informática , el algoritmo de Davis-Putnam-Logemann-Loveland ( ...

Hispanopedia WikiContenido en espanolLectura gratuita

En lógica e informática , el algoritmo de Davis-Putnam-Logemann-Loveland ( DPLL ) es un algoritmo de búsqueda completo basado en retroceso para decidir la satisfacibilidad de fórmulas de lógica proposicional en forma normal conjuntiva , es decir, para resolver el problema CNF-SAT .

Fue introducido en 1961 por Martin Davis , George Logemann y Donald W. Loveland , y constituye un perfeccionamiento del algoritmo Davis-Putnam , un procedimiento basado en la resolución desarrollado por Davis y Hilary Putnam en 1960. Especialmente en publicaciones antiguas, el algoritmo Davis-Logemann-Loveland suele denominarse "método Davis-Putnam" o "algoritmo DP". Otros nombres comunes que mantienen esta distinción son DLL y DPLL.

Implementaciones y aplicaciones

El problema SAT es importante tanto desde el punto de vista teórico como práctico. En la teoría de la complejidad, fue el primer problema que se demostró que era NP-completo , y puede aparecer en una amplia variedad de aplicaciones, como la verificación de modelos , la planificación y programación automatizadas y el diagnóstico en inteligencia artificial .

Por ello, la creación de solucionadores SAT eficientes ha sido un tema de investigación durante muchos años. GRASP (1996-1999) fue una implementación temprana que utilizaba DPLL. [ 1 ] En las competiciones internacionales SAT, las implementaciones basadas en DPLL, como zChaff [ 2 ] y MiniSat [ 3 ], obtuvieron los primeros puestos en las competiciones de 2004 y 2005. [ 4 ]

Otra aplicación que a menudo involucra DPLL es la demostración automatizada de teoremas o satisfacibilidad módulo teorías (SMT), que es un problema SAT en el que las variables proposicionales se reemplazan con fórmulas de otra teoría matemática .

El algoritmo

El algoritmo básico de retroceso consiste en elegir un literal, asignarle un valor de verdad , simplificar la fórmula y comprobar recursivamente si la fórmula simplificada es satisfacible; si lo es, la fórmula original también lo es; de lo contrario, se realiza la misma comprobación recursiva asumiendo el valor de verdad opuesto. Esto se conoce como regla de división , ya que divide el problema en dos subproblemas más sencillos. El paso de simplificación elimina de la fórmula todas las cláusulas que se vuelven verdaderas bajo la asignación y todos los literales que se vuelven falsos de las cláusulas restantes.

El algoritmo DPLL mejora el algoritmo de retroceso mediante el uso intensivo de las siguientes reglas en cada paso:

Propagación de unidades
Si una cláusula es una cláusula unitaria , es decir, contiene un único literal sin asignar, esta cláusula solo puede satisfacerse asignándole el valor necesario para que dicho literal sea verdadero. Por lo tanto, no es necesario realizar ninguna elección. La propagación de unidades consiste en eliminar cada cláusula que contenga el literal de una cláusula unitaria y descartar el complemento de dicho literal de cada cláusula que lo contenga. En la práctica, esto suele generar cascadas deterministas de unidades, evitando así gran parte del espacio de búsqueda ingenuo.
eliminación literal pura
Si una variable proposicional aparece con una sola polaridad en la fórmula, se denomina pura . Un literal puro siempre puede asignarse de forma que todas las cláusulas que lo contienen sean verdaderas. Por lo tanto, cuando se asigna de esta forma, estas cláusulas ya no restringen la búsqueda y pueden eliminarse.

La insatisfacibilidad de una asignación parcial se detecta si una cláusula queda vacía, es decir, si todas sus variables se han asignado de forma que los literales correspondientes resulten falsos. La satisfacibilidad de la fórmula se detecta cuando todas las variables se asignan sin generar la cláusula vacía o, en implementaciones modernas, si todas las cláusulas se satisfacen. La insatisfacibilidad de la fórmula completa solo puede detectarse tras una búsqueda exhaustiva.

El algoritmo DPLL se puede resumir en el siguiente pseudocódigo, donde Φ es la fórmula CNF :

Algoritmo DPLL Entrada: Un conjunto de cláusulas Φ. Salida: Un valor de verdad que indica si Φ es satisfacible.
función DPLL (Φ) // propagación de unidades: Mientras haya una cláusula de unidad { l } en Φ, haga Φ ← unit-propagate ( l , Φ); // eliminación literal pura: mientras haya un literal l que aparezca puro en Φ hacer Φ ← pure-literal-assign ( l , Φ); // condiciones de parada: Si Φ está vacío, entonces devuelve verdadero; si Φ contiene una cláusula vacía, entonces devuelve falso; // Procedimiento DPLL: l ← elegir-literal (Φ); devolver DPLL (Φ ∧ {l}) o DPLL (Φ ∧ {¬l});
  • " ← " denota asignación . Por ejemplo, " largest ← item " significa que el valor de largest cambia al valor de item .
  • " return " finaliza el algoritmo y devuelve el siguiente valor.

En este pseudocódigo, unit-propagate(l, Φ)y pure-literal-assign(l, Φ)son funciones que devuelven el resultado de aplicar la propagación unitaria y la regla literal pura, respectivamente, al literal ly a la fórmula Φ. En otras palabras, reemplazan cada aparición de lcon "verdadero" y cada aparición de not lcon "falso" en la fórmula Φ, y simplifican la fórmula resultante. El oren la returninstrucción es un operador de cortocircuito . denota el resultado simplificado de sustituir "verdadero" por en .Φ ∧ {l}lΦ

El algoritmo finaliza en uno de dos casos. O bien la fórmula CNF Φestá vacía, es decir, no contiene ninguna cláusula. En ese caso, se satisface con cualquier asignación, ya que todas sus cláusulas son trivialmente verdaderas. En caso contrario, cuando la fórmula contiene una cláusula vacía, esta es trivialmente falsa porque una disyunción requiere al menos un miembro verdadero para que el conjunto global sea verdadero. En este caso, la existencia de dicha cláusula implica que la fórmula (evaluada como una conjunción de todas las cláusulas) no puede evaluarse como verdadera y, por lo tanto, debe ser insatisfacible.

La función DPLL en pseudocódigo solo devuelve si la asignación final satisface la fórmula o no. En una implementación real, la asignación parcial que satisface la fórmula también se suele devolver en caso de éxito; esto se puede obtener registrando los literales de ramificación y las asignaciones de literales realizadas durante la propagación de unidades y la eliminación de literales puros.

El algoritmo de Davis-Logemann-Loveland depende de la elección del literal de ramificación , que es el literal considerado en el paso de retroceso. Por lo tanto, no se trata exactamente de un algoritmo, sino más bien de una familia de algoritmos, uno para cada posible forma de elegir el literal de ramificación. La eficiencia se ve fuertemente afectada por la elección del literal de ramificación: existen casos en los que el tiempo de ejecución es constante o exponencial dependiendo de la elección de los literales de ramificación. Estas funciones de elección también se denominan funciones heurísticas o heurísticas de ramificación. [ 5 ]

Formalización

La notación similar al cálculo de secuencias se puede utilizar para formalizar muchos algoritmos de reescritura, incluido DPLL. Las siguientes son las 5 reglas que un solucionador de DPLL puede aplicar para encontrar o no encontrar una asignación satisfactoria, es decirA=(l1,¬l2,l3,...){\displaystyle A=(l_{1},\neg l_{2},l_{3},...)}. [ 6 ] [ 7 ]

Si una cláusula en la fórmulaΦ{\displaystyle \Phi }tiene exactamente un literal sin asignarl{\displaystyle l}enA{\displaystyle A}, con todos los demás literales en la cláusula que aparecen negativamente, extenderA{\displaystyle A}conl{\displaystyle l}Esta regla representa la idea de que una cláusula actualmente falsa con solo una variable sin definir obliga a que esa variable se defina de tal manera que toda la cláusula sea verdadera; de lo contrario, la fórmula no se cumplirá .{l1,…,lnorte,l}∈Φ¬l1,…,¬lnorte∈Al,¬l∉AA:=Al (Propagar){\displaystyle {\frac {\begin{array}{c}\{l_{1},\dots ,l_{n},l\}\in \Phi \;\;\;\neg l_{1},\dots ,\neg l_{n}\in A\;\;\;\;\;l,\neg l\notin A\end{array}}{A:=A\;l}}{\text{ (Propagar)}}}Si un literall{\displaystyle l}aparece en la fórmulaΦ{\displaystyle \Phi }pero su negación¬l{\displaystyle \neg l}no lo hace, yl{\displaystyle l}y¬l{\displaystyle \neg l}no están enA{\displaystyle A}, extenderA{\displaystyle A}conl{\displaystyle l}Esta regla representa la idea de que si una variable aparece solo de forma puramente positiva o puramente negativa en una fórmula, todas las instancias se pueden establecer como verdaderas o falsas para que sus cláusulas correspondientes sean verdaderas .l literal de Φ¬l no literal de Φl,¬l∉AA:=Al (Puro){\displaystyle {\frac {\begin{array}{c}l{\text{ literal of }}\Phi \;\;\;\neg l{\text{ not literal of }}\Phi \;\;\;\;\;l,\neg l\notin A\end{array}}{A:=A\;l}}{\text{ (Pure)}}}Si un literall{\displaystyle l}está en el conjunto de literales deΦ{\displaystyle \Phi }y ningunol{\displaystyle l}ni¬l{\displaystyle \neg l}está enA{\displaystyle A}, luego decide sobre el valor de verdad del{\displaystyle l}y extenderA{\displaystyle A}con la decisión literal∙l{\displaystyle \bullet l}Esta regla representa la idea de que, si no estás obligado a realizar una tarea, debes elegir una variable para asignar y anotar cuál fue la asignación elegida, para que puedas volver atrás si la elección no dio como resultado una asignación satisfactoria .l∈Literatura(Φ)l,¬l∉AA:=A∙l (Decidir){\displaystyle {\frac {\begin{array}{c}l\in {\text{Lits}}(\Phi )\;\;\;l,\neg l\notin A\end{array}}{A:=A\;\bullet \;l}}{\text{ (Decide)}}}Si una cláusula{l1,…,lnorte}{\displaystyle \{l_{1},\dots ,l_{n}\}}está enΦ{\displaystyle \Phi }y sus negaciones¬l1,…,¬lnorte{\displaystyle \neg l_{1},\dots ,\neg l_{n}}están enA{\displaystyle A}, yA{\displaystyle A}puede representarse comoA=A′∙lnorte{\displaystyle A=A'\;\bullet \;l\;N}dónde∙∉norte{\displaystyle \bullet \notin N}, luego retroceda configurandoA{\displaystyle A}aA′¬l{\displaystyle A'\;\neg l}Esta regla representa la idea de que si llegas a una contradicción al tratar de encontrar una asignación válida, debes volver al punto donde tomaste una decisión previamente entre dos asignaciones y elegir la otra.{l1,…,lnorte}∈Φ¬l1,…,¬lnorte∈AA=A′∙lnorte∙∉norteA:=A′¬l (Volver hacia atrás){\displaystyle {\frac {\begin{array}{c}\{l_{1},\dots ,l_{n}\}\in \Phi \;\;\;\neg l_{1},\dots ,\neg l_{n}\in A\;\;\;\;\;A=A'\;\bullet \;l\;N\;\;\;\;\;\bullet \notin N\end{array}}{A:=A'\;\neg l}}{\text{ (Backtrack)}}}Si una cláusula{l1,…,lnorte}{\displaystyle \{l_{1},\dots ,l_{n}\}}está enΦ{\displaystyle \Phi }y sus negaciones¬l1,…,¬lnorte{\displaystyle \neg l_{1},\dots ,\neg l_{n}}están enA{\displaystyle A}y no hay ningún marcador de conflicto∙{\displaystyle \bullet }enA{\displaystyle A}En ese caso, el algoritmo DPLL falla. Esta regla representa la idea de que si se llega a una contradicción pero no había nada que se pudiera haber hecho de manera diferente en el camino, la fórmula es insatisfacible.{l1,…,lnorte}∈Φ¬l1,…,¬lnorte∈A∙∉AFallar (Fallar){\displaystyle {\frac {\begin{array}{c}\{l_{1},\dots ,l_{n}\}\in \Phi \;\;\;\neg l_{1},\dots ,\neg l_{n}\in A\;\;\;\;\;\bullet \notin A\end{array}}{\text{Fail}}}{\text{ (Fail)}}}

Visualización

Davis, Logemann y Loveland (1961) desarrollaron este algoritmo. Algunas propiedades de este algoritmo original son:

  • Se basa en la búsqueda.
  • Es la base de casi todos los solucionadores SAT modernos.
  • No utiliza aprendizaje ni retroceso no cronológico (introducido en 1996).

Un ejemplo con visualización de un algoritmo DPLL con retroceso cronológico:

Desde 1986, los diagramas de decisión binarios (ordenados reducidos) también se han utilizado para la resolución de problemas SAT.

En 1989-1990, se presentó y patentó el método de Stålmarck para la verificación de fórmulas. Ha encontrado cierta utilidad en aplicaciones industriales. [ 8 ]

DPLL se ha extendido para la demostración automatizada de teoremas para fragmentos de lógica de primer orden mediante el algoritmo DPLL(T) . [ 1 ]

En la década de 2010-2019, el trabajo para mejorar el algoritmo ha encontrado mejores políticas para elegir los literales de ramificación y nuevas estructuras de datos para hacer que el algoritmo sea más rápido, especialmente la parte de propagación de unidades . Sin embargo, la mejora principal ha sido un algoritmo más potente, el Aprendizaje de Cláusulas Impulsado por Conflictos (CDCL), que es similar a DPLL pero que después de llegar a un conflicto "aprende" las causas raíz (asignaciones a variables) del conflicto y usa esta información para realizar retroceso no cronológico (también conocido como salto hacia atrás ) para evitar llegar al mismo conflicto nuevamente. La mayoría de los solucionadores SAT de última generación se basan en el marco CDCL a partir de 2019. [ 9 ]

Relación con otras nociones

Las ejecuciones de algoritmos basados ​​en DPLL en instancias insatisfacibles corresponden a pruebas de refutación de resolución de árboles . [ 10 ]

Véase también

Referencias

General

  • Davis, Martin ; Putnam, Hilary (1960). "Un procedimiento computacional para la teoría de la cuantificación" . Journal of the ACM . 7 (3): 201– 215. doi : 10.1145/321033.321034 . S2CID 31888376 . 
  • Davis, Martin; Logemann, George; Loveland, Donald (1962). "Un programa informático para la demostración de teoremas" . Communications of the ACM . 5 (7): 394– 397. doi : 10.1145/368273.368557 . hdl : 2027/mdp.39015095248095 . S2CID 15866917 . 
  • Ouyang, Ming (1998). "¿Qué tan buenas son las reglas de ramificación en DPLL?". Matemáticas Aplicadas Discretas . 89 ( 1– 3): 281– 286. doi : 10.1016/S0166-218X(98)00045-6 .
  • John Harrison (2009). Manual de lógica práctica y razonamiento automatizado . Cambridge University Press. págs. 79–90 . ISBN  978-0-521-89957-4.

Específico

  1. 1 2 Nieuwenhuis, Robert; Oliveras, Albert; Tinelli, Cesar (2004), "DPLL abstracto y DPLL abstracto módulo teorías" (PDF) , Actas de la Conferencia Internacional sobre Lógica para la Programación, la Inteligencia Artificial y el Razonamiento , LPAR 2004 , págs. 36–50 
  2. ↑ Sitio web de zChaff
  3. ↑ "Sitio web del Ministerio de Satélite" .
  4. ↑ La página web de las competiciones internacionales SAT , sat! live
  5. ^ Marques-Silva, João P. (1999). "El impacto de la heurística de ramificación en algoritmos de satisfacción proposicional". En Barahona, Pedro; Alferes, José J. (eds.). Progreso en inteligencia artificial: novena conferencia portuguesa sobre inteligencia artificial, EPIA '99 Évora, Portugal, 21 al 24 de septiembre de 1999 Actas . LNCS . vol. 1695. págs. 62– 63. doi : 10.1007/3-540-48159-1_5 . ISBN   978-3-540-66548-9.
  6. ↑ Nieuwenhuis, Robert; Oliveras, Albert; Tinelli, Cesare (2006-11-01). "Resolución de SAT y SAT Modulo Theories: De un procedimiento abstracto de Davis-Putnam-Logemann-Loveland a DPLL(T)" . J. ACM . 53 (6): 937–977 . doi : 10.1145/1217856.1217859 . ISSN 0004-5411 . 
  7. ↑ Krstić, Sava; Goel, Amit (2007). Konev, Boris; Wolter, Frank (eds.). "Architecting Solvers for SAT Modulo Theories: Nelson-Oppen with DPLL" . Frontiers of Combining Systems . Berlín, Heidelberg: Springer: 1–27 . doi : 10.1007/978-3-540-74621-8_1 . ISBN 978-3-540-74621-8.
  8. ↑ Stålmarck, G.; Säflund, M. (octubre de 1990). "Modelado y verificación de sistemas y software en lógica proposicional". IFAC Proceedings Volumes . 23 (6): 31– 36. doi : 10.1016/S1474-6670(17)52173-4 .
  9. ↑ Möhle, Sibylle; Biere, Armin (2019). «Backing Backtracking». Theory and Applications of Satisfiability Testing – SAT 2019 (PDF) . Lecture Notes in Computer Science. Vol. 11628. pp. 250–266 . doi : 10.1007/978-3-030-24258-9_18 . ISBN   978-3-030-24257-2. S2CID 195755607 . 
  10. ↑ Van Beek, Peter (2006). «Algoritmos de búsqueda con retroceso» . En Rossi, Francesca; Van Beek, Peter; Walsh, Toby (eds.). Manual de programación con restricciones . Elsevier. pág. 122. ISBN  978-0-444-52726-4.

Lecturas adicionales

  • Malay Ganai; Aarti Gupta; Dra. Aarti Gupta (2007). Soluciones de verificación formal escalables basadas en SAT . Springer. págs. 23–32 . ISBN  978-0-387-69166-4.
  • Gomes, Carla P.; Kautz, Henry; Sabharwal, Ashish; Selman, Bart (2008). «Solucionadores de satisfacibilidad». En Van Harmelen, Frank; Lifschitz, Vladimir; Porter, Bruce (eds.). Manual de representación del conocimiento . Fundamentos de la inteligencia artificial. Vol.  3. Elsevier. pp. 89–134 . doi : 10.1016/S1574-6526(07)03002-7 . ISBN  978-0-444-52211-5.
Lecturas relacionadas
6 articulos
Cartel de 1901LógicaLa lógica estudia formas válidas de inferencia como el modus ponens . La lógica es el estudio del razonamiento correcto . Incluye tanto la lógica f...Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...Algoritmo de búsquedaAlgoritmo de búsquedaEn informática , un algoritmo de búsqueda es un algoritmo diseñado para resolver un problema de búsqueda . Los algoritmos de búsqueda funcionan par...{\displaystyle \models _{\mathcal {S}}\varphi \ \to \ \vdash _{\mathcal {S}}\varphi .}Completitud (lógica)En lógica matemática y metalógica , un sistema formal se llama completo con respecto a una propiedad particular si cada fórmula que tiene la propie...BacktrackingBacktracking is a class of algorithms for finding solutions to some computational problems , notably constraint satisfaction problems , that increm...Problema de satisfacibilidad booleanaProblema de satisfacibilidad booleanaEn lógica y ciencias de la computación , el problema de satisfacibilidad booleano (a veces llamado problema de satisfacibilidad proposicional y abr...