I Avance

I Avance.
Evaluación del código entregado
Para poder hacer una evaluación exhaustiva o aplicación del algoritmo entregado por el cliente, se
requiere entender muy bien el funcionamiento del algoritmo DPLL con sus vertientes, considero
necesario entregar este análisis previo, para luego dar un veredicto final o una mejor propuesta al
código que se ha entregado. Mi experiencia como programadora me indica que resulta menos
complicado hacer un código desde cero que tratar de entender un código realizado por otro
programador. Dicho esto comenzaré mi análisis del algoritmo DPLL y una propuesta de pseudocódigo
que se puede aplicar para próximas entregas.
El DPLL puede expresarse en forma normal conjuntiva (FNC), lo que significa una conjunción de
cláusulas, es decir, (...) ^ (...) ^ (...)
Donde una cláusula es una disyunción de variables booleanas, es decir (A v B v C 'v D). Un ejemplo de
fórmula booleana expresada en FNC es:
(A v B v C) ^ (C 'v D) ^ (D' v A)
Para resolver el problema SAT significa encontrar la combinación de valores para las variables en la
fórmula que lo satisfacen como A = 1, B = 0, C = 0, D = 0
Supongamos que quiere resolver un problema SAT como este
(A v B v C) ^ (C 'v D v B) ^ (B v A' v C) ^ (C 'v A' v B ')
Si enumeramos las variables como A = 1 B = 2 C = 3 D = 4 y vemos números negativos para variables

negadas como A '= -1, entonces la misma fórmula se puede escribir en Python de esta forma:
[[1,2,3], [- 3,4,2], [2, -1,3], [- 3, -1, -2]]
Es decir se lleva forma canoníca, es un abre boca como para entender como se aplicaría el algoritmo en
python.
Ahora presento una manera resumida de entender el algoritmo.
DPLL (Ø)
Entrada: Ø: cadena con la fórmula en FNC
Salida: cierto si la fórmula es satisfacible, falso de otra forma
 Casos base
1. Si Ø es vacía regresa cierto
2. Si existe una cláusula vacía en Ø regresa falso
 Otros casos
3. Si (ꝭ) es una cláusula unitaria en Ø regresa DPLL (Ø(ꝭ))
4. Si existe una literal para ꝭ en Ø regresa DPLL (Ø(ꝭ))
5. Selecciona una variable ⱴ que aparece en Ø
I Avance. Evaluación del código entregado
6. Si DPLL (Ø(ⱴ)) regresa cierto

7. En caso contrario regresa DPLL (Ø (¬ⱴ))
Existen elementos del código entregado por el cliente que se pueden aprovechar para algunas partes
del algoritmo.
A continuación presentaré un pseudocódigo sugerido que se puede aplicar al proyecto, esto con la
finalidad de implementar el algoritmo anterior
[https://upcommons.upc.edu/bitstream/handle/2117/87417/T064.pdf;jsessionid=4DD578B9E551EA3D869DD3F70
DBE5F3E?sequence=1]
Las funciones principales del algoritmo son las siguientes:
1. Unitpropagation: Esta función propaga literales en M usando al heurística de two-watched literal.
2. Backjump: La función backjump una vez alcanzado un conflicto, y no pudiéndose aplicar la regla f ail,
genera el tratamiento de conflicto para determinar a que punto debe volver la asignación M.
Learn es la función que aprende las cláusulas generadas por la función calculus, y evitar
conflictos posteriores.
Forget esta función, borra algunas de las cláusulas aprendidas por la función learn, mirando el
índice de cláusulas menos usadas por la función verifica y eliminándolas.
regresa-l esta función, regresa al literal decisional penúltima y borra las literales propagadas en
el presente nivel de decisión agregando la última literal decisional como l 0.
calculus. esta función calcula el UIP, sobre el cual se debo volver, mediante la aplicación de la
regla de resolución.
existe-espacio. Esta función verifica si existe espacio para aprender, si es así retorna TRUE, en
caso contrario false.
3. Decide: En esta función, se elige la literal decisional que se ha de elegir para continuar la expansión de
M, cuando no es posible expandir la asignación M a partir de alguna otra regla. La heurística usada para
la selección de una literal l, es que al principio del programa se genera una lista de todas las literales
existentes en F, y se crea un listado de por ordenado de mayor a menor por orden de aparición en M.
Una vez obtenida esta lista la función decide, hace un recorrido por ella y selecciona la literal que tenga
un índice de incidencia superior y que además no esté asignada en M.
4. Fail: Esta función verifica si se ha alcanzado el estado de falla (fail state). Si es así termina el programa.
5. Verifica: Esta función verifica si existe un conflicto de M sobre alguna cláusula perteneciente, si hay M
puede ser extendido por que existe literales de propagación pendiente. Además contiene actualizado el
listado de que cláusulas aprendidas que aparecen en casos de conflicto, y el listado de las literales que
también aparecen en casos de conflicto.
Lo anterior lo cito ya que me parece muy interesante para entender y aplicar el algoritmo DPLL, es muy
importante acotar que no es el resultado definitivo que se pueda aplicar al proyecto final, es una forma
de avanzar en el proceso y en el análisis definitivo de una solución.
Como se puede observar el pseudocódigo tiene varios casos, que es en sí lo que aplica el algoritmo de
DPLL, viendo el código presentado por el cliente, presenta varias funciones, pero quizás se puedan
organizar por casos y estructurar de forma más práctica el producto final.
El código lo traté de ejecutar y dio errores, por lo cual hay que validar cada línea y luego introducir la
fórmula para poder probar la codificación completa, sin embargo considero que si se puede aprovechar
parte del código escrito. Además que ese código lo estoy comprando con un programa que está
realizado en python y otro en javascript, entonces estoy revisando y probando todos los códigos,
mismos que nos conducirán a una solución satisfactoria para la resolución del problema.
En otro orden de ideas, y completando la actividad que entregaré en este avance, la programación en
python que emplearé para el desarrollo de los algoritmos será estructurada, considero que es más
sencilla de entender, sin embargo si existiese alguna clase que simplifique el objetivo final del proyecto,
se podría aplicar. Igualmente la interfaz gráfica que se empleará para ver el funcionamiento de los
algoritmos, muy posiblemente se utilice POO, porque hay librerías en python que permitirán hacer de
esto una mejor solución.

I Avance

Cargado por

Copyright:

Formatos disponibles

I Avance

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

I Avance

Cargado por

Copyright:

Formatos disponibles

I Avance.

Evaluación del código entregado

Supongamos que quiere resolver un problema SAT como este

(A v B v C) ^ (C 'v D v B) ^ (B v A' v C) ^ (C 'v A' v B ')

Si enumeramos las variables como A = 1 B = 2 C = 3 D = 4 y vemos números negativos para variables

[[1,2,3], [- 3,4,2], [2, -1,3], [- 3, -1, -2]]

Ahora presento una manera resumida de entender el algoritmo.

Entrada: Ø: cadena con la fórmula en FNC

Salida: cierto si la fórmula es satisfacible, falso de otra forma

6. Si DPLL (Ø(ⱴ)) regresa cierto

Las funciones principales del algoritmo son las siguientes:

1. Unitpropagation: Esta función propaga literales en M usando al heurística de two-watched literal.

También podría gustarte