Hoy en día, muchos problemas reales pueden ser modelados como problemas de
satisfacción de restricciones (CSPs) y ser resueltos utilizando técnicas de programación de restricciones. Estos problemas pertenecen a diferentes áreas de conocimiento
tales como inteligencia artificial, investigación operativa, sistemas de información,
bases de datos, etc. Los CSPs pertenecen a la categoría de problemas NP-completos
por lo que es necesario el uso de herramientas que simplifiquen el problema de forma
que se encuentre una solución de forma eficiente. Las técnicas más comunes
para manejar un CSP son las técnicas de consistencia y las técnicas de búsqueda.
Las técnicas de consistencia o de filtrado tienen por objeto reducir el espacio de
búsqueda mediante el filtrado de los dominios de las variables. Las técnicas de arcoconsistencia
son las más utilizadas ya que llevan a cabo una importante poda de
dominios; eliminando valores que no formaran parte de la solución; de una manera
eficiente.
Por ello, proponer algoritmos que alcancen la arco-consistencia ha sido un punto
central en la comunidad científica reduciendo la complejidad tanto espacial como
temporal de estos algoritmos.
Sin embargo, muchos trabajos que investigan la arco-consistencia llevan a cabo
asumpciones que no están presentes en muchos problemas de la vida real. Por
ejemplo, un mismo par de variables pueden participar en más de una restricción (lo
que se denomina problema no-normalizado), y cuando el tamaño de los dominios
es grande, el proceso de normalización puede resultar prohibitivo. En estos casos
la 2-consistencia lleva a cabo una reducción de los dominios de las variables mayor
que la arco-consistencia por lo que los algoritmos de búsqueda pueden resultar más eficientes. Sin embargo, la literatura es escasa en relación al desarrollo de algoritmos
que alcancen la 2-consistencia.
En esta tesis presentamos nuevos algoritmos de arco-consistencia y de 2-consistencia
como algoritmos de preproceso para la resolución de problemas de satisfacción
de restricciones. / Arangú Lobig, MA. (2011). MODELOS Y TÉCNICAS DE CONSISTENCIA EN PROBLEMAS DE SATISFACCIÓN DE RESTRICCIONES [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/14120
| Identifer | oai:union.ndltd.org:upv.es/oai:riunet.upv.es:10251/14120 |
| Date | 23 December 2011 |
| Creators | Arangú Lobig, Marlene Alicia |
| Contributors | Salido Gregorio, Miguel Angel, Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació |
| Publisher | Universitat Politècnica de València |
| Source Sets | Universitat Politècnica de València |
| Language | Spanish |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/acceptedVersion |
| Source | Riunet |
| Rights | http://rightsstatements.org/vocab/InC/1.0/, info:eu-repo/semantics/openAccess |
Page generated in 0.0187 seconds