Una introducción a los algoritmos de satisfactibilidad

View/ Open
Issue date
2003Suggested citation
Ansótegui Gil, Carlos José;
Manyà Serres, Felip;
.
(2003)
.
Una introducción a los algoritmos de satisfactibilidad.
Inteligencia artificial: revista iberoamericana de inteligencia artificial, 2003, vol.7, núm.20, p.43-56.
http://hdl.handle.net/10459.1/47674.
Metadata
Show full item recordAbstract
En este artículo se presenta una introducción a los algoritmos de satisfactibilidad.
Primero, se describe el procedimiento de Davis-Putnam, que constituye la base de la
mayoría de algoritmos completos (por ejemplo: Satz, SATO, GRASP y Chaff). Después,se presentan las mejoras que pueden incorporarse al procedimiento de Davis-Putnam para obtener un algoritmo competitivo: estructuras de datos optimizadas, heurísticas de selecciónn de variable, backtracking no cronológico, aprendizaje de cláusulas, aleatorización y reinicios. Finalmente, se describen GSAT y WalkSAT, que son los algoritmos incompletos de búsqueda local más utilizados.