Una introducción a los algoritmos de satisfactibilidad

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