En el campo de la satisfacción de restricciones , el algoritmo AC-3 (abreviatura de Arc Consistency Algorithm #3) es uno de una serie de algoritmos utilizados para la solución de problemas de satisfacción de restricciones (o CSP). Fue desarrollado por Alan Mackworth en 1977. Los primeros algoritmos AC suelen considerarse demasiado ineficientes y muchos de los posteriores son difíciles de implementar, por lo que AC-3 es el que se enseña y se utiliza con más frecuencia en solucionadores de restricciones muy simples. El algoritmo AC-3 no debe confundirse con el algoritmo A3C de nombre similar en el aprendizaje automático. [1]
AC-3 opera sobre restricciones , variables y los dominios (ámbitos) de las variables. Una variable puede tomar cualquiera de varios valores discretos; el conjunto de valores para una variable en particular se conoce como su dominio . Una restricción es una relación que limita o restringe los valores que puede tener una variable. La restricción puede involucrar los valores de otras variables.
El estado actual del CSP durante el algoritmo se puede ver como un gráfico dirigido , donde los nodos son las variables del problema, con aristas o arcos entre las variables que están relacionadas por restricciones simétricas, donde cada arco en la lista de trabajo representa una restricción que necesita ser revisada para su consistencia . AC-3 procede examinando los arcos entre pares de variables ( x , y ). Elimina aquellos valores del dominio de x que no son consistentes con las restricciones entre x e y . El algoritmo mantiene una colección de arcos que aún deben ser revisados; cuando el dominio de una variable tiene algún valor eliminado, todos los arcos de restricciones que apuntan a esa variable podada (excepto el arco de la restricción actual) se agregan a la colección. Dado que los dominios de las variables son finitos y se elimina un arco o al menos un valor en cada paso, se garantiza que este algoritmo terminará .
A modo de ilustración, he aquí un ejemplo de un problema de restricción muy simple: X (una variable) tiene los valores posibles {0, 1, 2, 3, 4, 5}—el conjunto de estos valores son el dominio de X , o D( X ). La variable Y tiene el dominio D( Y ) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Junto con las restricciones C1 = " X debe ser par" y C2 = " X + Y debe ser igual a 4" tenemos un CSP que AC-3 puede resolver. Observe que el gráfico de restricciones real que representa este problema debe contener dos aristas entre X e Y ya que C2 no es dirigido pero la representación gráfica que utiliza AC-3 es dirigida.
AC-3 resuelve el problema eliminando primero los valores no pares del dominio de X como lo requiere C1 , dejando D( X ) = { 0, 2, 4 }. Luego examina los arcos entre X e Y implícitos en C2 . Solo los pares ( X = 0, Y = 4), ( X = 2, Y = 2) y ( X = 4, Y = 0) coinciden con la restricción C2 . AC-3 luego termina, con D( X ) = { 0, 2, 4} y D( Y ) = { 0, 2, 4}.
AC-3 se expresa en pseudocódigo de la siguiente manera:
Entrada: Un conjunto de variables X Un conjunto de dominios D(x) para cada variable x en X. D(x) contiene vx0, vx1... vxn, los posibles valores de x Un conjunto de restricciones unarias R1(x) sobre la variable x que deben satisfacerse Un conjunto de restricciones binarias R2(x, y) sobre las variables x e y que deben satisfacerse Producción: Dominios consistentes de arco para cada variable. función ac3(X, D, R1, R2) // Los dominios iniciales se hacen consistentes con restricciones unarias. para cada x en X D(x) := { vx en D(x) | vx satisface R1(x) } // 'worklist' contiene todos los arcos que deseamos probar si son consistentes o no. lista de trabajo := { (x, y) | existe una relación R2(x, y) o una relación R2(y, x) } hacer Seleccione cualquier arco (x, y) de la lista de trabajo lista de trabajo := lista de trabajo - (x, y) si arc-reduce (x, y) si D(x) está vacío devuelve falla de lo contrario worklist := worklist + { (z, x) | z != y y existe una relación R2(x, z) o una relación R2(z, x) } mientras la lista de trabajo no esté vacía función arc-reduce(x, y) bool cambio = falso para cada vx en D(x) Encuentra un valor vy en D(y) tal que vx y vy satisfagan la restricción R2(x, y) si no existe tal vy { D(x) := D(x) - vx cambiar := verdadero } devolver cambio
El algoritmo tiene una complejidad temporal de peor caso de O ( ed 3 ) y una complejidad espacial de O ( e ), donde e es el número de arcos y d es el tamaño del dominio más grande.