El algoritmo de mapa de diferencias es un algoritmo de búsqueda para problemas generales de satisfacción de restricciones . Es un meta-algoritmo en el sentido de que se construye a partir de algoritmos más básicos que realizan proyecciones sobre conjuntos de restricciones . Desde una perspectiva matemática, el algoritmo de mapa de diferencias es un sistema dinámico basado en un mapa del espacio euclidiano . Las soluciones se codifican como puntos fijos del mapeo.
![](http://wikiimg.tojsiabtv.com/wikipedia/en/thumb/6/69/Iterations_0%2C_100%2C_200%2C_300_and_400_in_difference-map_reconstruction_of_grayscale_image_from_Fourier_transform_modulus.png/220px-Iterations_0%2C_100%2C_200%2C_300_and_400_in_difference-map_reconstruction_of_grayscale_image_from_Fourier_transform_modulus.png)
Aunque originalmente se concibió como un método general para resolver el problema de fase , el algoritmo de mapa de diferencias se ha utilizado para el problema de satisfacibilidad booleano , la predicción de la estructura de la proteína , los números de Ramsey , las ecuaciones diofánticas y el Sudoku , [1] así como la esfera y el disco. -Problemas de embalaje. [2] Dado que estas aplicaciones incluyen problemas NP-completos , el alcance del mapa de diferencias es el de un algoritmo incompleto . Mientras que los algoritmos incompletos pueden verificar soluciones de manera eficiente (una vez que se encuentra un candidato), no pueden probar que no existe una solución.
El algoritmo de mapa de diferencias es una generalización de dos métodos iterativos : el algoritmo híbrido de entrada y salida (HIO) de Fienup para la recuperación de fase [3] y el algoritmo de Douglas-Rachford [4] para la optimización convexa . Los métodos iterativos, en general, tienen una larga historia en recuperación de fase y optimización convexa. El uso de este estilo de algoritmo para problemas difíciles no convexos es un desarrollo más reciente.
Algoritmo
El problema a resolver debe formularse primero como un problema de intersección de conjuntos en el espacio euclidiano: encuentre un en la intersección de conjuntos y . Otro requisito previo es la implementación de las proyecciones. y que, dado un punto de entrada arbitrario , devuelve un punto en el conjunto de restricciones o que está más cerca de . El mapeo da una iteración del algoritmo:
El verdadero parámetro no debe ser igual a 0 pero puede tener cualquiera de los dos signos; los valores óptimos dependen de la aplicación y se determinan mediante experimentación. Como primera suposición, la elección (o ) se recomienda porque reduce el número de cálculos de proyección por iteración:
Un punto es un punto fijo del mapa precisamente cuando . Dado que el lado izquierdo es un elemento de y el RHS es un elemento de , la igualdad implica que hemos encontrado un elemento común a los dos conjuntos de restricciones. Tenga en cuenta que el punto fijo en sí mismo no tiene por qué pertenecer a ninguno o . El conjunto de puntos fijos normalmente tendrá una dimensión mucho mayor que el conjunto de soluciones.
El progreso del algoritmo se puede monitorear inspeccionando la norma de la diferencia de las dos proyecciones:
- .
Cuando esto desaparece, se ha encontrado un punto común a ambos conjuntos de restricciones y se puede terminar el algoritmo.
Ejemplo: satisfacibilidad lógica
Los algoritmos incompletos, como la búsqueda local estocástica , se utilizan ampliamente para encontrar asignaciones de verdad satisfactorias a fórmulas booleanas. Como ejemplo de resolución de una instancia de 2-SAT con el algoritmo de mapa de diferencias, considere la siguiente fórmula (~ indica NO):
- ( q 1 o q 2 ) y (~ q 1 o q 3 ) y (~ q 2 o ~ q 3 ) y ( q 1 o ~ q 2 )
A cada uno de los ocho literales en esta fórmula le asignamos una variable real en un espacio euclidiano de ocho dimensiones. La estructura de la fórmula 2-SAT se puede recuperar cuando estas variables se ordenan en una tabla:
x 11 x 12 ( x 21 ) x 22 ( x 31 ) ( x 32 ) x 41 ( x 42 )
Las filas son las cláusulas de la fórmula 2-SAT y los literales correspondientes a la misma variable booleana se organizan en columnas, con la negación indicada entre paréntesis. Por ejemplo, las variables reales x 11 , x 21 y x 41 corresponden a la misma variable booleana ( q 1 ) o su negación, y se denominan réplicas . Es conveniente asociar los valores 1 y -1 con VERDADERO y FALSO en lugar de los tradicionales 1 y 0. Con esta convención, la compatibilidad entre las réplicas toma la forma de las siguientes ecuaciones lineales:
- x 11 = - x 21 = x 41
- x 12 = - x 31 = - x 42
- x 22 = - x 32
El subespacio lineal donde se satisfacen estas ecuaciones es uno de los espacios de restricción, digamos A , utilizado por el mapa de diferencias. Para proyectar a esta restricción, reemplazamos cada réplica por el promedio de réplicas firmadas, o su negativo:
- a 1 = ( x 11 - x 21 + x 41 ) / 3
- x 11 → a 1 x 21 → - a 1 x 41 → a 1
La segunda restricción del mapa de diferencias se aplica a las filas de la tabla, las cláusulas. En una asignación satisfactoria, a las dos variables de cada fila se les deben asignar los valores (1, 1), (1, -1) o (-1, 1). El conjunto de restricciones correspondiente, B , es, por tanto, un conjunto de 3 4 = 81 puntos. Al proyectar esta restricción, se aplica la siguiente operación a cada fila. Primero, los dos valores reales se redondean a 1 o -1; entonces, si el resultado es (-1, -1), el mayor de los dos valores originales se reemplaza por 1. Ejemplos:
- (-2, 1,2) → (-1, 1)
- (-.2, -.8) → (1, -1)
Es un ejercicio sencillo comprobar que las dos operaciones de proyección descritas minimizan la distancia euclidiana entre los valores de entrada y salida. Además, si el algoritmo tiene éxito en encontrar un punto x que se encuentra en ambos conjuntos de restricciones, entonces sabemos que (i) las cláusulas asociadas con x son todas VERDADERAS , y (ii) las asignaciones a las réplicas son consistentes con una asignación de verdad a las variables booleanas originales.
Para ejecutar el algoritmo, primero se genera un punto inicial x 0 , digamos
-0,5 -0,8 (-0,4) -0,6 (0,3) (-0,8) 0,5 (0,1)
Usando β = 1, el siguiente paso es calcular P B ( x 0 ):
1 -1 (1) -1 (1) (-1) 1 (1)
A esto le sigue 2 P B ( x 0 ) - x 0 ,
2.5 -1,2 (2,4) -1,4 (1,7) (-1,2) 1,5 (1,9)
y luego proyectado sobre la otra restricción, P A (2 P B ( x 0 ) - x 0 ):
0.53333 -1,6 (-0,53333) -0,1 (1,6) (0,1) 0.53333 (1,6)
Incrementar x 0 por la diferencia de las dos proyecciones da la primera iteración del mapa de diferencias, D ( x 0 ) = x 1 :
-0,96666 -1,4 (-1.93333) 0,3 (0,9) (0,3) 0.03333 (0,7)
Aquí está la segunda iteración, D ( x 1 ) = x 2 :
-0,3 -1,4 (-2,6) -0,7 (0,9) (-0,7) 0,7 (0,7)
Este es un punto fijo: D ( x 2 ) = x 2 . La iteración no se modifica porque las dos proyecciones coinciden. Desde P B ( x 2 ),
1 -1 (-1) 1 (1) (-1) 1 (1)
podemos leer la asignación de verdad satisfactoria: q 1 = VERDADERO , q 2 = FALSO , q 3 = VERDADERO .
Dinámica caótica
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/f/f6/Time_series_of_norm_of_difference-map_increment_%CE%94%2C_during_solving_random_3-SAT_instance.png/220px-Time_series_of_norm_of_difference-map_increment_%CE%94%2C_during_solving_random_3-SAT_instance.png)
En el ejemplo simple de 2-SAT anterior, la norma del incremento del mapa de diferencias Δ disminuyó monótonamente a cero en tres iteraciones. Esto contrasta el comportamiento de Δ cuando al mapa de diferencias se le da una instancia dura de 3-SAT , donde fluctúa fuertemente antes del descubrimiento del punto fijo. Como sistema dinámico, se cree que el mapa de diferencias es caótico y que el espacio que se busca es un atractor extraño .
Recuperación de fase
![](http://wikiimg.tojsiabtv.com/wikipedia/en/thumb/8/8e/Diffraction_data.png/220px-Diffraction_data.png)
En la recuperación de fase, una señal o imagen se reconstruye a partir del módulo (valor absoluto, magnitud) de su transformada discreta de Fourier . Por ejemplo, la fuente de los datos del módulo puede ser el patrón de difracción de Fraunhofer que se forma cuando un objeto se ilumina con luz coherente .
La proyección a la Fourier módulo de restricción, por ejemplo P A , se lleva a cabo calculando primero la transformada discreta de Fourier de la señal o imagen, cambiar la escala de los módulos de acuerdo con los datos, y luego transformar de manera inversa el resultado. Esta es una proyección, en el sentido de que la distancia euclidiana a la restricción se minimiza, porque (i) la transformada discreta de Fourier, como transformación unitaria , conserva la distancia, y (ii) reescalar el módulo (sin modificar la fase) es la el cambio más pequeño que se da cuenta de la restricción del módulo.
Para recuperar las fases desconocidos de la transformada de Fourier del mapa de diferencias se basa en la proyección de otra condición, P B . Esto puede tomar varias formas, ya que se puede saber que el objeto que se está reconstruyendo es positivo, tiene un soporte acotado , etc. En la reconstrucción de la imagen de la superficie, por ejemplo, el efecto de la proyección P B fue anular todos los valores fuera de un soporte rectangular, y también para anular todos los valores negativos dentro del soporte.
enlaces externos
- Sudoku Solver : un solucionador de Sudoku basado en el algoritmo del mapa de diferencias.
Notas
- ^ Elser, V .; Rankenburg, I .; Thibault, P. (9 de enero de 2007). "Búsqueda con mapas iterados" . Actas de la Academia Nacional de Ciencias . 104 (2): 418–423. doi : 10.1073 / pnas.0606359104 . PMC 1766399 . PMID 17202267 .
- ^ Gravel, Simon; Elser, Veit (22 de septiembre de 2008). "Dividir y concurrir: un enfoque general para la satisfacción de la restricción". Revisión E física . 78 (3): 036706. arXiv : 0801.0222 . Código Bibliográfico : 2008PhRvE..78c6706G . doi : 10.1103 / PhysRevE.78.036706 . PMID 18851188 . S2CID 27814394 .
- ^ Fienup, JR (1 de agosto de 1982). "Algoritmos de recuperación de fase: una comparación". Óptica aplicada . 21 (15): 2758. Código Bibliográfico : 1982ApOpt..21.2758F . doi : 10.1364 / AO.21.002758 . PMID 20396114 . S2CID 10777701 .
- ^ Bauschke, Heinz H .; Combettes, Patrick L .; Luke, D. Russell (1 de julio de 2002). "Recuperación de fase, algoritmo de reducción de errores y variantes de Fienup: una vista desde la optimización convexa". Revista de la Sociedad Americana de Óptica A . 19 (7): 1334. Código Bibliográfico : 2002JOSAA..19.1334B . CiteSeerX 10.1.1.75.1070 . doi : 10.1364 / JOSAA.19.001334 . PMID 12095200 .