Problemas de Satisfacción de

Restricciones (CSP)

Autor. Leopoldo Capa

Definición del problema de satisfacción de restricciones (CSP).

Áreas de aplicación.

Especificación de un problema CSP: variables, dominios y restricciones.

Tipología de restricciones (discretas y continuas, fuertes y débiles, restricciones lineales, disyuntivas, etc.).

Un Problema de Satisfacción de Restricciones(CSP) se puede representar como:

Un Conjunto de Variables: X={x1, x2, ..., xn} Dominios de Interpretación (D = <D1,…,Dn> )para las

variables: xi Di∈ Un Conjunto de Restricciones entre las variables:

C ={c1, c2, ..., cm}

Consistencia del problema (existe solución). Obtener una o todas las soluciones del problema. Obtener los dominios mínimos. La solución que optimiza una función objetivo o multi-objetivo.

Dado un CSP (X, Di, C),

Una instanciación(o asignación) de las variables X es una asignación de valores a las variables en sus dominios:

x1=v1, x2=v2, ..., xn=vn/ vi D∈

Una solución del CSP es una instanciación consistente de las variables, de forma que se satisfacen todas las restricciones del problema.

Un valor v es un valor consistente(o posible) para xi si existe una solución del CSP en la cual participa la asignación xi=v.

Un CSP es consistente si tiene al menos una solución.

Un CSP discreto es aquel en el que todas las variables son

discretas, es decir, toman valores en dominios discretos. Un CSP continuo es un CSP en el que todas las variables son

continuas, es decir, tienen dominios continuos. Un CSP mixto consta de variables continuas y discretas. Un CSP binario es aquel en el que todas las restricciones tienen

a los sumo dos variables respectivamente. Un CSP no binario o n-ario es aquel en el que las restricciones tienen

más de dos variables.

Discretas: las variables participantes están acotadas en dominios discretos.

Continuas: las variables participantes están acotadas en dominios continuos.

Binarias: son restricciones en las que sólo participan dos variables.

N-arias: son restricciones en las que participan Nvariables (N>2). Fuertes (hard): son restricciones cuya satisfabilidad e

imprescindible. Débiles (soft): son restricciones cuya satisfabilidad no es

imprescindible. Difusas (fuzzy): son restricciones definidas sobre niveles de

preferencia. Disyuntivas: son restricciones compuestas por un conjunto

disjunto de restricciones.