Page 183 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 183
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
el problema de satisfacibilidad booleana
• Un problema es satisfacible si existe al menos una asignación de valores a las
variables del problema que lo hagan verdadero ( ).
• Un problema es insatisfacible si todas las posibles asignaciones de valores
hacen el problema siempre falso ( ).
Veamos esto con un ejemplo:
• Se va a partir de la siguiente proposición en forma normal disyuntiva:
• Se realiza la siguiente asignación:
• Se sustituye en la expresión:
• Se evalúa la expresión .
• Como no se ha encontrado una solución válida, se hace una nueva asignación:
• Se evalúa la expresión .
Como se ha encontrado una asignación de valores (modelo) que hacen a la expresión verdadera, se
ha demostrado que este problema en concreto es satisfacible.
Estas son solo dos de las ocho (2 n = 3 ) posibles asignaciones. Se puede apreciar que el número de
soluciones crece rápidamente al añadir nuevas variables, de ahí que su complejidad computacional
sea elevada.
Un algoritmo creado para la resolución de problemas SAT es el siguiente:
• Algoritmo DPLL: Utiliza una búsqueda hacia atrás sistemática (backtracking)
para explorar las posibles asignaciones de valores a las variables que hagan al
problema satisfacible.
177
