IA - PSR


Inteligencia Artificial
Problemas de satisfacción de restricciones






Índice

Introducción 3
Problemas de satisfacción de restricciones 4
Búsqueda por vuelta atrás 7
Variable yordenamiento de valor 8
Propagación de la información a través de las restricciones 8
Comprobación hacia delante 8
Vuelta atrás inteligente 10
Búsqueda local para problemas de satisfacción derestricciones 11
Estructura de los problemas 12
Conclusión 16
Bibliografía 17


Introducción



Hasta ahora en las clases anteriores se han tratado a los estados como si fueran una caja negra sinuna estructura perceptible interna.

Los representamos por una estructura de datos arbitraria a la que se puede acceder solo son funciones específicas (función sucesor, heurística, test objetivo).Al tratar los estados como más que solo pequeñas cajas negras encontraremos nuevos poderosos métodos de búsqueda y entender mejor la estructura y complejidad del problema
Problemas de satisfacciónde restricciones

Formalmente, un problema de satisfacción de restricciones (o PSR) está definido por un conjunto de variables, X1, X2…, Xn, y un conjunto de restricciones, C1, C2…, Cm. Cadavariable Xi tiene un dominio no vacío Di de valores posibles. Cada restricción Ci implica algún subconjunto de variables y especifica las combinaciones aceptables de valores para ese subconjunto. Un estadodel problema está definido por una asignación de valores a unas o todas las variables, {Xi _ vi, Xj _ vj…}. A una asignación que no viola ninguna restricción se llama asignación consistente o legal.Una asignación completa es una asignación en la que se menciona cada variable, y una solución de un PSR es una asignación completa que satisface todas las restricciones. Algunos problemas desatisfacción de restricciones
(PSRs) también requieren una solución que maximiza una función objetivo.
Ejemplo:
Vemos un mapa de Australia que muestra cada uno de sus estados y territorios, como en la...