Nada

4.Busqueda y satisfacción de restricciones

La programación de restricciones puede dividirse en dos ramas claramente diferenciadas: la “satisfacción de restricciones” y la “resolución de restricciones”. Ambas comparten la misma terminología, pero sus orígenes y técnicas de resolución son diferentes.
La satisfacción de restricciones trata con problemas que tienen dominios finitos, mientras quela resolución de restricciones está orientada principalmente a problemas sobre dominios infinitos o dominios más complejos. En este capítulo, se tratarán principalmente los problemas de satisfacción de restricciones (CSP). Los conceptos clave en esta metodología corresponden a los aspectos de:
La modelización del problema, que permite representar un problema mediante un conjunto finito devariables, un dominio de valores finito para cada variable y un conjunto de restricciones que acotan las combinaciones válidas de valores que las variables pueden tomar. En la modelización CSP, es fundamental la capacidad expresiva, a fin de poder captar todos los aspectos significativos del problema a modelar.

Técnicas inferenciales que permiten deducir nueva información sobre el problema a partirde la explícitamente representada. Estas técnicas también permiten acotar y hacer más eficiente el proceso de búsqueda de soluciones.

Técnicas de búsqueda de la solución, apoyadas generalmente por criterios heurísticos, bien dependientes o independientes del dominio. El objetivo es encontrar un valor para cada variable del problema de manera que se satisfagan todas las restricciones delproblema. En general, la obtención de soluciones en un CSP es NP-completo, mientras que la obtención de soluciones optimizadas es NPduro, no existiendo forma de verificar la optimalidad de la solución en tiempo polinomial. Por ello, se requiere una gran eficiencia en los procesos de búsqueda.

Problemas de satisfacción de restricciones es un tipo especial de problemas que satisfacen algunaspropiedades adicionales. Las restricciones pueden involucrar una o varias variables al mismo tiempo. A veces en estos problemas conviene hacer una verificación hacia adelante (forward checking) para detectar estados sin solución (e.g., las 8-reinas). Muchas veces lo que conviene es analizar la variable más restringida, esto es, asignarle un valor a la variable que está involucrada en la mayor cantidad derestricciones. Otra heurística común es seleccionar un valor que elimine el menor número de valores en las otras variables asociadas a la variable por medio de una restricción.

A veces la descripción del estado contiene toda la información necesaria para llegar a una solución (e.g., las 8-reinas) y se utilizan algoritmos que hacen mejoras iterativas. La idea general es empezar con unaconfiguración completa y hacer modificaciones para mejorar su calidad. Normalmente, en problemas de maximización se trata de moverse hacia el pico más alto. Los métodos iterativos normalmente guardan sólo su estado actual y no ven mas allá de sus vecinos inmediatos.

Aquí podemos mencionar a gradiente descendiente (hill-climbing) y a recocido simulado (pero esos los veremos más adelante).

4.1.Problemas y Espacios de estados

Muchos de los problemas que pueden ser resueltos aplicando técnicas de inteligencia artificial se modelan en forma simbólica y discreta definiendo las configuraciones posibles del universo estudiado. El problema se plantea entonces en términos de encontrar una configuración objetivo a partir de una configuración inicial dada, aplicando transformaciones válidas según elmodelo del universo. La respuesta es la secuencia de transformaciones cuya aplicación sucesiva lleva a la configuración deseada.

Los ejemplos más característicos de esta categoría de problemas son los juegos (son universos restringidos fáciles de modelar). En un juego, las configuraciones del universo corresponden directamente a las configuraciones del tablero. Cada configuración es un...