Problemas de satisfacción de restricciones

Un problema de satisfacción de restricciones, o CSP, describe un conjunto de elecciones y las reglas que las relacionan. Su estado es una representación factorizada: puedes examinar las variables individuales y sus valores, y después reutilizar métodos generales de poda y búsqueda.

Variables, dominios y restricciones

Una variable nombra algo que hay que elegir. Su dominio enumera sus valores permitidos. Una restricción especifica qué combinaciones pueden darse juntas. Para los talleres A y B, haz que cada valor sea una franja horaria de $\{1,2,3\}$. La regla «A va antes que B» tiene ámbito $\{A,B\}$ y relación $\{(1,2),(1,3),(2,3)\}$. Escribir $A<B$ expresa la misma relación de forma compacta.

El ámbito indica las variables involucradas; la relación da las tuplas de valores permitidas. Confundirlos conduce a un modelo en el que «rojo» se convierte en una variable. En la coloración de mapas, las regiones son variables y los colores son valores.

¿Qué cuenta como solución?

Una asignación da valores a las variables. Tres comprobaciones describen su estado:

• Es parcial si algunas variables no tienen valor.
• Es completa si cada variable tiene un valor.
• Es consistente si no incumple ninguna restricción entre las variables asignadas.

Una solución debe ser completa y consistente. Con solo $A=2$, la asignación es consistente pero parcial. Ampliarla con $B=1$ la hace completa e inconsistente. Elegir $B=3$ da una solución a este ejemplo de dos variables. Una asignación parcial consistente puede no tener ninguna forma de completarse: las variables sin asignar pueden quedarse sin opciones compatibles.

Interpreta un grafo de restricciones

Para un CSP binario, dibuja un nodo por variable y una arista por cada par restringido. En un mapa simplificado de Australia, las variables son WA, NT, SA, Q, NSW, V y T, cada una con dominio {rojo, verde, azul}. Los pares vecinos son WA–NT, WA–SA, NT–SA, NT–Q, SA–Q, SA–NSW, SA–V, Q–NSW y NSW–V. Cada arista exige colores diferentes.

Una solución es WA rojo, NT verde, SA azul, Q rojo, NSW verde, V rojo y T rojo. Comprueba cada arista, incluida SA–V. T no tiene ninguna arista, por lo que su color es independiente del territorio continental. Hay 6 coloraciones del territorio continental y 3 opciones para T, lo que da 18 soluciones. Una restricción que involucra varias variables necesita una representación mediante hipergrafo; un nodo adicional de restricción puede conectarse a cada variable de su ámbito.

Dominios y tamaño de la búsqueda

Un dominio discreto finito es una lista fija, como tres colores. Un dominio discreto infinito podría contener todos los tiempos de inicio enteros no negativos. Un dominio continuo podría contener tiempos expresados con números reales. Los dos últimos necesitan representaciones y métodos adecuados a esos dominios; la programación lineal maneja restricciones lineales continuas.

Para $n$ variables con $d$ valores cada una, hay $d^n$ asignaciones completas. El mapa tiene $3^7=2187$ candidatas antes de que las restricciones eliminen alguna. Los CSP finitos incluyen problemas NP-completos, por lo que no se conoce un método general de resolución en tiempo polinómico. Su estructura interna permite, aun así, la poda: el resolvedor puede descartar una elección sin enumerar cada asignación completa que la contiene. Solo los valores finales determinan si la respuesta es válida; el camino usado para encontrarlos es irrelevante.

Las restricciones difieren en cuántas variables conectan y en si establecen requisitos o preferencias. Reconocer esa estructura te ayuda a escribir un modelo fiel y a elegir métodos de propagación útiles.

Clasifica el ámbito

Una restricción unaria limita una variable. Si el taller E no puede usar la franja 1, aplica $E\mathrm{\ne }1$ reduciendo su dominio de $\{1,2,3\}$ a $\{2,3\}$ antes de la búsqueda. Una restricción binaria relaciona dos variables, como $A<B$ o $A\mathrm{\ne }D$. Un CSP binario solo contiene restricciones unarias y binarias.

Una restricción de orden superior involucra al menos tres variables. Si las duraciones de las tareas X, Y y Z deben llenar 10 horas, escribe $X+Y+Z=10$. Con cada duración en $\{1,2,3,4,5\}$, la tupla $(2,3,4)$ no cumple la restricción, mientras que $(2,3,5)$ sí la cumple. Comprobar una regla de orden superior requiere que los valores funcionen conjuntamente.

Conserva las restricciones globales útiles

Una restricción global da una regla con nombre sobre un grupo de tamaño variable. $\mathrm{Alldiff}(X_1,\dots ,X_k)$ exige valores diferentes para cada par. Su conjunto de soluciones equivale al conjunto definido por $k(k-1)\mathrm{/}2$ desigualdades entre pares. Para nueve celdas de Sudoku, eso supone 36 restricciones binarias.

La forma global también permite al resolvedor razonar sobre el grupo. Tres variables limitadas a dos valores distintos no pueden ser todas diferentes, aunque cada par por separado tenga una asignación compatible. Que los conjuntos de soluciones sean iguales no garantiza la misma capacidad de poda.

Una regla de capacidad también puede ser global. Aquí $\mathrm{Atmost}(10,P_1,P_2,P_3)$ significa $P_1+P_2+P_3\le 10$: el número total de personas asignadas a las tres tareas no puede superar diez. Los argumentos representan cantidades que se suman, por lo que esta regla permite, por ejemplo, $(3,4,3)$.

Convierte una restricción finita a forma binaria

Introduce una variable auxiliar U cuyos valores sean las tripletas permitidas para $X+Y+Z=10$. Un valor posible es $(2,3,5)$. Añade tres restricciones binarias: el primer componente de U es igual a X, el segundo es igual a Y y el tercero es igual a Z. Por tanto, seleccionar ese valor para U exige $X=2$, $Y=3$ y $Z=5$.

Cada tripleta original válida corresponde a un valor de U y cada asignación consistente que involucra a U produce una tripleta original válida. Esta construcción permite que los métodos binarios manejen una restricción finita de orden superior. Su costo es el dominio de tuplas potencialmente grande, por lo que los resolvedores suelen conservar la regla global o de orden superior original.

Requisitos y preferencias

Con restricciones blandas, la tarea se convierte en un problema de optimización con restricciones, o COP: satisfacer todas las reglas duras y minimizar el costo total de las preferencias. Para optimizar pueden usarse la ramificación y acotación y la búsqueda local.

Prueba el modelo con una asignación que sepas que es válida y otra que sepas que es inválida. Una desigualdad inventada entre talleres no relacionados elimina horarios legítimos; la ausencia de una restricción para una persona formadora compartida admite horarios imposibles. Las preferencias también requieren cuidado: convertir «se prefiere la tarde» en «se exige la tarde» puede eliminar todos los horarios viables.

Un modelo debe describir las decisiones de forma lo bastante directa para que las reglas sean fáciles de expresar. Empieza por identificar qué hay que elegir, después asigna dominios y traduce cada requisito sobre las variables que realmente involucra.

Construye un horario de talleres

Cinco talleres de una franja cada uno comparten tres franjas horarias: 1 por la mañana, 2 al mediodía y 3 por la tarde. Sea A Fundamentos de Python, B Python avanzado, C Estadística, D Bases de datos y E Ética. Cada taller es una variable con dominio inicial $\{1,2,3\}$.

Los participantes compartidos exigen $A\mathrm{\ne }C$, $A\mathrm{\ne }D$, $C\mathrm{\ne }D$, $B\mathrm{\ne }C$, $C\mathrm{\ne }E$ y $D\mathrm{\ne }E$. Fundamentos debe preceder a Avanzado, por lo que $A<B$. La persona que imparte Ética llega al mediodía, por lo que $E\mathrm{\ne }1$. Esto da siete aristas binarias y una regla unaria; C tiene cuatro vecinos.

La asignación $A=2,B=3,C=1,D=3,E=2$ satisface todas las reglas: cada par con participantes compartidos es diferente, Fundamentos precede a Avanzado y Ética no está en la franja 1. Es la única asignación válida entre las $3^5=243$ candidatas. Los talleres B y D pueden usar ambos la franja 3 porque ninguna regla exige que sean diferentes.

Si se eligiera una variable por franja, cada valor sería un subconjunto de talleres, con hasta $2^5=32$ subconjuntos posibles por franja. Las reglas tendrían entonces que examinar esos conjuntos y asegurar que cada taller aparezca una vez. Elegir los talleres como variables mantiene las restricciones más sencillas.

Expresa los tiempos de las tareas y los recursos compartidos

En la programación de taller, usa una variable de tiempo de inicio para cada tarea. Preparar dura 20 minutos, Analizar 40 y Elaborar informe 30. Los tiempos de inicio son minutos enteros no negativos. El orden y el plazo de 120 minutos dan

Los inicios más tempranos son 0, 20 y 60. Al trabajar hacia atrás desde el plazo se obtienen los inicios más tardíos 30, 50 y 90. Por tanto, las ventanas son $S_P\in [0,30]$, $S_A\in [20,50]$ y $S_R\in [60,90]$.

Dos tareas que comparten una máquina necesitan una restricción disyuntiva: $S_X+d_X\le S_Y$ o $S_Y+d_Y\le S_X$. Cualquiera de las tareas puede ir primero, pero no pueden solaparse. Una simple restricción de precedencia impondría un orden concreto y eliminaría la otra posibilidad.

Modela asignaciones y acertijos

Para tres informes asignados a tres personas revisoras, haz de cada informe una variable cuyos valores sean las personas revisoras. Usa Alldiff si cada persona revisora se encarga de un informe. Un conflicto de intereses elimina a una persona revisora del dominio del informe correspondiente.

Para las n reinas, sea $Q_i$ la fila de la reina en la columna $i$. Una reina por columna está incorporada al modelo. Para cada par, exige $Q_i\mathrm{\ne }{Q}_j$ y $\mathrm{\mid }{Q}_i-Q_j\mathrm{\mid }\mathrm{\ne }\mathrm{\mid }i-j\mathrm{\mid }$ para impedir ataques en filas y diagonales. Para ocho reinas esto reduce el espacio de candidatos de elegir 8 casillas de 64, $4426165368$ colocaciones, a $8^8=16777216$ asignaciones. Hay 92 soluciones.

Para Sudoku, las 81 variables de celda tienen dominios 1–9. Los dígitos dados imponen restricciones unarias y cada una de las 9 filas, 9 columnas y 9 cajas impone Alldiff.

Elige las unidades de tiempo menos detalladas que sigan representando todos los inicios permitidos. Las sesiones que empiezan a la hora en punto necesitan opciones por hora; los dominios minuto a minuto aumentarían el trabajo sin añadir un horario útil. Termina separando las preferencias de las reglas duras y comprobando un caso pequeño con una respuesta conocida.

El retroceso construye una asignación parcial mediante búsqueda en profundidad. Elige una variable, prueba un valor y continúa hasta encontrar una solución o tener que deshacer una elección. La búsqueda conserva las elecciones anteriores útiles cuando falla una posterior.

Ramifica sobre valores, una variable cada vez

Asignar A y luego B produce la misma asignación final que asignar B y luego A. Esta conmutatividad significa que un resolvedor de CSP puede elegir una variable en cada nivel y ramificar sobre sus valores. Permitir todos los órdenes de variables produciría $n!d^n$ hojas para solo $d^n$ asignaciones completas distintas. Para cinco variables con tres valores, son 29 160 hojas en vez de 243.

La siguiente variable puede depender de los dominios actuales. Lo que importa es elegir una sola variable siguiente en un nodo; la búsqueda no necesita ramas separadas para todos los órdenes posibles de asignación.

Sigue los pasos recursivos

1. Si la asignación es completa y consistente, devuélvela.
2. Elige una variable sin asignar.
3. Prueba cada valor del dominio que sea consistente con la asignación actual.
4. Realiza una llamada recursiva después de añadir un valor. Si la llamada recursiva falla, elimina esa asignación y prueba el siguiente valor.
5. Si ningún valor funciona, devuelve fallo a quien hizo la llamada.

El retroceso básico comprueba una restricción una vez que todas las variables de su ámbito tienen valores. Con $A=1$ y B sin asignar, $A<B$ no tiene ningún par completo que rechazar. Al probar $B=1$, falla de inmediato. Esperar hasta que todas las variables estén asignadas retrasaría este rechazo sencillo.

Sigue un callejón sin salida

Usa las reglas de los talleres: $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Toma las variables en el orden A, B, C, D, E y prueba los valores 1, 2, 3.

• Fija $A=1$. Rechaza $B=1$ y elige $B=2$.
• Rechaza $C=1$ por A y $C=2$ por B; elige $C=3$.
• Rechaza $D=1$ por A; elige $D=2$.
• E no tiene ningún valor permitido: 1 está prohibido, 2 entra en conflicto con D y 3 entra en conflicto con C.

El fallo en E devuelve el control a D. Su siguiente valor, 3, entra en conflicto con C. C no tiene ningún valor posterior, por lo que el control vuelve a B. Al probar $B=3$ se llega finalmente a otro callejón sin salida con $A=1$. La búsqueda prueba entonces $A=2$ y llega a $A=2,B=3,C=1,D=3,E=2$. Con este orden, el retroceso básico prueba 32 valores candidatos en total, incluidos los rechazados.

Qué garantiza el método

Comprobar las restricciones y almacenar el modelo también tienen costos. La descripción de memoria lineal se refiere al camino de búsqueda, mientras que la propagación también puede almacenar dominios y registros para deshacer cambios.

El retroceso cronológico vuelve a la elección más reciente. Las variantes más rápidas mejoran cuatro decisiones distintas: la siguiente variable, el orden de sus valores, las consecuencias inferidas después de una elección y la elección anterior que se debe revisar después de un fallo. Estas mejoras reducen el trabajo práctico sin cambiar lo que cuenta como solución.

Una buena ordenación puede revelar fallos cerca de la raíz de un árbol de búsqueda o conservar opciones útiles para más adelante. La ordenación de variables y la de valores tienen propósitos diferentes, por lo que la dirección que parece mejor difiere entre ellas.

Elige la variable más restringida

La heurística de los mínimos valores restantes (MRV) selecciona la variable sin asignar con menos valores actualmente permitidos. También se llama heurística de la variable más restringida o de fallar primero. Es probable que un dominio casi agotado revele pronto una contradicción. Si un dominio está vacío, la rama falla de inmediato.

Cuenta los valores actuales después de la poda, no los tamaños iniciales de los dominios. Sin dominios almacenados, un resolvedor debe determinar qué valores originales siguen siendo consistentes con la asignación antes de aplicar MRV.

La heurística del grado resuelve un empate de MRV eligiendo la variable con más restricciones sobre otras variables sin asignar. Esta elección afecta a más decisiones restantes. Los vecinos ya asignados no cuentan para este grado restante. Al principio del mapa de Australia, los dominios iguales de tres colores empatan y los cinco vecinos de SA le dan el grado más alto.

Mantén abiertas las opciones al elegir un valor

La heurística del valor menos restrictivo (LCV) prueba el valor que elimina menos valores de los dominios vecinos sin asignar. Evaluar valores candidatos añade cálculos, pero puede evitar una rama fallida costosa.

Con WA rojo y NT verde, SA solo puede ser azul, mientras que Q puede ser rojo o azul. Elegir Q azul vaciaría el dominio de SA. Elegir Q rojo elimina rojo de NSW y conserva el azul de SA. Por tanto, LCV prueba Q rojo.

Cada variable debe recibir finalmente un valor, lo que hace útil probar pronto una variable con pocas opciones. Solo se necesita un valor para completar una primera solución, lo que favorece un valor que deje margen para otras decisiones.

Combina la ordenación con la comprobación hacia delante

En el horario de talleres, aplica primero $E\mathrm{\ne }1$. E tiene dos valores; A, B, C y D tienen tres cada una. MRV elige E. Prueba $E=2$ y la comprobación hacia delante elimina 2 de C y D.

C y D empatan ahora con dominios $\{1,3\}$. C tiene tres vecinos sin asignar, A, B y D; D tiene dos, A y C. La heurística del grado selecciona C. Elige $C=1$, con lo que quedan $D_D=\{3\}$ y $D_A=D_B=\{2,3\}$. MRV elige $D=3$, lo que obliga a $A=2$; la regla de precedencia da entonces $B=3$. Cinco asignaciones encuentran la solución sin retrocesos. El orden fijo de variables con comprobación hacia delante necesita 12 asignaciones y llega a dos callejones sin salida.

La ordenación conserva la completitud porque cambia la secuencia de elecciones sin descartar ramas permitidas. La búsqueda en el peor caso sigue siendo exponencial. Al enumerar todas las soluciones o demostrar que no hay solución, todos los valores relevantes deben explorarse finalmente, por lo que se reduce la ventaja de LCV de lograr un éxito temprano. Su principal utilidad es encontrar antes una primera solución.

Un callejón sin salida suele tener una causa más pequeña que toda la asignación actual. El retroceso por saltos usa esa causa para decidir a dónde volver, y el aprendizaje de restricciones recuerda un fallo para que no sea necesario descubrirlo de nuevo.

Encuentra las elecciones que causaron el fallo

En el mapa de Australia, toma el orden de asignación Q, NSW, V, T, SA. Sean Q rojo, NSW verde, V azul y T rojo. SA limita con Q, NSW y V, por lo que los tres colores están prohibidos. Su conjunto de conflictos es $\{Q,NSW,V\}$: las variables anteriores cuyas elecciones excluyen sus valores.

El retroceso cronológico intentaría cambiar T. Tasmania no tiene ninguna arista con SA, por lo que cambiar su color no puede restaurar ninguna opción para SA. El retroceso por saltos vuelve a V, el miembro del conjunto de conflictos asignado más recientemente, y salta T.

Un conjunto de conflictos contiene variables; una combinación prohibida registra asignaciones concretas. Esa distinción importa: otro color para V puede corregir el fallo, aunque V siga siendo vecina de SA.

Propaga un conflicto a través de fallos anteriores

El retroceso por saltos simple usa el conjunto de conflictos directo del fallo actual. El retroceso por saltos dirigido por conflictos lleva información a través de varios niveles fallidos. Cuando una variable fallida X salta a Y, Y absorbe el conjunto de conflictos de X sin incluir Y. Si Y agota después todos sus valores, su conjunto combinado identifica una causa situada más atrás en la asignación.

Por ejemplo, usa el orden WA, NSW, T, NT, Q, V, SA y empieza con WA rojo, NSW rojo, T rojo. WA y NSW no son vecinas, por lo que esta asignación parcial es consistente. Sus elecciones eliminan rojo de NT, Q y SA. Esas tres regiones forman un triángulo que no puede colorearse usando solo verde y azul.

Ninguna elección hecha para T cambia ese triángulo. La información sobre conflictos puede viajar hacia atrás a través de los intentos fallidos e identificar WA y NSW como la causa subyacente. La búsqueda vuelve a NSW, la última de esas dos decisiones, en vez de dedicar tiempo a volver a colorear T.

Aprende la combinación fallida

Un resolvedor puede registrar $\{WA=\text{rojo},NSW=\text{rojo}\}$ como una combinación prohibida. Siempre que ambas elecciones se repitan, se produce la misma contradicción del triángulo, por lo que la rama puede rechazarse de inmediato. Sería incorrecto prohibir WA rojo por sí solo: WA puede ser rojo en soluciones válidas con un color diferente para NSW.

El aprendizaje añade una restricción o una combinación prohibida almacenada en caché. La condición aprendida debe deducirse de las restricciones originales; un fallo causado simplemente por alcanzar un límite de tiempo no proporciona esa justificación lógica. Una combinación prohibida útil conserva suficientes asignaciones para explicar la imposibilidad sin incluir elecciones no relacionadas.

Combina la anticipación y la revisión retrospectiva

La comprobación hacia delante y la consistencia de arcos eliminan los valores sin soporte antes de que se produzca un fallo profundo. El retroceso por saltos diagnostica un fallo después de que ocurre. El retroceso por saltos directo y simple no añade poda a lo que ya detecta la comprobación hacia delante, pero los métodos dirigidos por conflictos pueden combinar explicaciones de fallos más profundos. El aprendizaje conserva esas explicaciones para ramas posteriores.

La comprobación hacia delante pregunta qué descarta de inmediato una nueva asignación para las variables vecinas sin asignar. Elimina los valores incompatibles antes de que la búsqueda llegue a esas variables, lo que permite detectar algunos callejones sin salida varios niveles antes.

Poda después de una asignación

Después de elegir $X=x$, examina cada Y sin asignar que comparta una restricción con X. Elimina cada valor de $D_Y$ que entre en conflicto con la elección. Un dominio vacío significa que la rama actual no puede completarse, por lo que hay que retroceder de inmediato.

Para $X\mathrm{\ne }Y$, asignar $X=2$ elimina 2 de Y. Para $X<Y$, asignar $X=2$ elimina todos los valores de Y que sean como máximo 2. La relación concreta determina qué se elimina; la comprobación hacia delante no se limita a eliminar valores iguales.

La poda cambia los dominios de la rama actual. Mantén un registro de deshacer, a menudo llamado registro de cambios, de cada eliminación causada por la elección. Cuando se deshaga esa elección, restaura sus eliminaciones y conserva las restricciones que pertenecen a elecciones anteriores. Otra implementación consiste en copiar los dominios en cada nivel.

Sigue los dominios de los talleres

Usa las franjas 1–3 y las reglas $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Aplica la regla unaria para obtener $D_E=\{2,3\}$ y después usa el orden fijo A, B, C, D, E.

1. $A=1$ deja a B, C y D con $\{2,3\}$.
2. $B=2$ deja a C con $\{3\}$.
3. $C=3$ deja tanto a D como a E con $\{2\}$.
4. $D=2$ elimina 2 de E y vacía su dominio. Retrocede.

Restaurar los dominios y probar $B=3$ obliga a C a ser 2. D y E pasan ambas a 3, por lo que asignar D vuelve a vaciar E. La búsqueda debe cambiar A. Con $A=2$, puede llegar a $B=3,C=1,D=3,E=2$. Este recorrido prueba 12 valores, frente a 32 pruebas de candidatos del retroceso básico en el mismo orden.

Reconoce el límite de la comprobación de un paso

Después del paso 3, D y E tienen ambas como único valor 2 y deben ser diferentes. La comprobación hacia delante aún no ha comprobado esa restricción: ni D ni E se han asignado en ese momento. Solo detecta el fallo cuando D recibe su valor.

Este es el límite central de la comprobación hacia delante. Comprueba la variable asignada frente a sus vecinas sin asignar, sin propagar los efectos de la reducción del dominio de una vecina. La consistencia de arcos puede seguir esas consecuencias entre variables sin asignar.

Usa los dominios actualizados

MRV puede ahora seleccionar directamente el dominio restante más pequeño. Un dominio con un solo valor suele ser la siguiente elección; un dominio vacío señala un fallo sin añadir otra asignación. Mantener los dominios actualizados ayuda tanto a la inferencia como a la ordenación.

Para como máximo $n-1$ vecinos y como máximo $d$ valores por vecino, una pasada de comprobación hacia delante usa unas $O(nd)$ comprobaciones binarias, suponiendo que la prueba de la relación tarda tiempo constante. Solo elimina valores incompatibles con la asignación actual, por lo que el retroceso sigue siendo completo. Olvidar restaurar una eliminación puede hacer que una rama posterior pierda una solución válida; podar una variable no relacionada puede tener el mismo efecto.

Un valor necesita un valor compatible en cada dominio vecino. La consistencia de arcos hace explícito ese requisito de soporte y sigue los efectos de los cambios de dominio por todo un CSP binario.

El soporte tiene una dirección

La consistencia de nodos elimina primero los valores prohibidos por las reglas unarias. Para una restricción binaria, el arco dirigido $X\to Y$ es consistente cuando cada valor de X tiene al menos un valor compatible en Y. Ese valor de Y es un soporte. Revisar el arco elimina los valores sin soporte de su origen, X.

Para $A<B$ con ambos dominios $\{1,2,3\}$, revisar $A\to B$ elimina 3 de A. Revisar $B\to A$ elimina 1 de B. Los dominios resultantes son $D_A=\{1,2\}$ y $D_B=\{2,3\}$. Un valor que permanece puede usar un soporte diferente para cada vecino; los soportes no tienen por qué formar una solución conjunta.

Ejecuta AC-3

AC-3 usa una cola de arcos dirigidos:

1. Pon inicialmente todos los arcos en la cola.
2. Extrae $X\to Y$ y revisa X usando el dominio de Y.
3. Si X queda vacío, detente e informa de un fallo.
4. Si X se reduce, añade $Z\to X$ para cada otro vecino Z de X, excepto Y.
5. Continúa hasta que la cola esté vacía.

Una eliminación en X puede quitar un soporte de Z, por lo que la cola debe incluir arcos que apunten al dominio modificado. El arco desde Y no necesita una nueva comprobación inmediata: los valores eliminados de X no daban soporte a ningún valor de Y, ya que ninguno era compatible con Y desde el principio. Los dominios no vacíos obtenidos al finalizar son independientes del orden de procesamiento; distintos órdenes pueden llegar al fallo con distintos dominios vacíos.

Propaga una decisión sobre los talleres

Para las reglas de los talleres $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$, la ejecución inicial de AC-3 elimina 3 de A y 1 de B. Deja a C y D con $\{1,2,3\}$ y a E con $\{2,3\}$.

Ahora decide $C=1$. El arco $A\to C$ elimina 1 de A y deja $A=2$. Revisar B frente a A obliga a $B=3$. D es diferente de C y de A, por lo que $D=3$. E es diferente de D y no puede ser 1, por lo que $E=2$. Las reducciones de dominio han llegado más allá de los vecinos inmediatos de la decisión original.

El mantenimiento de la consistencia de arcos (MAC) aplica esta inferencia después de cada decisión de búsqueda. Partiendo de dominios consistentes de arco, restringir $X=x$ requiere una cola de arcos entrantes desde sus vecinos sin asignar. Las eliminaciones de dominio deben restaurarse cuando la búsqueda deshace la rama.

Interpreta el resultado y el costo

Un triángulo con dominios {rojo, azul} y desigualdades en las tres aristas sigue siendo consistente de arco, pero no tiene solución. Cada arista tiene soportes por separado, pero las tres elecciones no pueden funcionar conjuntamente.

Con $c$ restricciones binarias y un tamaño máximo de dominio $d$, AC-3 tarda $O(c{d}^3)$: una revisión de arco comprueba hasta $d^2$ pares, y cada arco puede requerir hasta $d$ rondas a medida que su destino pierde valores. MAC dedica más trabajo por nodo de búsqueda que la comprobación hacia delante, a menudo a cambio de un árbol de búsqueda mucho más pequeño.

Los soportes separados entre pares pueden ocultar una contradicción de grupo. Una consistencia más fuerte y la propagación global especializada examinan combinaciones que la consistencia de arcos pasa por alto, mientras que las cotas numéricas pueden comprimir dominios grandes en intervalos útiles.

Amplía asignaciones a otra variable

La consistencia de caminos examina tripletas. Toda asignación consistente a dos variables debe poder ampliarse a una tercera de forma consistente con ambas. En un triángulo coloreado de rojo o azul, X rojo e Y azul no dejan ningún valor para Z. La consistencia de caminos elimina ese par permitido y finalmente revela que no hay solución. Puede eliminar tuplas de las relaciones, por lo que hace más que eliminar valores individuales de los dominios.

La k-consistencia exige que toda asignación consistente a cualesquiera $k-1$ variables pueda ampliarse a cualquier variable adicional. Para CSP binarios, la 1-consistencia corresponde a la consistencia de nodos, la 2 a la consistencia de arcos y la 3 a la consistencia de caminos. La k-consistencia fuerte incluye todos los niveles del 1 al k. Con n-consistencia fuerte en n variables y dominios no vacíos, cualquier asignación parcial consistente puede ampliarse hasta convertirse en una solución, sin retroceso. Establecer esta propiedad tiene costos de tiempo y memoria exponenciales en el peor caso.

Cuenta los valores en Alldiff

Alldiff exige valores distintos para todas las variables de su ámbito. Si un grupo de m variables tiene solo n valores posibles distintos y $m>n$, ninguna asignación puede satisfacerla.

Para tres celdas con dominios $\{4,7\}$, las desigualdades por pares son consistentes de arco: cada 4 tiene soporte 7 en cada vecina y cada 7 tiene soporte 4. Sin embargo, el conteo global falla porque se necesitan tres valores diferentes y solo existen dos.

Si dos celdas tienen ambas el dominio $\{4,7\}$, deben usar 4 y 7 entre las dos. Esos valores pueden eliminarse de todas las demás celdas de esa fila. Este razonamiento de par desnudo usa un subconjunto del ámbito completo de Alldiff. Un propagador global simple también puede procesar repetidamente variables con un solo valor, eliminar sus valores de las demás y comprobar si quedan demasiados pocos valores distintos. Los propagadores más fuertes también reconocen subconjuntos restringidos.

Ajusta las cotas numéricas

La propagación de cotas almacena un dominio mediante su mínimo y su máximo. La consistencia de cotas exige que cada extremo tenga una ampliación que satisfaga cada restricción pertinente; no comprueba todos los valores interiores.

Para dos autobuses que transportan 100 personas, sean $B_1\in [0,50]$ y $B_2\in [0,70]$, con $B_1+B_2=100$. El segundo autobús transporta como máximo 70, lo que obliga a $B_1\ge 30$. El primero transporta como máximo 50, lo que obliga a $B_2\ge 50$. Las ventanas ajustadas son $[30,50]$ y $[50,70]$.

Para Preparar, Analizar y Elaborar informe, que duran 20, 40 y 30 minutos en ese orden, un plazo de 120 minutos da los inicios más tardíos 30, 50 y 90. Los inicios no negativos dan los inicios más tempranos 0, 20 y 60. La propagación hacia delante y hacia atrás obtiene estas ventanas antes de elegir un tiempo de inicio.

Elige una intensidad útil

Cada celda de Sudoku tiene 20 celdas relacionadas distintas: 8 en su fila, 8 en su columna y 4 celdas adicionales en su caja. En las 81 celdas eso da $81\times 20\mathrm{/}2=810$ pares distintos que deben ser diferentes. Las restricciones globales conservan las mismas soluciones que esos pares, pero pueden revelar antes pares desnudos y escasez de valores. Una inferencia más fuerte cuesta más por pasada; los resolvedores prácticos equilibran ese costo con la búsqueda que ahorra, combinando a menudo la consistencia de arcos con la propagación global y de cotas especializada.

La búsqueda local parte de un valor para cada variable, incluso cuando algunas restricciones no se cumplen. La heurística de mínimos conflictos repara esta asignación completa moviendo una variable en conflicto a un valor con el menor número posible de conflictos.

Elige una reparación

1. Construye una asignación completa, de forma aleatoria o voraz.
2. Si no se incumple ninguna restricción, devuelve la solución.
3. Elige al azar una variable que intervenga en una restricción incumplida.
4. Evalúa cada uno de sus valores de dominio frente a las otras variables, que permanecen fijas.
5. Elige un valor con el menor número de conflictos, resuelve los empates al azar y repite hasta alcanzar el éxito o un límite de pasos.

Una variable en conflicto participa en al menos una restricción incumplida. No tiene por qué ser la variable con el mayor número de incumplimientos. La elección aleatoria entre variables en conflicto y valores empatados ayuda a evitar una secuencia repetida y rígida.

Repara un tablero de 4 reinas

Usa una reina por columna, con las variables de fila $Q_1,Q_2,Q_3,Q_4$. Un par está en conflicto si sus filas son iguales o si su diferencia de filas es igual a su diferencia de columnas. Empieza con $(2,4,2,3)$. Las columnas 1 y 3 comparten la fila 2; las columnas 3 y 4 se atacan en diagonal. Las variables en conflicto son Q1, Q3 y Q4.

Elige Q3 y evalúa las filas mientras Q1, Q2 y Q4 permanecen fijas:

La fila 1 da $(2,4,1,3)$, una solución. Si se hubiera elegido Q1, sus números para las filas 1–4 serían 0, 1, 2 y 2. Moverla a la fila 1 da $(1,4,2,3)$, con el conflicto diagonal Q3–Q4 restante. Por tanto, una reparación localmente óptima puede dar lugar a otro proceso de reparación incompleto.

Cuenta las restricciones que involucran a la variable seleccionada. Contar todos los incumplimientos de cada tablero resultante da el mismo orden, porque las restricciones no relacionadas aportan una constante a cada candidato. Simplemente requiere más trabajo. Usa una definición consistente de conflicto al comparar candidatos.

Repara un horario existente

Cuando una persona formadora deja de estar disponible, el horario actual ya es una asignación completa. La heurística de mínimos conflictos puede empezar ahí y mover sesiones hasta que se cumplan las restricciones nuevas y las existentes. Un cambio pequeño suele necesitar pocas reparaciones, aunque un movimiento puede crear nuevos conflictos en otra parte. Si importa conservar el plan anterior, asigna un costo explícito a cambiar una asignación; minimizar solo los incumplimientos no minimiza las alteraciones.

Los experimentos con una buena asignación inicial han requerido relativamente pocos pasos de reparación incluso para un millón de reinas. Los tableros más grandes siguen haciendo que cada paso sea más costoso. La heurística de mínimos conflictos también se ha usado para programar el Hubble, con una reducción comunicada de unas tres semanas a unos 10 minutos para programar una semana de observaciones.

Interpreta el comportamiento de la búsqueda

Muchas familias de CSP aleatorios pasan de ser mayormente resolubles a no tener solución en su mayoría a medida que aumenta la proporción de restricciones respecto a variables. Cerca de esa transición, decidir cómo interactúan las elecciones suele ser más difícil. Los problemas con pocas restricciones pueden tener muchas soluciones fáciles de alcanzar. Los problemas sin solución y con muchas restricciones pueden ser rechazados rápidamente por resolvedores completos basados en propagación.

Alcanzar el límite de pasos de mínimos conflictos significa que no se encontró una solución en esa ejecución. El problema aún puede tener solución. La eficacia práctica del método proviene de reparaciones eficientes, incluidos los movimientos con igual puntuación, a pesar de que las soluciones son una fracción diminuta de todas las asignaciones posibles.

La búsqueda por reparación puede dejar de mejorar mientras aún quedan conflictos. Para continuar, el resolvedor necesita una forma de moverse por estados con igual puntuación o cambiar qué movimientos parecen convenientes. El resultado requerido también importa: una reparación viable y rápida y una demostración de que no hay solución exigen métodos diferentes.

Muévete por una meseta

Un mínimo local tiene incumplimientos, pero ningún movimiento de una sola variable reduce su número. Una meseta es una región conexa de asignaciones con la misma puntuación. Los movimientos que solo mejoran pueden quedar atrapados; un movimiento lateral cambia el estado sin reducir la puntuación.

Para 4 reinas, $(1,4,2,3)$ tiene un conflicto entre Q3 y Q4. Con las otras reinas fijas, los números de Q3 para las filas 1–4 son 1, 1, 3 y 2; los de Q4 son 2, 2, 1 y 2. Ninguna de las dos variables tiene un movimiento que mejore el resultado.

Mover Q3 a la fila 1 da $(1,4,1,3)$, todavía con un conflicto, ahora Q1–Q3 comparten una fila. En este nuevo estado los números de Q1 son 1, 0, 3 y 1. Mover Q1 a la fila 2 produce $(2,4,1,3)$ y elimina el conflicto. El movimiento lateral cambió los movimientos de mejora disponibles.

Mantén la búsqueda en movimiento

Una lista tabú es una memoria de corta duración. Desalienta el regreso inmediato a un estado que se acaba de abandonar. Un reinicio explora una región diferente, mientras que el recocido puede atravesar una región con más conflictos durante la ejecución actual.

Con la ponderación de restricciones, inicia cada peso en 1 y puntúa un estado mediante la suma de los pesos de sus restricciones incumplidas. Elige un cambio que reduzca esta puntuación ponderada y después aumenta los pesos de las restricciones que siguen incumplidas. Los fallos repetidos se vuelven más costosos y remodelan el paisaje de búsqueda. Una puntuación ponderada de cero sigue significando que se satisfacen todas las restricciones duras con peso positivo.

Elige la información que necesitas

La búsqueda local es incompleta: puede pasar por alto una solución existente y una ejecución finita sin éxito deja sin resolver si no existe solución. El retroceso con propagación en dominios finitos es completo: finalmente encuentra una solución o agota todas las formas posibles de completar la asignación.

Usa la búsqueda local cuando un problema grande con pocas restricciones necesite una asignación viable o una reparación rápida. El retroceso con MRV y MAC es una buena opción para acertijos con muchas restricciones y siempre que la tarea requiera demostrar que no hay solución. El tiempo de ejecución sigue dependiendo de la instancia; estas elecciones de método se basan en sus garantías.

El horario de talleres tiene la solución única $A=2,B=3,C=1,D=3,E=2$. Añadir $C\mathrm{\ne }1$ la elimina. La heurística de mínimos conflictos puede intentar reparaciones hasta su límite, pero solo una búsqueda completa que agote los casos restantes demuestra que la persona organizadora debe cambiar un requisito, por ejemplo añadir otra franja.

Un grafo de restricciones puede revelar problemas más pequeños dentro de uno grande. Los componentes independientes pueden resolverse por separado, y los componentes acíclicos admiten un algoritmo especialmente eficiente con una pasada de poda hacia atrás y una pasada de asignación hacia delante.

Separa los componentes desconectados

Un componente conexo es independiente cuando ninguna restricción conecta sus variables con otro componente. Resuelve cada componente y después combina una solución de cada uno. Si algún componente no tiene solución, el CSP completo no tiene solución. En el mapa de Australia, Tasmania es independiente del territorio continental.

Con n variables divididas en grupos independientes de tamaño c, obtener una asignación completa requiere trabajo del orden de $O((n\mathrm{/}c)d^c)$ en vez de $O(d^n)$. Para 60 variables binarias divididas en tres grupos de 20, las búsquedas exhaustivas separadas consideran como máximo $3\times 2^{20}=3145728$ asignaciones en vez de aproximadamente $\mathrm{1,15}\times {10}^{18}$. Enumerar todas las soluciones combinadas seguiría requiriendo listar las combinaciones; el ahorro describe la resolución de los problemas de los componentes.

Ordena un árbol desde su raíz

Un CSP binario tiene estructura de árbol cuando su grafo de restricciones es acíclico. Un árbol conexo tiene un camino entre cada par de variables; un bosque contiene árboles separados. Aplica primero las restricciones unarias. Elige cualquier raíz y ordena las variables de modo que cada padre aparezca antes que sus hijos.

La consistencia de arcos dirigida en este orden exige que cada variable anterior tenga soporte en cada vecino posterior. En un árbol, esos vecinos posteriores son sus hijos. La dirección del soporte va del padre al hijo, aunque el algoritmo procesa a los hijos antes que a los padres.

Poda hacia atrás y asigna hacia delante

1. Lee el orden hacia atrás, excluyendo la raíz. Para cada hijo, revisa el arco desde su padre hacia ese hijo. Elimina los valores sin soporte del dominio del padre.
2. Si un dominio queda vacío, informa de que no hay solución.
3. Lee el orden hacia delante. Elige cualquier valor restante para la raíz y después da a cada hijo un valor compatible con su padre asignado.

Los descendientes del hijo ya se han procesado cuando se revisa su padre. Por tanto, un valor restante del padre tiene soporte en cada hijo y cada valor de un hijo ya tiene soporte más abajo. Las distintas ramas de hijos no tienen aristas que las conecten, por lo que esos soportes pueden elegirse de forma independiente. Por eso el recorrido hacia delante no necesita retroceso.

Sigue el árbol de los talleres

Fija $C=1$ en el horario de talleres y elimina 1 de los dominios de los otros talleres. El grafo restante es el camino B–A–D–E, con dominios $\{2,3\}$ y restricciones $A<B,A\mathrm{\ne }D,D\mathrm{\ne }E$.

Elige la raíz A y el orden A, B, D, E. El recorrido hacia atrás revisa $D\to E$ y después $A\to D$, sin cambios. Finalmente, $A\to B$ elimina 3 de A porque B no tiene un valor mayor. Asignar hacia delante da $A=2,B=3,D=3,E=2$. Restaurar $C=1$ da el horario completo.

Para n variables con tamaño máximo de dominio d, el recorrido hacia atrás revisa $n-1$ arcos con hasta $O(d^2)$ cada uno, lo que da un tiempo $O(n{d}^2)$. La garantía depende de la ausencia de ciclos. Un ciclo puede conectar ramas de hijos separadas e invalidar la independencia que hacía seguras esas elecciones locales.

Un grafo con pocos ciclos aún puede estar lo bastante cerca de un árbol como para resolverse eficientemente. El condicionamiento por conjunto de corte asigna primero las variables seleccionadas; la descomposición arbórea agrupa las variables en partes solapadas. Ambos hacen que la coordinación restante tenga forma de árbol.

Condiciona sobre un conjunto de corte de ciclos

Un conjunto de corte de ciclos es un conjunto de variables cuya eliminación deja un árbol o un bosque. Comprueba todos los ciclos restantes, no solo el más visible. Para el mapa de Australia, eliminar SA deja el camino WA–NT–Q–NSW–V más T aislada. Para el grafo de talleres, eliminar C deja B–A–D–E.

Para cada asignación al conjunto de corte que satisfaga sus restricciones internas:

1. Elimina los valores incompatibles de los dominios restantes.
2. Resuelve cada árbol restante mediante poda hacia atrás y asignación hacia delante.
3. Si todos tienen éxito, combina sus asignaciones con los valores del conjunto de corte. En caso contrario, prueba otra asignación del conjunto de corte.

En el problema de los talleres, $C=1$ deja un árbol resoluble. Con $C=2$, A y B deben proceder de $\{1,3\}$ y $A<B$ obliga a $A=1,B=3$. D debe ser diferente tanto de A como de C, lo que da $D=3$. E no puede ser 1 y debe ser diferente de C y D, por lo que no queda ningún valor. Con $C=3$, A y B deben ser 1 y 2; D debe ser entonces 2, lo que vuelve a dejar a E sin valor.

Para un conjunto de corte de tamaño c, hay como máximo $d^c$ asignaciones, cada una seguida de un problema de árbol con costo $O((n-c)d^2)$. El total es $O(d^c(n-c)d^2)$. Un c pequeño hace que esto sea útil; sigue siendo exponencial en c. Encontrar un conjunto de corte mínimo es NP-difícil, pero un conjunto de corte válido no mínimo sigue dando un procedimiento correcto.

Une bolsas solapadas

Una descomposición arbórea organiza conjuntos de variables, llamados bolsas, en un árbol. Debe satisfacer tres condiciones:

• Cada variable aparece en una bolsa.
• El ámbito de cada restricción cabe dentro de al menos una bolsa.
• Las bolsas que contienen una misma variable forman una parte conexa del árbol de bolsas.

La tercera regla es la propiedad de intersección continua. Si X aparece en ambos extremos de un camino de bolsas, debe aparecer a lo largo de todo ese camino. De lo contrario, bolsas distantes podrían elegir valores inconsistentes de X sin ninguna comprobación de concordancia intermedia.

Las asignaciones localmente válidas de cada bolsa se convierten en valores de una megavariable. Las bolsas adyacentes deben coincidir en las variables compartidas. El árbol resultante coordina las soluciones locales. Para un triángulo X–Y–Z–X más la arista Z–W, las bolsas $\{X,Y,Z\}$ y $\{Z,W\}$ cubren todas las aristas y coinciden en Z.

La anchura arbórea de la descomposición es el tamaño de su bolsa más grande menos 1. La anchura arbórea de un grafo es el mínimo entre las descomposiciones válidas. Para una anchura w, la cota habitual del CSP es $O(n{d}^{w+1})$. Una anchura fija y acotada controla el exponente.

Elimina la simetría de valores

Cuando los nombres de los colores no tienen un significado especial, permutar rojo, verde y azul conserva la validez. Las seis soluciones del territorio continental de Australia son seis cambios de nombre de un mismo patrón. Fijar el orden NT antes de SA antes de WA en el orden de colores rojo, verde, azul conserva un representante. Una restricción de ruptura de simetría de este tipo solo es válida cuando el cambio de nombres conserva las reglas originales. Una regla que exija que una región concreta sea roja hace especial ese color y cambia qué permutaciones siguen siendo simetrías.