1

Capítulo 5

SATISFACCION DE RESTRICCIONES

Sección 1-3

2

Bosquejo

El problema de satisfacción de restricciones (CSP)

Backtracking en CSPsLa búsqueda local para CSPs

3

El problema de restricción (CSPs)

• El problema estándar de búsqueda:• La condición es una “caja negra” – cualquier estructura

de datos que soporta la función sucesor, cualquiera función heurística, y cualquiera meta experimenta CSP:

• La condición está definida por la variable Xi con valores de dominio Di

• La prueba de meta es jugar especificando las restricciones y combinaciones admisibles de valores para los subconjuntos de variables

• El ejemplo simple de un lenguaje formal de representación

• Deja los algoritmos útiles multiusos con más poder que los algoritmos estándar de búsqueda

4

Ejemplo: coloración de un Mapa

• Variable WA, NT, Q, NSW, V, SA, T• Dominio Di = { rojo, verde, azul }• Las restricciones: Las regiones adyacentes deben tener colores

diferentes• v.g., WA ≠ NT, o (WA, NT) { (rojo, verde), (rojo, azul), (verde, rojo),

(verde, azul), (azul, rojo), (azul, verde) }

5

Soluciones: asignaciones completas y coherentes

{WA, rojo}, {NT, verde}, {Q, rojo}, {NSW, verde}, {SA, azul}, {T, verde}, {V, rojo}

Ejemplo: coloración de un Mapa

6

Gráfico de restricciones

• CSP binario: Cada restricción relaciona dos variables• Gráfico de restricciones:

nodos variables, arcos restricciones

7

Variedades de CSPs• Las variables discretas

• Los dominios finitos• n variables, el tamaño de dominio d O(dn) asignaciones completas

• Los dominios infinitos• Los enteros, los instrumentos de cuerda, etc.• v.g., El trabajo programando, variedad de días de

principio /fin para cada trabajo• Restricción nescesita un lenguaje de programación• v.g., StartJob1 + 5 antes StartJob3

• Las variables continuas• v.g., El principio/fin toma el tiempo para

observar• Las restricciones lineales recientes en el

tiempo la programación de polinomios lineales

8

Variedades de restricciones• Unas restricciones implican una sola

variable • v.g., SA ≠ ‚ verde

• Las restricciones binarias implican pares de variables• v.g., SA ≠ WA

• Las restricciones de orden superior involucran 3 o más variables• v.g., Las restricciones de columna de la

criptoaritmética

9

Ejemplo: Criptoaritmética

• Las variables: F T U W R O X1 X2 X3

• Los dominios: {0,1,2,3,4,5,6,7,8,9}• Las restricciones: Alldiff (F,T,U,W,R,O)

– O + O = R + 10 · X1

– X1 + W + W = U + 10 · X2

– X2 + T + T = O + 10 · X3

– X3 = F, T ≠ 0, F ≠ 0

––

–•

10

Los CSPs del mundo real

• Problemas de asignación- v.g., Quien y que clase enseñe

• Problemas temporales- v.g., ¿Cuál clase es ofrecida cuándo y

dónde?• Planificación del transporte• Planificación de fábricas

• Note que muchos problemas del mundo real implican variables de valores reales

11

Formulación estándar (incremento) de búsqueda

Comencemos con el acercamiento directo, luego arreglémoslo

• Las condiciones están definidas por los valores asignados hasta ahora

• La condición inicial: La asignación vacía { }• La función sucesora: Asigne un valor a una variable que

no entre en conflicto con asignación actual falle si no hay asignaciones legales

• La prueba de meta: La asignación actual es completa

• Esto es lo mismo para todos los CSPs• Cada solución aparece a profundidad n (no. de variables)

use búsqueda a lo profundo• El camino es irrelevante, así es que también puede usar

formulación de condición completa

12

Búsqueda hacía atras

13

Ejemplo: de búsqueda hacía atras

14

Ejemplo: de búsqueda hacía atras

15

Ejemplo: de búsqueda hacía atras

16

Ejemplo: de búsqueda hacía atras

17

Búsqueda hacía atrás mas eficiente

• Los métodos multiusos pueden dar ganancias enormes en la velocidad:• ¿Cuál variable debería ser asignada

después?• ¿El que hace el pedido deberían

probar sus valores?• ¿Podemos detectar un fracaso

inevitable antes de que pase?

18

La variable más restringida

• Escoger la variable con menos valores permitidos

• El faltante heurístico del mínimo de a.k.a. se aprecia (MRV)

19

La variable restringida• La pregunta de desempate entre la mayoría de

variables restringidas• La variable restringida:

- Escoja la variable con las la mayoría de restricciones en las variables restantes

20

El valor restringido

• Dada una variable, escoger el valor menos restringido

• Combinando estas heurísticas - 1000 reinas

21

Contener para enviar• Registrar los valores permitidos para las variables

disponibles• Terminar cuando alguna variable no tenga valores

permitidos

22

Contener para enviar• Registrar los valores permitidos para las variables

disponibles• Terminar cuando alguna variable no tenga valores

permitidos

23

Contener para enviar• Registrar los valores permitidos para las variables

disponibles• Terminar cuando alguna variable no tenga valores

permitidos

24

Contener para enviar• Registrar los valores permitidos para las variables

disponibles• Terminar cuando alguna variable no tenga valores

permitidos

25

Propagación de restricciones

• Contener para enviar información de las variables disponibles, pero no provee detección para todos los fracasos:

• ¡NT y SA ambos no pueden ser azules!• La propagación de restricciones

repetidamente implementa restricciones localmente

26

Consistencia formada • La forma más simple de propagación de cada arco

consistente• X Y si consistente• Pues cada valor de x, allí permite X

27

Consistencia formada• La forma más simple de propagación de cada arco

consistente• X Y si consistente• Pues cada valor de x, allí permite X

28

Consistencia formada• La forma más simple de propagación de cada arco

consistente• X Y si consistente• Pues cada valor de x, allí permite X

Si la X pierde un valor, entonces los vecinos de X necesitan ser a los que se tomarón

29

Consistencia formada• La forma más simple de propagación de cada arco

consistente• X Y si consistente• Pues cada valor de x, allí permite X

Si la X pierde un valor, entonces los vecinos de X necesitan ser a los que se tomaronLa consistencia formada detecta el fracaso antes que la comprobación delanteraPuede ser dirigida como un preprocesador o después de cada asignación

30

El algoritmo de la consistencia formada AC-3

Complejidad: O(n2d3)

31

Búsqueda local para CSPs

• La búsqueda hacia arriba, simulado la busqueda de forja simulada, típicamente trabaja con condiciones "completas", i.e., Se asignan todas las variables

• Para aplicar a los CSPs:- Deje las condiciones con restricciones - Los operadores reasignan variables a los valores

• Selección variable: Al azar seleccione cualquier variable estando dentro

- Escoja un valor que viole las menos restricciones- i.e., La búsqueda hacía arriba con un número total de = h(n)

de restricciones violadas

32

Ejemplo: 4 reinas• Condiciones: 4 reinas en 4 columnas• Acciones: Mueva a la reina en su columna• Prueba de meta: Ningún ataque• Evaluación: = h(n) el número de ataques

• Condición inicial aleatoria. Puede solucionar n-reinas en tiempo casi constante para n arbitraria con alta probabilidad (v.g., n= 10,000,000)

33

Resumen

• Los CSPs son problemas especiales:- Condiciones definidas por los valores de un conjunto fijo de

variables- Prueba de meta definida por las restricciones en los valores de

las variables

• Búsqueda hacia atrás = primera en la profundidad con una variable asignada por nodo

• El ordenamiento de las variables y las heurísticas de selección de valor ayudan significativamente

• La comprobación para enviar impide asignaciones para fracasos posteriores

• La propagación de restricciones (v.g., La consistencia formada) hace trabajo adicional para restringir valores y detectar incongruencias

• El minimo conflicto iterativo es usualmente efectivo en la práctica