Algoritmo de mapa de diferencias

El algoritmo de mapa de diferencias es un algoritmo de búsqueda para problemas generales de satisfacción de restricciones . Es un metaalgoritmo, ya 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 una aplicación del espacio euclidiano . Las soluciones se codifican como puntos fijos de dicha aplicación.

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 booleana , la predicción de la estructura de proteínas , los números de Ramsey , las ecuaciones diofánticas y el Sudoku , ^{[ 1 ]} así como los problemas de empaquetamiento de esferas y discos. ^{[ 2 ]} Dado que estas aplicaciones incluyen problemas NP-completos , el alcance del mapa de diferencias es el de un algoritmo incompleto . Si bien los algoritmos incompletos pueden verificar eficientemente las soluciones (una vez que se encuentra un candidato), no pueden probar que una solución no existe.

El algoritmo de mapa de diferencias es una generalización de dos métodos iterativos : el algoritmo de entrada-salida híbrida (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 trayectoria en la recuperación de fase y la optimización convexa. El uso de este tipo de algoritmo para problemas difíciles y no convexos es un desarrollo más reciente.

El problema a resolver debe formularse primero como un problema de intersección de conjuntos en el espacio euclidiano: encontrar un${\displaystyle x}$en la intersección de conjuntos${\displaystyle A}$y${\displaystyle B}$Otro requisito previo es la implementación de las proyecciones.${\displaystyle P_{A}}$y${\displaystyle P_{B}}$que, dado un punto de entrada arbitrario${\displaystyle x}$, devuelve un punto en el conjunto de restricciones${\displaystyle A}$o${\displaystyle B}$que está más cerca de${\displaystyle x}$Una iteración del algoritmo viene dada por la siguiente función:

${\displaystyle {\begin{aligned}x\mapsto D(x)&=x+\beta \left[P_{A}\left(f_{B}(x)\right)-P_{B}\left(f_{A}(x)\right)\right],\\f_{A}(x)&=P_{A}(x)-{\frac {1}{\beta }}\left(P_{A}(x)-x\right),\\f_{B}(x)&=P_{B}(x)+{\frac {1}{\beta }}\left(P_{B}(x)-x\right)\end{aligned}}}$

El parámetro real${\displaystyle \beta }$No debe ser igual a 0, pero puede tener cualquier signo; los valores óptimos dependen de la aplicación y se determinan mediante experimentación. Como primera suposición, la elección${\displaystyle \beta =1}$(o${\displaystyle \beta =-1}$) se recomienda porque reduce el número de cálculos de proyección por iteración:

${\displaystyle D(x)=x+P_{A}\left(2P_{B}(x)-x\right)-P_{B}(x)}$

Un punto ${\displaystyle x}$es un punto fijo del mapa${\displaystyle x\mapsto D(x)}$precisamente cuando${\displaystyle P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)}$. Dado que el lado izquierdo es un elemento de${\displaystyle A}$y el lado derecho es un elemento de${\displaystyle B}$La igualdad implica que hemos encontrado un elemento común a los dos conjuntos de restricciones. Nótese que el punto fijo${\displaystyle x}$No es necesario que pertenezca a ninguno de los dos.${\displaystyle A}$o${\displaystyle B}$El conjunto de puntos fijos tendrá, por lo general, 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:

${\displaystyle \Delta =\left|P_{A}\left(f_{B}(x)\right)-P_{B}\left(f_{A}(x)\right)\right|}$.

Cuando esto desaparece, se ha encontrado un punto común a ambos conjuntos de restricciones y el algoritmo puede finalizarse.

Los algoritmos incompletos, como la búsqueda local estocástica , se utilizan ampliamente para encontrar asignaciones de verdad satisfactorias para fórmulas booleanas. Como ejemplo de cómo resolver una instancia de 2-SAT con el algoritmo de mapa de diferencias, considérese la siguiente fórmula (~ indica NO):

( q ₁ o q ₂ ) y (~ q ₁ o q ₃ ) y (~ q ₂ o ~ q ₃ ) y ( q ₁ o ~ q ₂ )

A cada uno de los ocho literales de 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 organizan en una tabla:

Las filas representan 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 por paréntesis. Por ejemplo, las variables reales x₁₁, x₂₁ y x₄₁ _corresponden a la misma variable booleana ₍ q₁ ) o a 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 se expresa mediante las siguientes ecuaciones lineales:

x ₁₁ = - x ₂₁ = x ₄₁

x ₁₂ = - x ₃₁ = - x ₄₂

x ₂₂ = - x ₃₂

El subespacio lineal donde se satisfacen estas ecuaciones es uno de los espacios de restricciones, digamos A , utilizado por el mapa de diferencias. Para proyectar a esta restricción, reemplazamos cada réplica por el promedio de réplicas con signo, o su negativo:

a ₁ = ( x ₁₁ - x ₂₁ + x ₄₁ ) / 3

x ₁₁ → a ₁ x ₂₁ → - a ₁ x ₄₁ → a ₁  

La segunda restricción del mapa de diferencias se aplica a las filas de la tabla, las cláusulas. En una asignación satisfactoria, las dos variables de cada fila deben tomar los valores (1, 1), (1, -1) o (-1, 1). El conjunto de restricciones correspondiente, B , es, por lo tanto, un conjunto de 3 ^{× 4} = 81 puntos. Al proyectar sobre esta restricción, se aplica la siguiente operación a cada fila. Primero, los dos valores reales se redondean a 1 o -1; luego, si el resultado es (-1, -1), el mayor de los dos valores originales se reemplaza por 1. Ejemplos:

(-0.2, 1.2) → (-1, 1)

(-0.2, -0.8) → (1, -1)

Es sencillo comprobar que ambas operaciones de proyección descritas minimizan la distancia euclidiana entre los valores de entrada y salida. Además, si el algoritmo logra encontrar un punto x que se encuentre dentro de ambos conjuntos de restricciones, entonces sabemos que (i) todas las cláusulas asociadas a x son 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 ₀ , por ejemplo

Usando β = 1, el siguiente paso es calcular P _B ( x ₀ )  :

A esto le sigue 2 P _B ( x ₀ ) - x ₀ ,

y luego proyectado sobre la otra restricción, P _A (2 P _B ( x ₀ ) - x ₀ )  :

Incrementar x ₀ por la diferencia de las dos proyecciones da la primera iteración del mapa de diferencias, D ( x ₀ ) = x ₁  :

Aquí está la segunda iteración, D ( x ₁ ) = x ₂  :

Este es un punto fijo: D ( x ₂ ) = x ₂ . La iteración no cambia porque las dos proyecciones coinciden. Desde P _B ( x ₂ ),

Podemos leer la asignación de verdad satisfactoria: q ₁ = VERDADERO , q ₂ = FALSO , q ₃ = VERDADERO .

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 con el comportamiento de Δ cuando al mapa de diferencias se le da una instancia difícil de 3-SAT , donde fluctúa fuertemente antes de descubrir el punto fijo. Como sistema dinámico, se cree que el mapa de diferencias es caótico y que el espacio que se está explorando es un atractor extraño .

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 restricción del módulo de Fourier, digamos P _A , se realiza calculando primero la transformada discreta de Fourier de la señal o imagen, reescalando los módulos para que coincidan con los datos y luego aplicando la transformada inversa al resultado. Esto es una proyección, en el sentido de que se minimiza la distancia euclidiana a la restricción, 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 el cambio más pequeño que cumple con la restricción del módulo.

Para recuperar las fases desconocidas de la transformada de Fourier, el mapa de diferencias se basa en la proyección a otra restricción, P _B . Esta puede adoptar diversas formas, ya que se sabe que el objeto que se está reconstruyendo es positivo, tiene un soporte acotado , etc. En la reconstrucción de la imagen de superficie, por ejemplo, el efecto de la proyección P _B fue anular todos los valores fuera de un soporte rectangular, y también anular todos los valores negativos dentro del soporte.

• Solucionador de Sudoku : un solucionador de Sudoku basado en el algoritmo de Mapa de Diferencias.