Satisfaccion y restriccion de juegos inteligencia artificial

Instituto Tecnológico Superior de
Misantla

Materia:
Inteligencia Artificial
Docente:
MIA. Roberto Ángel Meléndez Armenta
Temas:
 Satisfacción de Restricciones
 Teoría de Juegos
Presenta:
José Manuel Muñoz Contreras
Misantla, Ver a 18 Diciembre 2014.

Satisfacción de Restricciones
La programación por restricciones es una metodología software utilizada para la
descripción yposterior resolución efectiva de cierto tipo de problemas, típicamente
combinatorios y de optimización. Estos problemas aparecen en muy diversas áreas,
incluyendo inteligencia artificial, investigación operativa, bases de datos y sistemas de
recuperación de la información, etc., con aplicaciones en scheduling, planificación,
razonamiento temporal, diseño en la ingeniería, problemas deempaquetamiento,
criptografía, diagnóstico, toma de decisiones, etc. Estos problemas pueden modelarse
como problemas de satisfacción de restricciones (Constraint Satisfaction Problems - CSP)
y resolverse usando técnicas de satisfacción de restricciones. En general, se trata de
grandes y complejos problemas, típicamente de complejidad NP. Las etapas básicas para
la resolución de un problema CSP son sumodelización y su posterior resolución mediante
la aplicación de técnicas CSP específicas, que incluyen procesos de búsqueda apoyados
con métodos heurísticos y procesos inferenciales. En este capítulo se presentan los
conceptos, algoritmos y técnicas más relevantes en el área de los CSP, junto con diversos
ejemplos y ejercicios.
Muchas decisiones que tomamos a la hora de resolver diversosproblemas cotidianos
están sujetas a restricciones. Decisiones tan cotidianas como fijar una cita, planificar un
viaje, comprar un coche o preparar un plato de cocina puede depender de muchos
aspectos interdependientes e incluso conflictivos, cada uno de los cuales está sujeto a un
conjunto de restricciones que se deben satisfacer para que la decisión sea válida.
Además, cuando se encuentra unasolución que satisface plenamente a unos criterios,
puede que no sea tan apropiada para otros, por lo que, para obtener una solución
optimizada, no suele ser suficiente con obtener una única solución. Los primeros trabajos
relacionados con la programación de restricciones datan de los años 60 y 70 en el campo
de la Inteligencia Artificial. Durante los últimos años, la programación derestricciones ha
generado una creciente expectación entre expertos de muchas áreas debido a su
potencial para la resolución de grandes y complejos problemas reales. Sin embargo, al
mismo tiempo, se considera como una de las tecnologías menos conocida y comprendida.
La programación de restricciones se define como el estudio de sistemas computacionales
basados en restricciones. La idea de la programaciónde restricciones es resolver
problemas mediante la declaración de restricciones sobre el dominio del problema y
consecuentemente encontrar soluciones a instancias de los problemas de dicho dominio

que satisfagan todas las restricciones y, en su caso, optimicen unos criterios
determinados.

Problema de Satisfacción de Restricciones
Un problema de satisfacción de restricciones (PSR) vienedefinido por los siguientes
elementos:
• Un conjunto finito de variables X1, . . . , Xn
• Un conjunto finito de dominios Di asociados a cada variable Xi , especificando los
posibles valores que puede tomar.
• Un conjunto finito de restricciones C1, . . . , Cm, que definen una serie de propiedades
que deben verificar los valores asignados a las variables
• Una solución al problema es unaasignación de valores a las variables {X1 = v1, . . . , Xn
= vn} tal que vi ∈ Di y se verifican las restricciones
• Esta formulación permite una representación simple del problema, y el uso de
heurísticas de propósito general, independientes del problema

Satisfacción de Restricciones
Los componentes del estado, son equivalentes a un grafo de restricciones, los cuales están
compuestos de:
...