Hola

Inteligencia
Artificial

Problema de
Satisfacción de
Restricción


Facultad de Ingeniería en Ciencias Aplicadas
Carrera de Ingeniería en Sistemas Computacionales

Temas a tratar
• Problemas de Satisfacción de restricciones
• Búsqueda con vuelta atrás para PSR
• Propagación de la información a través de las restricciones

• Comprobación hacia Adelante
• Propagación derestricciones

• Manejo de restricciones especiales
• Vuelta atrás inteligente(mirando hacia atrás).

•

Búsqueda local para PSR

• Estructura de los problemas

Problemas de Satisfacción de
restricciones
Esta definido por un conjunto de variables x1,….xz , y un
conjunto de restricciones c1,…..cz , cada variable tiene un
dominio vacío de valores posibles, por ende cada
restricción tendrá unsubconjunto de las combinaciones
posibles

Búsqueda con vuelta atrás para
PSR
• Este método se utiliza para que busque
principalmente en profundidad en donde se
elige valores para una variable a la vez y
vuelve atrás cuando una variable no tiene
ningún valor legal para asignarle.

Propagación de Restricciones

Se dan cuando se elije una variable y se considera las restriccionessobre una variable, pero mirando algunas restricciones antes en la
búsqueda o incluso antes de que haya comenzado la búsqueda

Comprobación hacia adelante

Manejo de restricciones
especiales
• Algoritmos de
propósito especial
Restricciones todasdif.
si hay m variables
implicadas en la
restriccion, y si tienen
n valores posibles
distintos, y m > n,
entonces la restricción
no puedesatisfacerse.

Algoritmo:
• Primero,
quite
cualquier
variable en la restriccion que
tenga un dominio con una sola
posibilidad, y suprima el valor
de esa variable de los dominios
de las variables restantes.
Repetir
mientras
existan
variables
con
una
sola
posibilidad.
Si
en
algun
momento se produce un
dominio vacio o hay mas
variables que valores en el
dominio, entonces se haescubierto una inconsistencia.

Restricción de recursos
• Llamada
restricción
como-máximo.

•

•
•

•

supongamos que hay dos vuelos, 271 y 272,
para los cuales los aviones tienen capacidades
de 156 y 385, respectivamente. Los dominios
iniciales para el numero de pasajeros sobre
cada vuelo son
Vuelo271e [0,165] y Vielo272e[0,385]
Supongamos ahora que tenemos la restricciónadicional que los dos vuelos juntos deben
llevar a las 420 personas: Vuelo271 +
Vuelo272e [420,420], Propagando los limites
de las restricciones, reducimos los dominios a
Vuelo271 e [35,165] y Vuelo272e[255,385]

Vuelta atrás inteligente: mirando
hacia atrás
• Este algoritmo de
Búsqueda tiene una
política muy simple
para saber que hacer
cuando falla una rama
de búsqueda: hacia
atráshasta la variable
anterior e intentar un
valor diferente para
ella. Se llama vuelta
atrás
cronológica,
porque se visita de
nuevo el punto de
decisión mas reciente.

• Conjunto conflicto.- Conjunto de
variables que causaron el fracaso.
• El método salto-atrás retrocede a la
variable mas reciente en el conjunto
conflicto.
• Si no se encuentra un valor legal,
debería devolver elelemento mas
reciente del conjunto conflicto con el
indicador de fracaso.
• El salto-atrás se da cuenta del
fracaso cuando el dominio de una
variable se hace vacío.

Búsqueda local para problemas de satisfacción de
restricciones
• Los algoritmos de búsqueda local resultan ser muy
eficaces en la resolución de muchos PSRs. Ellos utilizan
una formulación de estados completa: el estado inicialasigna un valor a cada variable, y la función sucesor, por
lo general, trabaja cambiando el valor de una variable a
la vez.
• Por ejemplo, en el problema de las 8 -reinas, el estado
inicial podría ser una configuración arbitraria de ocho
reinas en ocho columnas, y la función sucesor escoge a
una reina y piensa en moverla a otra parte en su
columna.

Heurística de mínimosconflíctos
•...