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 algoritmos AC anteriores a menudo se consideran demasiado ineficientes, y muchos de los últimos son difíciles de implementar, por lo que AC-3 es el que se enseña y se usa con más frecuencia en solucionadores de restricciones muy simples.
El algoritmo
AC-3 opera sobre restricciones , variables y dominios de las variables (alcances). 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 puede verse como un gráfico dirigido , donde los nodos son las variables del problema, con aristas o arcos entre variables que están relacionadas por restricciones simétricas, donde cada arco en la lista de trabajo representa una restricción que debe comprobarse la coherencia . AC-3 procede examinando los arcos entre pares de variables ( x , y ). Se elimina esos valores del dominio de x que no sean compatibles con las restricciones entre x y y . El algoritmo mantiene una colección de arcos que aún no se han verificado; cuando el dominio de una variable tiene valores eliminados, 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, aquí hay 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 es 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 restricción real que representa este problema debe contener dos bordes entre X e Y, ya que C2 no está dirigido, pero la representación del gráfico que utiliza AC-3 está dirigida.
Lo hace quitando 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 implicados por 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:
Aporte: 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 cumplirse Un conjunto de restricciones binarias R2 (x, y) sobre las variables xey que deben cumplirse Producción: Dominios consistentes en Arc para cada variable. function ac3 (X, D, R1, R2) // Los dominios iniciales se hacen consistentes con las restricciones unarias. para cada x en X D (x): = {vx en D (x) | vx satisface R1 (x)} // 'lista de trabajo' contiene todos los arcos que deseamos que sean 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 el fallo si no lista de trabajo: = lista de trabajo + {(z, x) | z! = y y existe una relación R2 (x, z) o una relación R2 (z, x)} mientras que la lista de trabajo no está vacía función arc-reduce (x, y) bool change = falso para cada vx en D (x) encontrar 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 cambio: = verdadero } devolver cambio
El algoritmo tiene una complejidad temporal en el peor de los casos de O ( ed 3 ) y una complejidad espacial de O ( e ), donde e es el número de arcos yd es el tamaño del dominio más grande.
Referencias
- AK Mackworth. Coherencia en las redes de relaciones . Inteligencia artificial , 8: 99-118, 1977.
- Stuart Russel y Peter Norvig. Inteligencia artificial: un enfoque moderno , 202-233, 2003.