Una introducción a los algoritmos de satisfactibilidad

Thumbnail
View/Open
Issue date
2003
Author
Ansótegui Gil, Carlos José
Manyà Serres, Felip
Suggested 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.
Impact

Google Scholar logo  Google Scholar
Share
Export to Mendeley
Metadata
Show full item record
Abstract
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.
URI
http://hdl.handle.net/10459.1/47674
Is part of
Inteligencia artificial: revista iberoamericana de inteligencia artificial, 2003, vol.7, núm.20, p.43-56
Collections