1. Representando problemas como fórmulas booleanas:
* Codificación: La idea central de usar solucionadores SAT es codificar Un problema dado (por ejemplo, programación, diseño de circuitos, planificación) en una fórmula booleana en forma normal conjuntiva (CNF). Esto implica identificar las variables de decisión del problema y representar las restricciones en estas variables como cláusulas lógicas. La belleza radica en el hecho de que se puede expresar una amplia variedad de problemas en este formato.
* Forma normal conjuntiva (CNF): Casi todos los solucionadores SAT operan en fórmulas en CNF. CNF es una fórmula lógica que es una conjunción (y) de cláusulas, donde cada cláusula es una disyunción (o) de literales. Un literal es una variable o su negación. Por ejemplo:`(x o no y o z) y (no x o y)`. Estar en CNF hace que el proceso de búsqueda sea más estructurado y eficiente.
2. Algoritmo de Davis-Putnam-Logemann-Loveland (DPLL):
* Enfoque basado en la búsqueda: DPLL es el algoritmo fundamental para resolver problemas SAT. Es un algoritmo de búsqueda completo que explora sistemáticamente el espacio de posibles asignaciones de variables.
* Decisión: El algoritmo elige una variable que actualmente no está asignada y la asigna `verdadero` o` falso '. Esta elección crea dos ramas en el árbol de búsqueda.
* Propagación de la unidad: Después de tomar una decisión, DPLL realiza propagación de la unidad. Una cláusula unitaria es una cláusula que contiene solo un literal no asignado. Si existe una cláusula unitaria (por ejemplo, `x`), el algoritmo * debe * asignar la variable` x` al valor que hace que la cláusula sea verdadera (en este caso, `x =true`). La propagación de la unidad puede cascade, lo que lleva a más asignaciones de variables. Esto es crucial para simplificar el problema y evitar la búsqueda innecesaria.
* Eliminación literal pura: Un literal puro es un literal que aparece en una sola polaridad (positiva o negativa) en toda la fórmula. Si existe un literal puro, se le puede asignar un valor para hacer que todas las cláusulas lo contengan. Esto simplifica la fórmula sin afectar la satisfacción.
* retroceso: Si una rama de la búsqueda conduce a un conflicto (es decir, una cláusula se vuelve falsa), el algoritmo *retroceso *. Esto significa deshacer la última decisión y probar la tarea opuesta. Todo el proceso continúa hasta que se encuentre una tarea satisfactoria (la fórmula es SAT) o se han agotado todas las tareas posibles (la fórmula no está SAT).
3. Aprendizaje de cláusula impulsada por conflictos (CDCL):
* Aprendiendo de los conflictos: Los solucionadores SAT modernos se basan en CDCL, una extensión de DPLL. La innovación clave es que cuando se encuentra un conflicto, el solucionador analiza las razones del conflicto y aprende una nueva cláusula (una cláusula de conflicto) que evita que el mismo conflicto vuelva a ocurrir en el futuro.
* Análisis de conflictos: El proceso de análisis de conflictos utiliza el gráfico de implicación (un gráfico que representa las dependencias entre las asignaciones variables) para determinar un subconjunto de las decisiones que condujeron al conflicto.
* Aprendizaje de la cláusula: La cláusula de conflicto se agrega a la fórmula, típicamente utilizando el esquema "Primer punto de implicación único (UIP)". La cláusula resultante es una consecuencia lógica de la fórmula original, por lo que agregarla no cambia la satisfacción.
* retroceso no cronológico (chorro de retroceso): Los solucionadores CDCL pueden retroceder no cronológicamente. En lugar de deshacer la última decisión, pueden volver a un nivel de decisión anterior responsable del conflicto. Esto permite que el solucionador explore el espacio de búsqueda de manera más eficiente.
* Eleción de la cláusula: Para evitar que la fórmula crece demasiado grande, los solucionadores eliminan periódicamente algunas de las cláusulas aprendidas. Las heurísticas se utilizan para decidir qué cláusulas eliminar, equilibrando la necesidad de recordar información útil con la necesidad de mantener la fórmula manejable.
4. Heurística de ordenar variable (heurística de ramificación):
* Impacto en la eficiencia: El orden en el que se seleccionan las variables para la decisión (ramificación) tiene un impacto dramático en el rendimiento de los solucionadores SAT. Las buenas heurísticas pueden reducir significativamente el tamaño del árbol de búsqueda.
* VSIDS (suma de descomposición independiente del estado variable): Una heurística popular es VSIDS. Mantiene una puntuación para cada variable, que se incrementa cada vez que la variable está involucrada en un conflicto. Los puntajes se detienen periódicamente, dando preferencia a las variables que han estado recientemente involucradas en conflictos. Esta heurística enfoca la búsqueda en las partes "activas" de la fórmula.
* Otras heurísticas: Otras heurísticas consideran la frecuencia de las variables en las cláusulas, el número de cláusulas no resueltas que contienen una variable o usan técnicas de aprendizaje automático para aprender estrategias de ramificación.
5. Cláusula ordenando heurística:
* Propagación de la unidad de guía: El orden en el que se consideran las cláusulas para la propagación de la unidad también puede afectar el rendimiento.
* Vio literales: La mayoría de los solucionadores usan una técnica llamada literales observados. Para cada cláusula, se eligen dos literales como "observados". La propagación de la unidad solo debe activarse cuando uno de los literales observados se vuelve falso. Esto reduce significativamente el número de cláusulas que deben examinarse.
6. Reiniciar estrategias:
* escapando de los mínimos locales: Los solucionadores CDCL a veces pueden atascarse en una parte del espacio de búsqueda que es difícil de explorar. Reiniciar el solucionador periódicamente puede ayudar a escapar de estos mínimos locales.
* reinicio a base de glucosa: Los solucionadores modernos a menudo utilizan estrategias de reinicio basadas en la calidad de las cláusulas aprendidas. Por ejemplo, la estrategia de reinicio de glucosa reinicia el solucionador con más frecuencia cuando aprende muchas cláusulas de baja calidad.
7. Preprocesamiento y procesamiento:
* simplificando la fórmula: Las técnicas de preprocesamiento se aplican a la fórmula * antes de * Comienza el principal proceso de búsqueda. Estas técnicas tienen como objetivo simplificar la fórmula eliminando cláusulas redundantes, sustituyendo variables y realizando otras transformaciones lógicas.
* Incrusionamiento: Se aplican técnicas de procesamiento * durante * el proceso de búsqueda. Estas técnicas pueden simplificar dinámicamente la fórmula en función del estado actual de la búsqueda.
* Ejemplos: El preprocesamiento y el procesamiento incluyen subsunción (eliminación de cláusulas que están lógicamente implícitas por otras cláusulas), resolución (agregando nuevas cláusulas a la fórmula basada en las cláusulas existentes) y la eliminación variable (reemplazando una variable con su definición).
8. Paralelo SAT Resolviendo:
* Divide y conquista: Los solucionadores SAT paralelos explotan el paralelismo inherente al proceso de búsqueda. Pueden dividir el espacio de búsqueda en múltiples partes y explorarlas simultáneamente.
* Se acerca a la cartera: Otro enfoque es ejecutar múltiples solucionadores SAT diferentes (con diferentes configuraciones de parámetros) en paralelo, y esperar que uno de ellos encuentre una solución rápidamente.
* Compartir la cláusula: Los solucionadores paralelos pueden compartir cláusulas aprendidas entre diferentes procesos para mejorar la eficiencia de búsqueda general.
9. Resolución de teoría (SMT):
* Más allá de la lógica booleana: Los solucionadores SAT a menudo se usan como un componente central de los solucionadores de teorías de módulos de satisfacción (SMT). Los solucionadores SMT pueden razonar sobre fórmulas que contienen variables y restricciones de otras teorías, como aritmética, cadenas o matrices.
* Combinando SAT con solucionadores específicos de la teoría: Los solucionadores SMT utilizan una combinación de técnicas de resolución de SAT y solucionadores específicos de la teoría para determinar la satisfilidad de las fórmulas.
En resumen, los principios clave de la resolución de SAT giran en torno a explorar eficientemente el espacio de posibles tareas variables, aprender de conflictos para evitar repetir errores y simplificar la fórmula para reducir el espacio de búsqueda. Los solucionadores SAT modernos son herramientas altamente sofisticadas que pueden resolver problemas con millones de variables y cláusulas.