2 BH5 CSP N

Satisfacción de restricciones

Introducción

Satisfacción de Restricciones

Notas

Componentes del estado:
Variables
Dominios (valores posibles para las variables)
Restricciones binarias entre las variables

Objetivo: Encontrar un estado que satisface las restricciones
(Asignación de valores a las variables, que satisfaga las restricciones)
Ejemplos:
Colorear mapas, crucigramas, 8-reinas, sudoku,...
Asignación/distribución/ubicación de recursos (distribución de tareas
de fabricación, ubicación de gasolineras, antenas de telefonía, ...)

cbea (LSI-FIB-UPC)

Inteligencia Artificial

Satisfacción de restricciones

Curso 2011/2012

1 / 17

Introducción

Representación

Notas

Estado = Grafo de restricciones
Variables = etiquetas de nodos
Dominios = contenido de nodos
Restricciones = arcosdirigidos y etiquetados entre nodos

Ejemplo: colorear un mapa
Dominios={Rojo,Verde,Azul,Amarillo}
Restricción := Desigualdad

cbea (LSI-FIB-UPC)

4

5

6

7

8

9

3

2

1

Inteligencia Artificial

Satisfacción de restricciones

Curso 2011/2012

2 / 17

Introducción

Algoritmos

Notas

Generación y prueba: enormemente ineficiente
Búsqueda ciega
Búsqueda en profundidad con backtracking cronológicoPropagación de restricciones
Antes de la búsqueda
Durante la búsqueda

cbea (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

3 / 17

Satisfacción de restricciones

Backtracking Cronológico

Búsqueda en profundidad con backtracking cronológico

Notas

Búsqueda en profundidad sobre las variables
Asignar valor por estrategia exhaustiva
Comprobar restricciones tras cada posible asignación
Sino se satisfacen para ningún valor, backtracking sobre la última
asignación válida

La búsqueda se realiza en el espacio de soluciones parciales
Backtracking cronológico: tipos de variables (pasadas, actual, futuras)

cbea (LSI-FIB-UPC)

Inteligencia Artificial

Satisfacción de restricciones

Curso 2011/2012

4 / 17

Backtracking Cronológico

Algoritmo Backtracking Cronológico

Notas

Función:backtracking_cronologico(vfuturas, solucion)
si vfuturas.es_vacio?() entonces
retorna solucion
sino
vactual ← vfuturas.primero()
vfuturas.borrar_primero()
para cada v ∈ vactual.valores() hacer
vactual.asignar(v)
solucion.anadir(vactual)
si solucion.valida() entonces
solucion ← backtracking_cronologico(vfuturas,solucion)
si no solucion.es_fallo?() entonces
retorna solucion
sinosolucion.borrar(vactual)
sino
solucion.borrar(vactual)
retorna solucion.fallo()
cbea (LSI-FIB-UPC)

Inteligencia Artificial

Satisfacción de restricciones

Curso 2011/2012

5 / 17

Backtracking Cronológico

Ejemplo: 4-reinas

Notas

Colocar 4 reinas, 1 en cada fila de un tablero 4x4, sin que se maten
Variables: R1 , ... , R4 (reinas)
Dominios: [1 .. 4] para cada Ri (columna)
Restricciones: Ri no-mata Rj

Grafo derestricciones:

cbea (LSI-FIB-UPC)

R1

R2

R3

R4

Inteligencia Artificial

Curso 2011/2012

6 / 17

Satisfacción de restricciones

Backtracking Cronológico

4-reinas mediante backtracking cronológico

Notas

R1=2

R1=1

R2=1 NO
R2=2 NO
R2=3

R2=4

R3=1 NO
R3=2 NO
R3=3 NO
R3=4 NO

R3=1 NO
R3=2
NO
R3=3 NO
R3=4 NO

Backtracking a R2

R2=1 NO
R2=2 NO
R2=3 NO
R2=4

R3=1

R4=1 NO
R4=2 NO
R4=3 NO
R4=4 NOR4=1 NO
R4=2 NO
R4=3

Backtracking a R3

cbea (LSI-FIB-UPC)

Solucion (R1=2,R2=4,R3=1,R4=3)

Inteligencia Artificial

Satisfacción de restricciones

Curso 2011/2012

7 / 17

Propagación de restricciones

Propagación de restricciones

Notas

Un conjunto de restricciones puede inducir otras que estaban implícitas. La
propagación de restricciones es el proceso de hacerlas explícitas
X1

X1

{Rojo}{Axul, Rojo}

X2

X2

{Azul}

{Azul}

X3

X3

X4

X4
{Azul, Rojo, Verde}

{Azul, Verde}

{Rojo}

{Verde}

El papel de la PR es disminuir el espacio de búsqueda. Debemos realizar la
propagación:
1

preproceso (eliminar zonas del espacio donde no hay soluciones)

2

durante el proceso: podar el espacio a medida que la búsqueda
progresa (Forward Checking)

cbea (LSI-FIB-UPC)

Inteligencia Artificial...