SATISFACCION DE RESTRICCIONES (Constraint Satisfaction)

SATISFACCION DE RESTRICCIONES

(Constraint Satisfaction)

Problemas de Satisfacción de Restricciones (PSR) /  Constraint Satisfaction Problems (CSP)

Definición: Problemas donde la asignación de ciertos valores a una variable, restringen los posibles valores de otras variables. (Variables con restricciones sobre ellas).

Objetivo: Encontrar un estado que satisface el conjunto de restricciones entre las variables del problema.

Estado: Asignación de valores a un conjunto de variables.

*(Asignación: Dar un valor a una variable.  Asignación Parcial: sólo algunas variables. Asignación Completa: todas las variables)

1. Componentes del estado (Modelización):

• Variables (X): Conjunto de variables finitas.
• Dominios (D): que contiene los posibles valores que pueden asignarse a la variable Xi. (Finitos, Infinitos, Continuos)
• Restricciones (C): Conjunto restricciones finitas. Todas las restricciones definidas en un CSP son conjuntivas, de manera que una solución debe de satisfacer a todas ellas.

Tipos de restricciones:

• Unarias: Reducen el dominio de una variable.
• Binarias: Se aplica a pares de variables.  El valor asignado de una variable reduce el dominio de la otra variable.
• Múltiples: Se aplica a más de dos variables.  El valor asignado a una variable reduce el dominio del resto de variables.

Ejemplo: [pic 1]

Problema:  Usando tres colores (rojo, verde, azul) colorear el mapa de Australia.

Variables: Australia del Oeste (AO), Territorio del Norte (TN), Australia del Sur (AS), Queensland (Q), Nueva Gales del Sur (NGS), Victoria (V), Tasmania (T). (Conjunto de variables finitas).

Dominio: (rojo, verde, azul). El dominio de cada variable es el conjunto de colores finitos.

Restricciones: Se requiere que estados vecinos tengan diferente color.  (Conjunto de restricciones Binarias)

Variables (etiquetas nodos):  [pic 2]

X: { AO, TN, AS, Q, NGS, V, T }

Domino (contenido nodos):

D: { rojo, verde, azul }

Restricciones (arcos dirigidos):

C: { AO≠TN, AO≠AS, TN≠AS, TN≠Q, AS≠Q, AS≠NGS, AS≠V, Q≠NGS, NGS≠V }

Solución:[pic 3]

Hay muchas soluciones posibles, pero una solución es:

AO = rojo

TN = verde

Q = rojo

NGS = verde

V = rojo

AS = azul

T = rojo

1. Solución: Conjunto de valores de las variables que satisfacen una serie de restricciones.

1. Tipos de búsqueda:

• Una solución (cualquiera).
• Todas las soluciones. (NP-completo)
• La solución óptima. (NP-hard)

1. Técnicas de Búsqueda

1.  Búsqueda Sistemática:

Métodos de búsqueda que se centran en explorar el espacio de estados del problema.

• Pueden ser completos (exploran todo el espacio de estados), o incompletos (exploran una parte del espacio de estados).
• Los métodos completos garantizan encontrar una solución, si existe, o demuestran que el problema no es resoluble.
• Desventaja de estos algoritmos es que son muy costosos. Ejemplos: Generar y Testear (GT), Backtracking Cronológico (BT).

1. Técnicas de Inferencia (etapa de pre proceso):

Su objetivo es deducir nuevas restricciones, derivadas de las explícitamente conocidas sobre el problema.

...