search

IIC2213 / Syllabus-2021-1-

19 stars 2 forks source link

[Tarea 5] Duda algoritmo mejorado #65

Open benjaminlillo opened 3 years ago

benjaminlillo commented 3 years ago

Hola! Para el algoritmo mejorado se nos pide que:

Este algoritmo debe incorporar al menos una mejora importante a fuerza bruta, puede ser DPLL, resolución, o algo aún mejor.

¿Con "algo aún mejor" se refiere a que sea mejor que DPLL y resolución? ¿O simplemente que sea mejor que fuerzabruta?

juanreutter commented 3 years ago

simplemente mejor que fuerza bruta. Con importante me refiero a que se cambie la forma de trabajar la búsqueda de una valuación que satisfaga la formula. Por ejemplo, DPLL arma un árbol de búsqueda a partir de un orden de las proposiciones, y va cortando ese árbol. Resolución va buscando encontrar una contradicción, por lo que ni siquiera busca una valuación, solo contesta "no hay contradicción" cuando la fórmula es satisfacible.

Una optimización como las del #64 no cambia la naturaleza, se siguen probando todas las valuaciónes (solo que la forma de evaluar una fórmula con una valuación es un poco más rápida)

benjaminlillo commented 3 years ago

Perfecto, gracias!