Problemas de satisfacción de restricciones en Inteligencia Artificial
Problemas de satisfacción de restricciones (PSRs)
Componentes del estado = grafo de restricciones:
Variables
Dominios (valores posibles para las variables)
Restricciones (binarias) entre las variables
Objetivo: encontrar un estado (una asignación completa de valores a las variables) que satisface las restricciones.
2
2
Problemas de satisfacción de restricciones (PSRs)
Ejemplos:
colorear mapas
crucigramas
n-reinas
asignación/distribución/ubicación de recursos:
distribución de tareas de fabricación
ubicación de gasolineras
ubicación de antenas de telefonía
3
3
4
Representación
Problema: colorear mapa
Ejemplo de estado:
Variables (n) = etiquetas de nodos
Dominios = contenido de nodos
Restricciones = arcos dirigidos y etiquetados entre nodos
4
5
Representación
A cada paso hay una asignación de variable.
Las soluciones deben ser asignaciones completas y por lo tanto, en el árbol de búsqueda, aparecen a profundidad n.
El árbol se extiende sólo a profundidad n.
Los algoritmos de búsqueda primero en profundidad son populares para PSRs.
El camino que alcanza una solución es irrelevante.
La clase más simple de PSR implica variables discretas y dominios finitos: problemas de coloreo de mapas, de n-reinas…
5
6
Dominios finitos
Si el tamaño máximo del dominio de cualquier variable es d, entonces el número de posibles asignaciones completas es O(dn), exponencial en el número de variables.
Los PSRs con dominio finito incluyen a los PSRs booleanos, cuyas variables pueden ser verdaderas o falsas.
En el caso peor, no se pueden resolver los PSRs con dominios finitos en menos de un tiempo exponencial.
Evidentemente, los algoritmos para PSR resuelven problemas órdenes de magnitud más grandes que los resolubles con algoritmos de búsqueda no informada.
6
7
Dominios infinitos
Las variables discretas pueden tener dominios infinitos (p.e., el conjunto de números enteros o de cadenas).
Con dominios infinitos, no es posible describir restricciones enumerando todas las combinaciones permitidas de valores.
Se debe usar un lenguaje de restricción:
Comienzo-Trabajo1 + 5 = Comienzo-Trabajo3
Existen algoritmos para restricciones lineales sobre variables enteras.
7
8
Dominios infinitos
No existe un algoritmo general para restricciones no lineales sobre variables enteras.
En algunos casos, se pueden reducir los problemas de dominio infinito a dominio finito simplemente acotando los valores de todas las variables, p.e.:
fijando límites temporales para el comienzo de los trabajos.
8
9
Dominios continuos
Los PSRs con dominios continuos son muy comunes en el mundo real.
La categoría más conocida son los problemas de programación lineal:
las restricciones deben ser desigualdades lineales que forman una región convexa.
Los problemas de programación lineal pueden resolverse en tiempo polinomial en el número de variables.
9
Algoritmos
Basados en búsqueda
complejidad:
tiempo: O(exp(n))
espacio: O(n)
Basados en programación dinámica
complejidad:
tiempo: O(exp(w*+1))
espacio: O(exp(w*))
Donde n es el número de variables y w* es la anchura inducida del grafo de restricciones dado un orden.
10
10
11
Algoritmos basados en búsqueda
Formulación incremental, como en un problema de búsqueda estándar:
Estado inicial: la asignación vacía { }, en que todas las n variables no están asignadas.
Función de sucesor: asignación de un valor d a cualquier variable no asignada, a condición de que no suponga conflicto con variables ya asignadas.
Test objetivo: la asignación actual es completa.
Costo del camino: un costo constante (p.e., 1) para cada paso.
11
12
Algoritmos basados en búsqueda
Formulación completa de estados:
Cada estado es una asignación completa que satisface o no las restricciones.
Los métodos de búsqueda local trabajan bien para esta formulación.
12
13
Algoritmos basados en búsqueda
Búsqueda heurística
Búsqueda en profundidad con vuelta atrás cronológica
Propagación de restricciones
Antes de la búsqueda
Durante la búsqueda
13
14
Restricciones
El tipo más simple es la restricción unaria, que restringe los valores de una sola variable.
Una restricción binaria relaciona dos variables.
Las restricciones de orden alto implican tres o más variables. Un ejemplo son los puzzles cripto-aritméticos.
14
15
Puzzles cripto-aritméticos
Variables: F T U W R O X1 X2 X3
Dominio: {0,1,2,3,4,5,6,7,8,9}
Restricciones:
TodasDif (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
15
Búsqueda con vuelta atrás para PSR
Si los PSRs se formulan como problemas de búsqueda, cualquiera de los algoritmos de búsqueda vistos anteriormente los pueden resolver.
Estado inicial: la asignación vacía { }, en que todas las n variables no están asignadas.
Función de sucesor: asignación de un valor d a cualquier variable no asignada, a condición de que no suponga conflicto con variables ya asignadas.
Si aplicamos la búsqueda primero en anchura, notamos algo terrible:
El factor de ramificación en el nivel superior es de nd.
16
Página siguiente |