AC-3:1999 年的演算法如何在搜尋前縮減 CSP
AC-3: cómo un algoritmo de 1999 recorta un CSP antes de buscar
AC-3 透過檢查 CSP 中受限制連接的變數,移除沒有相容值的選項,縮小搜尋空間。它反覆檢查弧,直至達到弧一致性,再由回溯等搜尋演算法完成求解;AC-3 只處理兩個變數之間的二元限制。
Un Sudoku vacío parece un problema de fuerza bruta: probar cada número en cada casilla hasta que algo encaje. Pero antes de adivinar nada, se puede descartar buena parte de las opciones mirando solo las restricciones entre casillas vecinas. A ese filtrado previo se le llama propagación de restricciones, y el algoritmo que la popularizó en la inteligencia artificial clásica es AC-3, uno de los algoritmos que el investigador Krzysztof Apt unificó en un mismo marco formal en un paper de 1999 que todavía se usa como referencia (arxiv.org/abs/cs/9909009v1).
Qué es la propagación de restricciones en un CSP
Un CSP (constraint satisfaction problem, problema de satisfacción de restricciones) tiene tres partes: un conjunto de variables, un dominio de valores posibles para cada una y un conjunto de restricciones que dicen qué combinaciones de valores son válidas. Un Sudoku es un CSP: cada casilla vacía es una variable, su dominio son los números del 1 al 9 que todavía podrían ir ahí, y la restricción es que ninguna fila, columna o cuadro repita un número. Un cronograma de exámenes es otro CSP típico: cada materia es una variable, el dominio son los horarios disponibles y la restricción es que un mismo profesor no dé dos exámenes a la vez.
Resolver un CSP a fuerza bruta significa probar combinaciones hasta encontrar una que cumpla todas las restricciones. Eso funciona en problemas chicos, pero el espacio de búsqueda crece muy rápido: cada variable que se agrega multiplica las combinaciones posibles por el tamaño de su dominio. La propagación de restricciones ataca el problema antes: usa las restricciones mismas para eliminar valores que ya sabemos que nunca van a formar parte de una solución, sin tener que probarlos.
AC-3: cómo recorta el espacio antes de que empiece la búsqueda
AC-3 trabaja sobre pares de variables conectadas por una restricción, a los que llama arcos, la misma noción que Apt usa para formalizar el algoritmo dentro de su marco genérico de conmutatividad (arxiv.org/abs/cs/9909009v1). Para cada arco (Xi, Xj) revisa si todo valor que queda en el dominio de Xi tiene al menos un valor compatible en el dominio de Xj. Si encuentra un valor de Xi que no tiene ningún compañero posible en Xj, lo elimina del dominio de Xi: ese valor nunca podría formar parte de una solución válida.
El algoritmo mantiene una cola con todos los arcos pendientes de revisar. Cada vez que revisa un arco y elimina al menos un valor, vuelve a poner en la cola todos los arcos que apuntan hacia la variable que acaba de cambiar, porque esa reducción puede abrir nuevas eliminaciones en otras partes del grafo de restricciones. El proceso termina cuando la cola queda vacía: en ese punto, cada valor que sobrevive en cada dominio tiene al menos un valor compatible en cada variable vecina. A ese estado se lo llama consistencia de arcos. Esa misma lógica de cola de arcos y reencolado es la que implementa en código abierto python-constraint (github.com/python-constraint/python-constraint), la librería ya citada en Referencias.
Un ejemplo chico con dos casillas de Sudoku en la misma fila ayuda a verlo. Si la casilla A tiene dominio {2, 5} porque ya se descartaron el resto de los números por otras restricciones, y la casilla B tiene dominio {2, 5, 7}, la restricción de que A y B no repitan número todavía permite varias combinaciones: no hay nada para recortar todavía. Pero si una restricción aparte reduce el dominio de A a un único valor, {5}, entonces el arco (B, A) se vuelve a revisar y el 5 se elimina del dominio de B, porque B ya no puede valer 5 sin repetir el número de A. Esa eliminación en B puede, a su vez, disparar la revisión de otros arcos que involucran a B. AC-3 nunca decide un valor final por sí mismo: solo reduce los dominios hasta que no queda nada más para descartar, y ese resultado más chico es el que recibe el algoritmo de búsqueda (típicamente backtracking) para terminar de elegir los valores.
flowchart TD
A["Cola con todos los arcos"] --> B["Sacar un arco (Xi, Xj)"]
B --> C{"¿Algún valor de Xi sin soporte en Xj?"}
C -- "Sí" --> D["Eliminar ese valor del dominio de Xi"]
D --> E["Reencolar los arcos que apuntan a Xi"]
E --> B
C -- "No" --> F{"¿Queda algún arco en la cola?"}
F -- "Sí" --> B
F -- "No" --> G["Consistencia de arcos alcanzada"]
AC-3 solo recorta restricciones binarias, entre pares de variables.
Qué significa para vos si armás sistemas de asignación
Si trabajás en backend construyendo un configurador de productos, un armador de horarios académicos o un asignador de turnos, la decisión práctica es dónde meter la propagación: antes de la búsqueda, como filtro de entrada, o dentro de cada paso del backtracking, para que cada decisión parcial recorte inmediatamente los dominios de las variables que todavía faltan asignar. Implementar AC-3 a mano tiene sentido como ejercicio de aprendizaje o en un CSP chico y acotado, de pocas variables y restricciones binarias claras, como el Sudoku del ejemplo.
Para un problema de escala real (cientos de variables, restricciones de más de dos variables, límites de tiempo de cómputo) conviene usar un solver maduro en vez de reescribir AC-3: Google ofrece CP-SAT dentro de OR-Tools, un solver que combina métodos de SAT y CP para problemas de satisfacción de restricciones (developers.google.com/optimization/cp), y ya trae propagación de restricciones, heurísticas de búsqueda y paralelismo integrados.
Lo que el resumen de arXiv no destaca
El abstract del paper de Apt describe AC-3 como un caso particular, no como el tema central. El objetivo declarado es más ambicioso: usando las nociones de conmutatividad y semi-conmutatividad, el paper muestra que AC-3 y otros tres algoritmos clásicos de propagación (PC-2, DAC y DPC) son instancias de un único algoritmo genérico (arxiv.org/abs/cs/9909009v1). Es decir que la misma idea de ir sacando arcos de una cola y revisarlos sirve tanto para consistencia de arcos (AC-3) como para consistencia de camino (PC-2) o para las versiones direccionales DAC y DPC, cambiando solo qué propiedad se verifica en cada revisión.
AC-3 frente a otras formas de propagar o evitar restricciones
AC-3 no es la única manera de recortar un espacio de búsqueda antes o durante el backtracking. Tres alternativas conocidas resuelven el mismo problema con distintos compromisos:
TécnicaQué garantizaCuándo se aplicaCosto relativoAC-3Consistencia de arcos: cada valor que queda tiene soporte en cada variable vecinaAntes de buscar, como preprocesamiento, o repetido en cada nodo del backtrackingBajo frente a PC-2; solo mira pares de variablesPC-2Consistencia de camino: también valida tríos de variables, más fuerte que AC-3CSPs donde las restricciones binarias no alcanzan a detectar todas las inconsistenciasMás alto; revisa combinaciones de tres variables en vez de dosForward checkingRevisa solo las variables todavía sin asignar frente a la última decisión tomadaDentro del backtracking, en cada paso de la búsquedaMás barato que AC-3 por paso, pero propaga menosOR-Tools CP-SATCombina propagación, heurísticas de búsqueda y paralelismo en un solver completoCSPs de escala industrial con cientos o miles de variablesMayor, pero no hay que implementarlo: es una librería lista para usarEl paper de Apt unifica AC-3, PC-2, DAC y DPC en 1999.
Cuándo AC-3 no alcanza
AC-3 solo entiende restricciones binarias, las que conectan exactamente dos variables. Una restricción como la de que los nueve números de un cuadro de Sudoku tienen que ser todos distintos involucra a nueve variables a la vez, no a un par, así que para usarla con AC-3 hay que descomponerla primero en restricciones binarias entre cada pareja de casillas del cuadro. Esa descomposición es directa en Sudoku, pero en CSPs con restricciones genuinamente de más de dos variables, como buena parte de los problemas de asignación de recursos compartidos, complica la implementación o pierde parte de la información original.
Tampoco resuelve el CSP por sí solo. Alcanzar consistencia de arcos reduce los dominios, pero no garantiza que exista una asignación completa válida: todavía hace falta un algoritmo de búsqueda, normalmente backtracking, para terminar de elegir un valor por variable. Y cuantas más variables y valores por dominio tenga el problema, más arcos hay que revisar y más veces se repite cada revisión cuando los dominios se actualizan, así que el beneficio de aplicar AC-3 depende de cuánto efectivamente recorte: en un CSP con restricciones muy sueltas, el tiempo que toma correrlo puede no compensar lo poco que reduce.
Preguntas frecuentes
¿AC-3 resuelve un Sudoku por sí solo?
No. Reduce los dominios de las casillas vacías eliminando números que ya no tienen ningún lugar válido, pero normalmente deja más de un valor posible por casilla. La elección final de qué número va en cada casilla la hace un algoritmo de búsqueda, como backtracking, usando los dominios ya recortados por AC-3.
¿Qué es un arco en AC-3?
Un par ordenado de variables conectadas por una restricción, por ejemplo (Casilla A, Casilla B). El algoritmo revisa cada arco en una dirección: al revisar (A, B) comprueba que cada valor de A tenga un compañero compatible en B, y por separado hay que revisar (B, A) para lo mismo en sentido inverso.
¿Sirve para restricciones que involucran más de dos variables?
No directamente. AC-3 trabaja con restricciones binarias. Para usarlo con restricciones de tres o más variables hay que descomponerlas antes en restricciones binarias equivalentes, lo que no siempre es simple ni gratis en tiempo de cómputo.
Referencias
- The Rough Guide to Constraint Propagation (Apt, 1999): formaliza AC-3, PC-2, DAC y DPC como instancias de un único algoritmo genérico de propagación.- Apt, cs.AI/9811024: el paper anterior del mismo autor que The Rough Guide to Constraint Propagation extiende y simplifica.- Google OR-Tools, CP-SAT Solver: documentación oficial del solver de restricciones que Google mantiene, enfocado en factibilidad y restricciones antes que en optimización.- python-constraint: librería open source en Python que implementa AC-3 y backtracking para CSPs chicos y medianos.
Seguimos el tema en @programacion.
來源:DEV Community · dev.to