programacion con restricciones

IMPLEMENTACION DE AC6 Y MAXRPC….
JAIME DAMIAN ROMERO FERNANDEZ
HECTOR ANDRES ORTEGA MATURANA
INFORME DE AVANCE DE PROYECTO I
PARA OPTAR AL TÍTULO DE
INGENIERO DE EJECUCIÓN EN INFORMÁTICA



IMPLEMENTACION DE AC6 Y MAXRPC
JAIME DAMIAN ROMERO FERNANDEZ
HECTOR ANDRES ORTEGA MATURANA
Profesor Guía: Ricardo Soto de Giorgis.
Profesor Co-referente: Broderick crawford labrín.
Carrera:Ingeniería de Ejecución en Informática.
Resumen
La cantidad de problemas que se pueden expresar como Problemas de Satisfacción de Restricciones o CSP son demasiados, para lograr representarlos de esta manera se deben reconocer las variables que participan y los dominios respectivos, así como también la cantidad limitada de restricciones. La forma en que se encuentran la o las soluciones, dependende las Técnicas de Consistencia que se implementen, las que ayudarán a reducir la cantidad de nodos que se instanciarán en el proceso de búsqueda. Las utilizadas para el presente informe son la Arco-Consistencia y la Camino-Consistencia, las cuales se aplica a restricciones binarias. Existe una amplia gama de algoritmos de arco-consistencia, pero para efectos de esta investigación dicha gama seredujo en sólo un algoritmo, AC-6. Asimismo, para la otra técnica utilizaremos MaxRPC. Estos procesos trabajarán en conjunto con un algoritmo de búsqueda, para poder cuantificar la calidad del podado. Finalmente, los dos procesos se utilizarán como una Consistencia Adaptativa, con el propósito de resolver de forma correcta y eficiente un problema, así como también lograr mejorar los tiempos debúsqueda en las soluciones.
Palabras Claves: Problemas de Satisfacción, Técnicas de Consistencia, Arco-Consistencia, Consistencia Adaptativa, Camino-Consistencia.
Índice




Lista de Figuras




1 Introducción
Nuestro diario vivir conlleva un sin fin de toma de decisiones que están sujetas a restricciones. Problemas tan simples como comprar pan, realizar una junta con amigos, planificarun viaje, entre otras. Se ven afectadas por restricciones, tales como presupuesto, tiempo, disponibilidad de tus amigos, etc. estos factores generan conflictos en la búsqueda da la solución más optima para el problema, dado que para cada problema existe un sin fin de posibles soluciones satisfactorias, entre las cuales se encuentra la solución que cumple con todas las restricciones potenciando demejor manera la solución que las demás.
Entre los años 60 y 70 se realizaron los primeros trabajos de programación con restricciones, hoy en día surgen grandes expectativas por los expertos de diferentes aéreas por el potencial que puede llegar a tener en la resolución de problemas muy grandes, llegando a ser identificada como una de las direcciones estratégicas de la investigación informática.A pesar de esto se considera como una de las tecnologías menos comprendidas.
La programación con restricciones (CP) es definida como el estudio de sistemas computacionales basados en restricciones. Esta tecnología se utiliza para describir y solucionar de manera efectiva grandes y complejos problemas, se puede dividir en dos ramas claramente distintas una de la otra, la satisfacción derestricciones y la resolución de restricciones, las cuales comparten la misma terminología pero teniendo diferencias en lo que respecta a origen y técnicas de resolución. En este informe se dará un enfoque hacia los problemas de satisfacción de restricciones (CSPs, Constraint Satisfaction Problems).
Un CSPs consta de un conjunto de variables, dominios y restricciones, que respecta al modelamiento delproblema. Al procesar este problema existen dos maneras de tratar las restricciones: Técnicas de consistencia y Algoritmos de búsqueda. En el primer caso se tratan de técnicas para solución de CSPs basado en la eliminación de los dominios de las variables, es decir que no permita llegar a aquellos valores con los cuales no sea posible llegar a una solución factible, reduciendo el árbol para...