**IAIC 2024-25** Problemas de Satisfacción de Restricciones Definiciones y Métodos En muchas ocasiones, la resolución de problemas está sujeta a que las diversas unidades en las que éstos 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, sujetos a un conjunto de **restricciones** que deben ser satisfechas (y que pueden ser conflictivos) para poder encontrar una solución al problema planteado. Cuando estas unidades se pueden representar con variables booleanas, las Lógicas presentadas en el capítulo anterior ofrecen algunas herramientas tanto para su formalización como para su resolución. Pero también hemos visto las limitaciones y retos algorítmicos (de complejidad) que plantean. !!!side:1 Recordemos que son aquellos que presentan una complejidad computacional superior para su resolución. 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** $^1$. 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 las técnicas que se usan se han venido desarrollando desde mucho antes en diversas áreas de las Matemáticas y con aplicaciones a Economía, Ingeniería, Física, Biología, etc.  La idea central para resolver los CSP no es muy diferente de la presentada para el caso booleano: representar el problema mediante el conjunto de variables que representan el área del problema (el conjunto de todas las combinaciones posibles formarían el espacio de posibles soluciones) y buscar soluciones factibles que satisfagan todas las restricciones (en el caso booleano, las restricciones vienen dadas por las fórmulas que queremos que sean simultáneamente satisfactibles). 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 este tema nos centraremos principalmente en problemas con dominios finitos, que básicamente consisten en un conjunto finito de variables, un dominio finito de valores para cada variable, y un conjunto finito de restricciones que acotan las posibles combinaciones de valores que estas variables pueden tomar en su dominio. !!!ejemplo:Ejemplos 1. El problema **SAT de la Lógica Proposicional** se puede modelar como un CSP. Por ejemplo, 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 LP (o conjunto de fórmulas). Además, el número de variables que intervienen es finito, el dominio de estas variables es finito ($0/1$), y el número de restricciones viene asociado por las fórmulas del conjunto que queremos verificar si es satisfactible. 1. El problema de la **deducción** o **inferencia** es también un CSP, ya que vimos que se reduce de forma sencilla al problema SAT. 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 finito. En este problema tenemos un mapa dividido en regiones y un conjunto de colores predefinido, y el objetivo es colorear cada región del mapa con uno de los colores disponibles 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. Además, muchas veces se busca minimizar el número de colores que se deben usar para conseguir un coloreado válido, por lo que en este caso estaríamos ante un problema COP. Veremos que esta representación en forma de grafo, que en el problema de coloración de mapas es natural, será usada como metodología general para dar una estructura a las restricciones de cualquier CSP. !!!note En cierta forma, los CSP pueden verse como una extensión del problema SAT de la Lógica Proposicional, pero permitiendo introducir restricciones más expresivas (no únicamente las dadas por las conectivas lógicas) sobre un conjunto de variables que no tienen por qué ser únicamente booleanas y con un lenguaje no restringido (a priori). # Definición Formal de CSP Vamos a presentar más formalmente los conceptos y objetivos básicos que son necesarios en los CSP 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= \{x_1 ,...,x_n \}$ es un conjunto de variables. 2. $D =\langle D_1 ,...,D_n \rangle$ es un vector de dominios ($D_i$ es el conjunto 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 de $X$ por medio de un predicado que restringe los valores que las variables pueden tomar simultáneamente. Una **asignación de variable** es un par *variable-valor*, $(x,a)$, que representa la asignación del valor $a$ a la variable $x$ (a veces, también lo notaremos como $x=a$). Una **asignación de un conjunto de variables** es una tupla de pares ordenados, $((x_{i_1} ,a_{i_1} ),\dots,(x_{i_k} ,a_{i_k}))$, donde cada par ordenado $(x_i,a_i)$ asigna el valor $a_i\in D_i$ a la variable $x_i$. Una tupla se dice **localmente consistente**, o **solución parcial**, si satisface todas las restricciones en las que intervienen únicamente las variables de la tupla. Una **solución a un CSP** es una asignación de valores a todas las variables de $X$ de forma que se satisfagan todas las restricciones de $C$. Es decir, una solución es una tupla consistente que contiene todas las variables del problema. Diremos que un CSP es **consistente** si tiene, 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* (en este caso, es necesario dar alguna **función objetivo**, definida en términos de las variables, que mida la *calidad* de las posibles soluciones). 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. !!!side:2 Si $k=1$ se dice **unaria**. si $k=2$ se dice **binaria**. * **Restricciones**: La **aridad** de una restricción es el número de variables que intervienen en ella: una **restricción $k$-aria** es una restricción que involucra a $k$ variables $^2$. Una **restricción $k$-aria** entre las variables $\{x_{i_1} ,...,x_{i_k}\}$ la denotaremos por $C_{i_1..i_k}$. !!!ejemplo La restricción $C_1\equiv x_1 \leq 5$ es una restricción unaria sobre la variable $x_1$. La restricción $C_{34}\equiv x_4 - x_3 \neq 3$ es una restricción binaria sobre las variables $x_3$ y $x_4$. La restricción $C_{123}\equiv 2x_1 - x_2 + 4x_3 \leq 4$ es una restricción ternaria sobre $x_1, x_2$ y $x_3$. !!!Def: Definición (Tuplas) Una tupla para 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_1...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 $a \in D_j$ si $(x_j,a)$ pertenece a la tupla. 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. !!!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$, o *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 CSP**. 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 representado 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. - **Técnicas de búsqueda**: basadas en la exploración sistemática del espacio de asignaciones hasta encontrar una solución (o probar que no existe tal solución en caso contrario). 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. !!!note Aunque las soluciones son solo las tuplas consistentes con todas las restricciones, es habitual llamar **Espacio de Soluciones** al conjunto de asignaciones, independientemente de que sean solución o no (realmente, es el **espacio de posibles soluciones**). ## Algunos ejemplos de Modelización Veamos algunos ejemplos _clásicos_ de CSP: !!!ejemplo: Problema Criptoaritmético Comencemos por los conocidos **problemas criptoaritméticos**, concretamente por el problema **’send+more=money’**. Este problema (y el resto de problemas criptoaritméticos) puede ser definido 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%") Veamos algunas formas de representar el problema como un CSP, lo que nos servirá para entender también cómo las diversas representaciones intervienen en la dificultad de resolver el problema: **Primera Representación:** La manera más directa de modelar este problema es asignando una variable a cada una de las letras (que, por comodidad, vendrán representadas por las mismas letras del problema), todas ellas tomando valores en el dominio $\{0,...,9\}$ y con las restricciones: 1. Todas las variables toman valores distintos, y 2. Se satisface $send+more=money$. Si traducimos la _ecuación_ anterior al valor de la expresión en base $10$, 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 para encontrar soluciones al ser monolítica: la primera de las restricciones exige manipular todas las variables simultáneamente y no facilita recorrer el espacio combinatorio de valores de forma cómoda, 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 otra representación similar pero 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 restricciones aritméticas 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 ecuaciones. Por ejemplo: ![](img\acarreo.png align="center") Tal y como está planteado el problema, $m$ debe tomar el valor $1$ (ya que es el acarreo de 2 dígitos 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 en principio el espacio de posibles soluciones se amplía, estas permitirán simplificar las restricciones y facilitar su exploración de forma dramática. 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\}$ (solo con esto, hemos pasado de $10^8$ opciones a $9{\times} 1{\times} 2^3 {\times} 10^6$, pero con muchas más opciones para filtrar). 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í, que no repetimos ahora): $$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 a medida que vamos probando zonas en el espacio de soluciones. !!!ejemplo:Problema de las $N$ reinas Veamos ahora el famoso **problema de las $N$ reinas**, que plantea cómo disponer $N$ reinas en un tablero de ajedrez de tamaño $N\times N$ 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 siguientes, tanto por el espacio de combinaciones en las soluciones como por las restricciones: **Primera Representación:** las variables son las reinas, sus dominios las casillas que pueden ocupar: 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:** Las variables son las casillas, sus dominios un valor numérico que indica si hay una reina ($1$) o no ($0$): 1. $X=\{r_{i,j}:\ 1\leq x,y \leq N\}$ (una por cada casilla). 2. $D=\{0,1\}$ (booleanos) 3. Las restricciones: - $\displaystyle{\sum_i r_{i,j} = 1}$, para todo $1\leq j\leq N$. - $\displaystyle{\sum_j r_{i,j} = 1}$, para todo $1\leq i\leq N$. - $\displaystyle{\sum_{(i,j)\in D} r_{i,j} = 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 $k\neq 0$, con $1\leq i+k, j+k \leq N$. - $(r_{i,j} \rightarrow \neg r_{i+k,j-k})$, para todo $k\neq 0$, con $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). Cada variable indica la fila de la reina correspondiente: 1. $X=\{r_i :\ 1\leq i \leq N\}$ (la reina $i$ está en la columna $i$). 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 comprobar si hay alguna globalmente consistente (consideramos el problema de encontrar una solución, no todas): ```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 (ya que el número de posibles soluciones suele ser exponencial en la mayoría de los problemas interesantes). !!!note El método de la tabla de verdad para resolver el problema **SAT** de la Lógica Proposicional es, esencialmente, el método de fuerza bruta, donde: 1. Generamos las $2^n$ asignaciones/valoraciones posibles (cada fila de la tabla de verdad), 2. Comprobamos el valor de verdad de cada valoración para la fórmula, y 3. Seleccionamos (si las hay) aquellas que den valor $1$. Así descrito, este método usa una cantidad exponencial de memoria (para las filas) y una cantidad exponencial de pasos (al menos, un paso para cada fila). ## 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, para no almacenar en memoria todas las asignaciones innecesariamente, ya que no se usan para nada más. 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 y reservar tanta memoria. 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 podemos saber ya que tampoco serán solución. 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 en algunas restricciones por falta de asignació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.  !!!side:3 Más adelante podremos verificar que este procedimiento es simplemente una búsqueda en profundidad con backtracking sobre el árbol que usa las asignaciones parciales como nodos. A continuación presentamos el pseudocódigo de la búsqueda de soluciones por **Backtracking** (**BT**), que sigue fielmente esta idea $^3$. La entrada del algoritmo es una asignación parcial $A$ y una lista de variables sin asignar $U$. La salida es un `fallo/false` (si no hay solución) o una asignación completa (si es solución). Como el algoritmo es constructivo y recursivo, recibe inicialmente la asignación vacía, $A=\emptyset$, y la lista de todas las variables del CSP, $U=X$. Notamos por $D(x)$ al dominio de la variable $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 ``` Como veremos a continuación, este algoritmo básico de backtracking se puede mejorar con poco esfuerzo. La primera mejora 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 que comparten alguna restricción con ella. El siguiente pseudocódigo representa una búsqueda de soluciones por **backtracking con comprobación anticipada** (**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$. Como en el caso anterior, la salida es un `fallo/false` (si no hay solución) o una asignación completa (que es solución al problema). 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 ``` !!!side:4 El _arco_ al que se refiere es al del grafo que se puede construir usando las variables como nodos, y los arcos/aristas indican si hay una restricción común entre dos variables. La idea de comprobación anticipada puede generalizarse en un principio llamado de **consistencia de arco** que veremos un poco más adelante $^4$. En los algoritmos anteriores, hay fijado un cierto orden para las variables y los valores implicados a la hora de ir seleccionándolos... y el orden de estos elementos afecta dramáticamente a la eficiencia de los mismos. En la práctica, en vez de dar un orden a priori, suele ser mucho más eficaz decidir la siguiente variable y el valor correspondiente *sobre la marcha* basándose en algunas estrategias generales: - **Valores Mínimos Restantes** (**MRV**): Al seleccionar qué variable asignar a continuación, la política MRV elige la variable no asignada que tenga el menor número de valores restantes válidos (la variable más restringida), ya que es la que tiene más probabilidades de quedarse sin valores posibles y dar lugar a un retroceso más temprano 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 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. - **Min-conflicts**: ordena los valores de acuerdo a los conflictos en los que estos están involucrados con las variables no asignadas. 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, que supone un cambio del punto de vista, es considerar el problema 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**. !!!side:5 Porque fue la tercera versión que dio su creador, Mackworth, en 1977. El siguiente pseudocódigo corresponde al algoritmo de **Consistencia de Arcos**, **AC3** $^5$, la forma más básica de propagación de restricciones. La idea 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 ≠ ∅ 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 y luego se selecciona iterativamente una variable al azar que este en conflicto y se reasigna su valor a aquel 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**). 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 (en caso de estar interesados en soluciones óptimas). 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 y deja de merecer la pena. 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 motivando que sea preferible satisfacerlas. Además, este mecanismo permite 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: !!!ejemplo:Mantenimiento Preventivo Una central eléctrica típica consta de algunas 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, y sujeto a diversas restricciones. La programación depende de 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. !!!ejemplo:Problema de la subasta combinatoria En este tipo de subasta, los licitadores pueden hacer una oferta por varios artículos de forma conjunta, lo que 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 $R(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. !!!side:6 Existe una versión que sigue las mismas ideas para **SAT** se llama **Max-SAT**. 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 asignación que maximice el número de restricciones satisfechas: este problema se conoce como problema **Max-CSP** $^6$. 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 las tendencias de trabajo más actuales podemos destacar: 1. Técnicas para resolver problemas con muchas variables y/o 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](https://www.cs.us.es/~fsancho/Blog/posts/Algoritmos_Geneticos.md.html) al igual que las [redes neuronales](https://www.cs.us.es/~fsancho/Blog/posts/Redes_Neuronales.md.html), 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 el uso de heurísticas inspiradas biológicamente, tales como [colonias de hormigas](https://www.cs.us.es/~fsancho/Blog/posts/ACO_TSP.md.html), [optimización por enjambres de partículas](https://www.cs.us.es/~fsancho/Blog/posts/PSO.md.html), algoritmos meméticos, algoritmos culturales, búsqueda dispersa, etc.