**IAIC** Problemas de Satisfacción de Restricciones Definiciones y Métodos # Introducción En muchas ocasiones la resolución de problemas está sujeta a que las diversas unidades en las que se pueden descomponer verifiquen ciertos conjuntos de restricciones. Problemas tan cotidianos como fijar una cita con unos amigos, comprar un coche, o preparar una receta de cocina pueden depender de muchos aspectos interdependientes, e incluso conflictivos, sujetos a un conjunto de **restricciones** que deben ser satisfechas para poder encontrar una solución al problema planteado. Históricamente, la representación y resolución de **problemas de satisfacción de restricciones** (**CSP**, por sus siglas en inglés) ha generado una gran expectación entre expertos de muchas áreas debido a su potencial para la resolución de grandes problemas reales que caen, en muchas ocasiones, dentro de lo que se conocen como problemas **NP** (aquellos que presentan una complejidad computacional superior para su resolución). Los primeros trabajos relacionados con la programación de restricciones datan de los años 60 y 70 en el campo de la Inteligencia Artificial, aunque sus técnicas se han desarrollado desde mucho antes en diversas áreas de las Matemáticas y con aplicaciones a Economía, Ingeniería, Física, etc.  La idea de CSP es representar problemas mediante la declaración de restricciones sobre el área del problema (el espacio de posibles soluciones) y, consecuentemente, encontrar soluciones factibles que satisfagan todas las restricciones. A veces, se buscan soluciones que, además, optimicen algunos criterios determinados, en cuyo caso decimos que es un **Problema de Optimización de Restricciones** (**COP**, por sus siglas en inglés). La resolución de problemas con restricciones puede dividirse en dos ramas claramente diferenciadas, donde se aplican metodologías fundamentalmente distintas: 1. aquella que trata con problemas con **dominios finitos**, y 2. la que trata problemas sobre **dominios infinitos** o dominios más complejos. En esta ocasión nos centraremos principalmente en problemas con dominios finitos, que básicamente consisten en un conjunto finito de variables, un dominio de valores finito para cada variable y un conjunto de restricciones que acotan las posibles combinaciones de valores que estas variables pueden tomar en su dominio. !!!Tip:Ejemplo 1. ![](img\screen-shot-2013-05-20-at-3.57.27-pm.png width="60%" align="right") El **problema de coloración de mapas** es un problema clásico que se puede formular como un CSP. En este problema tenemos un conjunto de colores y un mapa dividido en regiones, y el objetivo es colorear cada región del mapa de manera que regiones adyacentes tengan distintos colores. Una forma de modelar este problema dentro del CSP sería asociando una variable a cada región del mapa, el dominio de cada variable sería el conjunto de posibles colores disponibles, y para cada par de regiones contiguas añadir una restricción sobre los valores de las variables correspondientes que impida asignarles el mismo valor (color). Como suele ser habitual, este mapa puede ser representado mediante un grafo donde los nodos representan las diversas regiones del mapa y cada par de regiones adyacentes están unidas por una arista. Veremos que esta representación en forma de grafo, que en este problema es natural, será usada como metodología general para dar una estructura a las restricciones de cualquier CSP. 2. El problema **SAT de la Lógica Proposicional es un CSP**: entre todas las posibles valoraciones de las variables de la fórmula, queremos saber si hay alguna que verifique la restricción expresada por la fórmula. !!!note En cierta forma, la idea de los CSP extiende el problema SAT de la Lógica Proposicional, permitiendo introducir restricciones más ricas (no únicamente las dadas por las conectivas lógicas) sobre un conjunto de variables que no tienen por qué ser únicamente binarias. # Definición Formal de CSP Vamos a presentar más formalmente los conceptos y objetivos básicos que son necesarios en los problemas de satisfacción de restricciones y que utilizaremos a lo largo de esta entrada. !!!Def:Definición (Problema de Satisfacción de Restricciones) Un **problema de satisfacción de restricciones** (**CSP**) es una terna $(X,D,C)$ donde: 1. $X$ es un conjunto de $n$ variables $\{x_1 ,...,x_n \}$. 2. $D =\langle D_1 ,...,D_n \rangle$ es un vector de dominios ($D_i$ es el dominio que contiene todos los posibles valores que puede tomar la variable $x_i$). 3. $C$ es un conjunto finito de restricciones. Cada restricción está definida sobre un conjunto de $k$ variables por medio de un predicado que restringe los valores que las variables pueden tomar simultáneamente. Una **asignación de variables**, $(x,a)$, es un par *variable-valor* que representa la asignación del valor $a$ a la variable $x$. Una asignación de un conjunto de variables es una tupla de pares ordenados, $((x_1 ,a_1 ),...,(x_i ,a_i ))$, donde cada par ordenado $(x_i,a_i)$ asigna el valor $a_i$ a la variable $x_i$. Una tupla se dice **localmente consistente** si satisface todas las restricciones formadas por variables de la tupla. Una **solución a un CSP** es una asignación de valores a todas las variables de forma que se satisfagan todas las restricciones. Es decir, una solución es una tupla consistente que contiene todas las variables del problema. Una **solución parcial** es una tupla consistente que contiene algunas de las variables del problema. Diremos que un **problema es consistente**, si existe al menos una solución. ![](img\slide_4.jpg width="50%") Habitualmente, el objetivo que se persigue se centra en una de las siguientes opciones: 1. Encontrar una solución, sin preferencia alguna. 2. Encontrar todas las soluciones. 3. Encontrar una solución *óptima* (es preciso dar alguna **función objetivo** definida en términos de las variables). Antes de entrar con más detalles vamos a resumir la notación que utilizaremos posteriormente: * **Variables**: Para representar las **variables** utilizaremos las últimas letras del alfabeto, por ejemplo $x,y,z$, así como esas mismas letras con un subíndice. * **Restricciones**: La **aridad** de una restricción es el número de variables que intervienen en dicha restricción (así, una **restricción unaria** es una restricción que involucra una sola variable; una **restricción binaria** es una restricción que involucra dos variables; una **restricción $k$-aria** es una restricción que involucra a $k$ variables). Una **restricción $k$-aria** entre las variables $\{x_1 ,...,x_k\}$ la denotaremos por $C_{i_1..i_k}$. De esta manera, una **restricción binaria** entre las variables $x_i$ y $x_j$ la denotaremos por $C_{ij}$. Cuando los índices de las variables en una restricción no son relevantes, lo denotaremos simplemente por $C$. !!!Tip:Ejemplo La restricción $C_1\equiv x_1 \leq 5$ es una restricción unaria sobre la variable $x$. La restricción $C_{34}\equiv x_4 - x_3 \neq 3$ es una restricción binaria. La restricción $C_{123}\equiv 2x_1 - x_2 + 4x_3 \leq 4$ es una restricción ternaria. !!!Def: Definición (Tuplas) Una tupla de una restricción $C_{i_1..i_k}$ es un elemento del producto cartesiano $D_{i_1} \times \dots\times D_{i_k}$. Una tupla que satisface la restricción $C_{i..k}$ se le llama **tupla permitida o válida**. Una tupla de una restricción $C_{i_1..i_k}$ se dice que es **soporte** para un valor $a \in D_j$ si la variable $x_j \in X_{C_{i_1..i_k} }$, es una tupla permitida y contiene a $(x_j,a)$. Verificar si una tupla dada es permitida o no por una restricción se llama **comprobación de la consistencia**. Una restricción puede definirse **extensionalmente** mediante un conjunto de tuplas válidas o no válidas (cuando sea posible) o también **intensionalmente** mediante un predicado entre las variables. !!!Tip:Ejemplo Consideremos una restricción entre 4 variables $x_1 ,x_2 ,x_3 ,x_4$, todas ellas con dominios el conjunto $\{1,2\}$, donde la suma entre las variables $x_1$ y $x_2$ es menor o igual que la suma entre $x_3$ y $x_4$. Esta restricción puede representarse intensionalmente mediante la expresión $x_1 + x_2 \leq x_3 + x_4$. Además, esta restricción también puede representarse extensionalmente mediante el conjunto de tuplas permitidas: $$\{(1,1,1,1), (1,1,1,2), (1,1,2,1), (1,1,2,2), (2,1,2,2), (1,2,2,2),$$ $$(1,2,1,2), (1,2,2,1),(2,1,1,2), (2,1,2,1), (2,2,2,2)\}$$ o mediante el conjunto de tuplas no permitidas: $$\{(1,2,1,1), (2,1,1,1), (2,2,1,1), (2,2,1,2), (2,2,2,1)\}$$ Como es habitual con los sistemas de representación, la resolución de un CSP consta de dos fases, que son: 1. **Modelar/Representar el problema como un problema de satisfacción de restricciones**. Para ello, y siguiendo una metodología similar al ejemplo anterior, el problema se expresa mediante un conjunto de variables, dominios en los que toman los posibles valores, y restricciones sobre estas variables. 2. **Procesar las restricciones**. Una vez formulado el problema como un CSP, hay esencialmente dos aproximaciones para procesar las restricciones: - **Técnicas de consistencia**: basadas en la eliminación de valores inconsistentes de los dominios de las variables (es decir, que no verifican las restricciones impuestas). A veces se pueden aplicar aquí técnicas derivadas de la [Lógica Proposicional](http://www.cs.us.es/~fsancho/?e=120) (o de primer orden). - **Algoritmos de búsqueda**: se basan en la exploración sistemática del espacio de soluciones hasta encontrar una solución (o probar que no existe tal solución en caso contrario) que verifica todas las restricciones del problema. Lo más normal es que se combinen ambas aproximaciones, ya que las técnicas de consistencia permiten deducir información del problema y reducir el espacio de soluciones para poder explorarlo usando algoritmos de búsqueda más o menos tradicionales. ## Algunos ejemplos de Modelización !!!Tip: Problema Criptoaritmético Consideremos el conocido **problema criptoaritmético ’send+more=money’**. Este problema puede ser declarado como: asignar a cada letra $\{s, e, n, d, m, o, r, y\}$ un dígito diferente del conjunto $\{0,...,9\}$ de forma que se satisfaga la expresión $send+more=money$. ![](img\sendmoremoney.jpg width="10%") **Primera Representación:** La manera más directa de modelar este problema es asignando una variable a cada una de las letras (que vendrán representadas por las mismas letras), todas ellas tomando valores en el dominio $\{0,...,9\}$ y con las restricciones de: 1. Todas las variables toman valores distintos, y 2. Se satisface $send+more=money$. De esta forma, podemos escribir las restricciones como: $$10^3 (s+m)+10^2 (e+o)+10(n+r)+d+e = 10^4 m + 10^3 o + 10^2 n + 10e + y$$ $$s\neq e,\ s\neq n,\ ...,\ r\neq y$$ Esta representación del problema es correcta, pero no es muy útil, ya que la primera de las restricciones exige manipular todas las variables simultáneamente y no facilita recorrer el espacio combinatorio de valores de una forma cómoda (ten en cuenta siempre que, finalmente, vamos a recorrer este espacio de combinaciones de valores como un espacio de estados, como veremos en el siguiente tema). Por lo que, al no disponer de restricciones locales entre las variables, no podemos podar el espacio de búsqueda para agilizar la búsqueda de soluciones. **Segunda Representación:** Vamos a dar otro modelado similar, que puede ser más eficiente a la hora de resolver el problema de manera efectiva, y que consiste en descomponer esta restricción global en restricciones más pequeñas haciendo uso de las relaciones que se producen entre los dígitos que ocupan la misma posición en una suma. Para ello, introducimos los **dígitos de acarreo** para descomponer la ecuación anterior en una colección de pequeñas restricciones. ![](img\acarreo.png align="center") Tal y como está planteado el problema, $m$ debe de tomar el valor $1$ (ya que es el acarreo de 2 cifras que como mucho pueden sumar $18$, más un posible acarreo previo de una unidad, lo que limita el resultado a $19$) y por lo tanto $s$ solamente puede tomar valores de $\{1,...,9\}$ (si $s=0$ entonces no podría haber acarreo). Además de las variables del modelo anterior, el nuevo modelo incluye tres variables adicionales, $c_1$, $c_2$, $c_3$ que sirven como dígitos de acarreo. Aunque introducimos nuevas variables, por lo que el espacio de búsqueda se amplía, estas nos permitirán simplificar las restricciones y facilitar su exploración de forma considerable. En consecuencia, el dominio de $s$ es $\{1,...,9\}$, el dominio de $m$ es $\{1\}$, el dominio de los dígitos de acarreo es $\{0,1\}$, y el dominio del resto de variables es $\{0,...,9\}$. Con la ayuda de los dígitos de acarreo la restricción de la ecuación anterior puede descomponerse en varias restricciones más pequeñas (junto con las restricciones que indican que todas las variables originales son distintas entre sí): $$e + d = y + 10c_1$$ $$c_1 + n + r = e + 10c_2$$ $$c_2 + e + o = n + 10c_3$$ $$c_3 + s + m = 10m + o$$ Esta nueva representación presenta la ventaja de que las restricciones más pequeñas pueden comprobarse durante la búsqueda de una forma más sencilla y local, permitiendo podar más inconsistencias y, consecuentemente, reduciendo el tamaño del espacio de búsqueda efectivo. !!!Tip:Ejemplo Vamos a dar como ejemplo diversas representaciones de un mismo problema usando la representación CSP. Trabajaremos sobre el **problema de las N reinas**, que plantea cómo disponer en un tablero de ajedrez de tamaño $N\times N$, $N$ reinas de forma que no haya amenazas entre ningún par de ellas (recordemos que una reina amenaza a toda la fila, columna y diagonales de la casilla en la que se sitúa).  Observa las diferencias que se producen en la complejidad de las representaciones, tanto por el espacio de combinaciones en las soluciones como por las restricciones. **Primera Representación:** 1. $X=\{R_1,\dots,R_N\}=\{R_i :\ 1 \leq i \leq N\}$ 2. $D=\{(x,y):\ 1\leq x,y \leq N\}$, donde $R_i=(x_i,y_i)$ 3. Las restricciones: - No hay amenaza horizontal: $x_i \neq x_j$, para todo $i\neq j$. - No hay amenaza vertical: $y_i \neq y_j$, para todo $i\neq j$. - No hay amenaza en la diagonal principal: $x_i - x_j \neq y_i - y_j$, para todo $i \neq j$. - No hay amenaza en la diagonal secundaria: $x_i - x_j \neq y_j - y_i$, para todo $i \neq j$. (Las dos diagonales se pueden tratar conjuntamente con: $|x_i - x_j| \neq |y_i - y_j|$, para todo $i \neq j$) En esta representación el dominio es finito y hace uso de restricciones binarias de obligación. Para $N=8$ hay $64^8$ posibles asignaciones y $126$ restricciones. **Segunda Representación:** 1. $X=\{R_{i,j}:\ 1\leq x,y \leq N\}$ (una por cada casilla). 2. $D=\{0,1\}$ 3. Las restricciones: - $\displaystyle{\sum_i R_{i,j} \leq 1}$, para todo $1\leq j\leq N$. - $\displaystyle{\sum_j R_{i,j} \leq 1}$, para todo $1\leq i\leq N$. - $\displaystyle{\sum_{(i,j)\in D} R_{i,j} \leq 1}$, para toda $D$ diagonal. En esta representación el dominio es finito y hace uso de restricciones de varias aridades. Para $N=8$ hay $64^2$ posibles asignaciones y unas $300$ restricciones. **Tercera Representación:** Similar a la anterior, pero por medio de predicados lógicos: 1. $X=\{R_{i,j}:\ 1\leq x,y \leq N\}$ (una por cada casilla). 2. $D=\{0,1\}$ 3. Las restricciones: - $(R_{i,j} \rightarrow \neg R_{i,j'})$, para todo $j' \neq j$. - $(R_{i,j} \rightarrow \neg R_{i',j})$, para todo $i' \neq i$. - $(R_{i,j} \rightarrow \neg R_{i+k,j+k})$, para todo $1\leq i+k, j+k \leq N$. - $(R_{i,j} \rightarrow \neg R_{i+k,j-k})$, para todo $1\leq i+k, j-k \leq N$. **Cuarta Representación:** Haciendo uso de conocimiento implícito del problema (que va a haber una, y solo una, reina en cada columna): 1. $X=\{R_i :\ 1\leq i \leq N\}$ 2. $D=\{1,\dots,N\}$ 3. Las restricciones: - $R_i \neq R_j$, para todo $i\neq j$. - $|R_i - R_j| \neq |i - j|$, para todo $i\neq j$. En esta representación el dominio es finito y hace uso de restricciones binarias. Para $N=8$ hay $8^8$ posibles asignaciones y unas $80$ restricciones. # Métodos de Resolución El método completo de resolución de CSPs más sencillo es el de **fuerza bruta básica**: generamos primero todas las posibles asignaciones completas (como producto cartesiano de los dominios de todas las variables) y, posteriormente, recorremos este conjunto de asignaciones para verificar si hay alguna que verifique todas las restricciones del problema. ```Julia Fuerza-Bruta As = D₁ × … × Dₙ Para cada A ∈ As: Si A es consistente Devolver A Parar Devolver false ``` El inconveniente evidente de este método es que puede requerir una cantidad excesiva de memoria inicial para almacenar el conjunto completo de las asignaciones, y una cantidad excesiva de tiempo para encontrar una solución en el peor de los casos. ## Basados en búsquedas con Backtracking Podemos hacer una mejora directa que, al menos, eliminaría el problema de la memoria, y que consiste en verificar si una asignación completa es solución tras crearla, y no almacenar en memoria el resto de asignaciones (ya que no hay necesidad de volver a ellas posteriormente en caso de que no sea válida). De esta forma, eliminamos el inconveniente del uso de memoria, aunque seguimos necesitando un tiempo potencialmente enorme en el peor de los casos. Sin embargo, si el método no reutiliza la información de posibles soluciones (asignaciones) anteriores para acelerar o decidir nada sobre asignaciones futuras, es conveniente no almacenar en memoria aquello que no se va a utilizar, y si es posible generar las asignaciones en el momento de usarlas, no tiene sentido generarlas por adelantado. Por lo que es una mejora que sí debería tenerse en cuenta. Además, con poco esfuerzo podemos tener una mejora considerable si tenemos en cuenta que la *inconsistencia* de una asignación no depende del valor de todas las variables, sino de la relación existente entre las que intervienen en alguna restricción de baja aridad. Esto nos indica que si, por ejemplo, al fijar los valores de 2 variables ya no se satisface una de las restricciones, las posibles ampliaciones de esa asignación parcial no serán soluciones del CSP, por lo que no habrá que generar inútilmente muchas asignaciones que no sirven para nada. Esta idea nos permite idear un algoritmo de búsqueda de soluciones mucho más eficiente que el anterior, trabajando con asignaciones parciales que se van extendiendo solo en caso de **NO** ser inconsistentes con el problema (no quiere decir que sean consistentes, podrían ser todavía no evaluables por falta de información en ciertas variables). Como es posible que en un momento determinado nos encontremos con una asignación parcial que ya es inconsistente, basta tener un poco de control acerca de cómo reasignar los valores conflictivos para eliminar grandes espacios de asignaciones que no serán útiles y que no tenemos que explorar. !!!note Este procedimiento lo veremos varias veces a lo largo de otras aproximaciones de Inteligencia Artificial, y se denomina **poda**, por la similitud con el proceso que se hace en árboles.  A continuación presentamos el pseudocódigo de la búsqueda de soluciones por **Backtracking** (**BT**), que sigue fielmente esta idea (más adelante podremos verificar que en este procedimiento es simplemente una búsqueda en profundidad con backtracking sobre el árbol que usa las asignaciones parciales como nodos). La entrada del algoritmo es una asignación parcial $A$ y una lista de variables sin asignar $U$. La salida es un `fallo/false` o una asignación completa. Notamos por $D(x)$ al dominio de la variable $x$. El algoritmo recibe inicialmente la asignación vacía, $A=\emptyset$ y la lista de todas las variables del CSP, $U=X$. ```Julia BT(A, U) Si A es completa Devolver A Seleccionar una variable x de U U ← U − {x} Para cada v ∈ D(x): Si {x = v} es consistente con A res ← BT(A ∪ {x = v}, U) Si res ≠ false Devolver res Devolver false ``` La primera mejora del rendimiento del CSP que consideraremos es el **filtrado**, que comprueba si podemos podar los dominios de las variables no asignadas con antelación eliminando valores que sabemos que darán lugar a backtracking. Un método ingenuo de filtrado es la **comprobación anticipada** (**Forward Checking**), que cada vez que se asigna un valor a una variable $x$, poda los dominios de las variables no asignadas que comparten una restricción con $x$ y que violarían la restricción si se asignaran. Cada vez que se asigna una nueva variable, podemos ejecutar la comprobación anticipada y podar los dominios de las variables no asignadas que son adyacentes a ella en el grafo de restricciones (es decir, que comparten alguna restricción con ella). El siguiente pseudocódigo representa una búsqueda de soluciones por **backtracking con comprobación hacia delante** (**BT+FC**). La entrada del algoritmo es una asignación parcial $A$, una lista de variables sin asignar $U$, y los dominios actuales de las variables, $D$. La salida es un *fallo* o una asignación completa. El algoritmo recibe inicialmente la asignación vacía, $A=\emptyset$, la lista de todas las variables del CSP, $U=X$, y el conjunto de dominios originales. Notaremos $(y ↔ x)$ cuando las variables $x$ e $y$ comparten una restricción. ```Julia BT+FC(A, U, D) Si A es completa Devolver A Seleccionar una variable x de U U ← U − {x} Para cada v ∈ D(x): Si A ∪ {x = v} es consistente A ← A ∪ {x = v} D' ← D (guardamos el dominio actual) Para cada y ∈ U con (y ↔ x): Elimina valores de y de D'(y) que son inconsistentes con A Si para todo y ∈ U tal que (y ↔ x) se tiene D'(y) ≠ ∅ res ← BT+FC(A, U, D') Si res ≠ false Devolver res A ← A − {x = v} Devolver false ``` La idea de comprobación anticipada puede generalizarse en el principio de **consistencia de arco** que veremos más adelante. Hemos comentado previamente que, al resolver un CSP, fijamos un cierto orden para las variables y los valores implicados. En la práctica, suele ser mucho más eficaz calcular la siguiente variable y el valor correspondiente "sobre la marcha" con dos principios generales: - **Valores Mínimos Restantes** (**MRV**): Al seleccionar qué variable asignar a continuación, utilizando una política MRV se elige la variable no asignada que tenga el menor número de valores restantes válidos (la variable más restringida). Esto es intuitivo en el sentido de que la variable más restringida tiene más probabilidades de quedarse sin valores posibles y dar lugar a un retroceso si se deja sin asignar, por lo que es mejor asignarle un valor cuanto antes. - **Valor menos restrictivo** (**LCV**): Del mismo modo, al seleccionar qué valor asignar a continuación, una buena política a aplicar es seleccionar el valor que elimine el menor número de valores de los dominios de los valores sin asignar restantes. En particular, esto requiere un cálculo adicional (por ejemplo, volver a ejecutar la comprobación anticipada, o consistencia de arco u otros métodos de filtrado, para cada valor con el fin de encontrar el LCV), pero puede aumentar la velocidad en función del uso. Hay una heurística adicional que podemos aplicar además de la ordenación de las variables, que sería la basa en ordenar el recorrido que hacemos sobre sus valores (ordenación del dominio). Las heurísticas para la ordenación de valores no han sido tan estudiadas como las de variables. La idea básica que hay detrás de las heurísticas de ordenación de valores es seleccionar el valor de la variable actual que más probabilidad tenga de llevarnos a una solución. La mayoría de las heurísticas propuestas tratan de seleccionar el valor menos restringido de la variable actual, es decir, el valor que reduce en menor medida el número de valores útiles para las futuras variables. Una de las heurísticas de ordenación de valores más conocidas es la heurística **min-conflicts**, que ordena los valores de acuerdo a los conflictos en los que estos están involucrados con las variables no instanciadas (sin valor asignado). Esta heurística asocia a cada valor de la variable actual, el número total de valores en los dominios de las futuras variables adyacentes que son incompatibles con él. El valor seleccionado es el asociado a la suma más baja. ## Propagación de Restricciones Los algoritmos anteriores se basan en recorrer/generar, de forma más o menos eficiente, las asignaciones posibles e ir comprobando cuáles verifican las restricciones impuestas por el problema. Pero otra opción sería cambiar el punto de vista y considerar el problema primero desde el ángulo de las propias restricciones. Los métodos más famosos que siguen esta aproximación se engloban bajo lo que se denomina **Propagación de Restricciones**. El siguiente pseudocódigo corresponde al algoritmo de **Consistencia de Arcos** (**AC3**, porque fue la tercera versión del inventor, Mackworth, en 1977), la forma más básica de propagación de restricciones. La idea básica del algoritmo es comprobar que todas las relaciones entre pares de variables que comparten restricción (lo que se llama un *arco*) son consistentes. Si no lo son, elimina los valores del dominio de la variable que hacen que el arco sea inconsistente, e inserta en la cola los arcos que se ven afectados por ese cambio en los valores del dominio. ```Julia AC3 Q = todos los arcos de restricciones Mientras Q no vacío Q ← Q - {(x ↔ y)} (el primer arco de Q) Si Eliminar-Valores-Inconsistentes(x,y) Para cada z ≠ y con (z ↔ x): Q ← Q ∪ {(z ↔ x)} (si no estaba ya) Eliminar-Valores-Inconsistentes(x, y) ; Procedimiento auxiliar Para cada x ∈ D(x): Si no existe v ∈ D(y) tal que x = w, y = v es consistente con la restricción entre x e y D(x) ← D(x) − {w} Si se han eliminado valores Devolver Si Si no Devolver No ``` ## Otros métodos La búsqueda backtracking no es el único algoritmo que existe para resolver CSPs. Otro algoritmo muy utilizado es la **búsqueda local**, cuya idea es infantilmente simple pero notablemente útil. La búsqueda local funciona por mejora iterativa: se empieza con alguna asignación aleatoria a valores y luego se selecciona iterativamente una variable aleatoria en conflicto y se reasigna su valor a la que viole menos restricciones hasta que no existan más violaciones de restricciones (siguiendo una política similar a la que vimos como **min-conflicts**). De hecho, la búsqueda local parece ejecutarse en tiempo casi constante y tener una alta probabilidad de éxito no solo para algunos problemas concretos sino también para cualquier CSP generado aleatoriamente. Sin embargo, a pesar de estas ventajas, la búsqueda local es incompleta y subóptima, por lo que no converge necesariamente a una solución óptima. Además, hay una relación crítica (entre el número de restricciones y el número de variables) alrededor de la cual el uso de la búsqueda local se vuelve extremadamente costoso, lo que quiere decir que cerca de ese valor crítico la búsqueda local precisa de muchísimas iteraciones para converger. Más adelante veremos algunas variantes de búsqueda local que funcionan bastante bien en la mayoría de los casos, como el **Templado Simulado**. # Problemas de Optimización de Restricciones (COP) Los problemas de la vida real suelen incluir tanto restricciones **duras** como **blandas**. Por ejemplo, en los problemas de asignación de horarios, mientras que una restricción de recursos como *un profesor solo puede dar una clase a la vez* debe satisfacerse obligatoriamente (es dura), la de que un profesor deba tener su *horario concentrado en solo dos días* es solo una preferencia, no es esencial (es blanda). Cuando formalizamos problemas que tienen restricciones duras y blandas, obtenemos una red de restricciones aumentada con una **función de coste global** (también llamada **función objetivo**) sobre todas las variables. Los **problemas de optimización de restricciones** (**COP**) encuentran una asignación completa de valores a todas las variables, satisfaciendo las restricciones duras y optimizando la función de coste global. Normalmente, la forma en que intervienen las restricciones blandas es añadiendo una penalización a la función de coste cuando no son satisfechas, alejándola así de su valor óptimo, y haciendo así que sea preferible satisfacerlas. Además, este mecanismo nos permitiría dar *prioridad* a las restricciones blandas modificando el valor relativo de las penalizaciones de cada una. Numerosos problemas industriales pueden modelarse como tareas de optimización de restricciones, en particular, las tareas de programación y diseño implican restricciones duras y blandas. Por ejemplo: !!!Tip:Ejemplo: Mantenimiento de unidades de generación de energía Una central eléctrica típica consta de una o dos docenas de unidades de generación de energía que pueden programarse individualmente para su mantenimiento preventivo. Se conoce de antemano tanto el tiempo necesario para el mantenimiento de cada unidad como una estimación razonablemente precisa de la demanda de energía de la central. El objetivo general de la programación del mantenimiento es determinar la duración y la secuencia de las paradas de las unidades individuales de generación de energía en un periodo de tiempo determinado, minimizando los costes de explotación y mantenimiento durante el periodo de planificación en cuestión, sujeto a diversas restricciones. La programación está influida por muchos factores, como la duración del periodo de mantenimiento de cada unidad, las restricciones sobre el momento en que se puede realizar el mantenimiento, la demanda de energía prevista para toda la planta y el coste variable del mantenimiento y del combustible en diferentes momentos del periodo de planificación. !!!Tip:Ejemplo: Problema de la subasta combinatoria En este tipo de subasta, los licitadores pueden hacer una oferta por varios artículos. Esto plantea al subastador el problema de determinar la selección óptima de ofertas para maximizar los ingresos. Más formalmente, dado un conjunto de artículos $S = \{a_1,\dots ,a_n\}$ y un conjunto de pujas $B = \{b_1,\dots, b_m\}$, donde cada puja es $b_i = (S_i, r_i)$, con $Si\subseteq S$ un conjunto de artículos y $r_i$ es el coste a pagar por la puja $b_i$, la tarea consiste en encontrar un subconjunto de pujas $B'\subseteq B$ tal que dos pujas cualesquiera de $B'$ no compartan un artículo y se maximice $C(B')=\displaystyle{\sum_{b_i\in B'}} r_i$. Una importante fuente de problemas de optimización se encuentra en el área de **planificación** en IA. En el marco determinista, la tarea consiste en encontrar una secuencia corta de acciones (un plan) que logre un conjunto de objetivos a partir de un estado inicial dado. Los problemas de planificación pueden formularse como tareas de satisfacción de restricciones asumiendo un plan de longitud fija. La planificación puede formularse alternativamente como tareas de optimización de restricciones, cuando la función de coste global que debe optimizarse es el número de acciones (o más generalmente, el coste) del plan. En última instancia, cada tarea de satisfacción de restricciones puede verse como un problema de optimización de restricciones. Cuando no se pueden satisfacer todas las restricciones, es posible que se quiera encontrar una solución que maximice el número de restricciones satisfechas. Este problema se conoce como problema **Max-CSP**, y la versión para **SAT** se llama **Max-SAT**. A las restricciones también se les puede asignar pesos de importancia, en cuyo caso la tarea es minimizar la suma ponderada de las restricciones violadas. # Tendencias Las tendencias actuales en CSP pasan por desarrollar técnicas para resolver determinados problemas de satisfacción de restricciones basándose principalmente en la topología de las redes de restricciones. Entre estas tendencias podemos destacar las siguientes: 1. Técnicas para resolver problemas con muchas restricciones. 2. Técnicas para resolver problemas con muchas variables y restricciones, donde puede resultar conveniente la paralelización o distribución del problema de forma que éste se pueda dividir en un conjunto de subproblemas más fáciles de manejar. 3. Técnicas combinadas de satisfacción de restricciones con métodos de investigación operativa con el fin de obtener las ventajas de ambas propuestas. 4. Técnicas de computación evolutiva, donde los [algoritmos genéticos](http://www.cs.us.es/~fsancho/?e=65) al igual que las [redes neuronales](http://www.cs.us.es/~fsancho/?e=72), se han ido ganando poco a poco el reconocimiento de los investigadores como técnicas efectivas en problemas de gran complejidad. Se distinguen por utilizar estrategias distintas a la mayor parte de las técnicas de búsqueda clásicas y por usar operadores probabilísticos más robustos que los operadores determinísticos. 5. Otros temas de interés son heurísticas inspiradas biológicamente, tales como [colonias de hormigas](http://www.cs.us.es/~fsancho/?e=71), [optimización por enjambres de partículas](http://www.cs.us.es/~fsancho/?e=70), algoritmos meméticos, algoritmos culturales, búsqueda dispersa, etc.