Algoritmo de intercambiabilidad

En informática , un algoritmo de intercambiabilidad es una técnica que se utiliza para resolver de forma más eficiente los problemas de satisfacción de restricciones (CSP). Un CSP es un problema matemático en el que los objetos, representados por variables, están sujetos a restricciones sobre los valores de dichas variables; el objetivo en un CSP es asignar valores a las variables que sean consistentes con las restricciones. Si dos variables A y B en un CSP pueden intercambiarse entre sí (es decir, A se reemplaza por B y B por A ) sin cambiar la naturaleza del problema ni sus soluciones, entonces A y B son variables intercambiables . Las variables intercambiables representan una simetría del CSP y, al explotar dicha simetría, se puede reducir el espacio de búsqueda de soluciones para un problema CSP. Por ejemplo, si se han probado soluciones con A = 1 y B = 2, entonces, por la simetría de intercambio, no es necesario investigar soluciones con B = 1 y A = 2.

El concepto de intercambiabilidad y el algoritmo de intercambiabilidad en problemas de satisfacción de restricciones fueron introducidos por primera vez por Eugene Freuder en 1991. ^{[ 1 ] [ 2 ]} El algoritmo de intercambiabilidad reduce el espacio de búsqueda de los algoritmos de búsqueda de retroceso , mejorando así la eficiencia de los problemas CSP NP-completos . ^{[ 3 ]}

Totalmente intercambiable

Un valor a para la variable v es completamente intercambiable con un valor b si y solo si toda solución en la que v = a sigue siendo una solución cuando se sustituye a por b y viceversa. ^{[ 2 ]}

Intercambiable de vecindario

Un valor a para la variable v es intercambiable en vecindad con el valor b si y solo si para cada restricción sobre v , los valores compatibles con v = a son exactamente aquellos compatibles con v = b. ^{[ 2 ]}

Totalmente sustituible

Un valor a para la variable v es completamente sustituible por el valor b si y solo si toda solución en la que v = a sigue siendo una solución cuando b se sustituye por a (pero no necesariamente a la inversa). ^{[ 2 ]}

Intercambiables dinámicamente

Un valor a para la variable v es dinámicamente intercambiable para b con respecto a un conjunto A de asignaciones de variables si y solo si son completamente intercambiables en el subproblema inducido por A. ^{[ 2 ]}

En el caso del algoritmo de vecindario intercambiable, si asignamos el límite del peor caso a cada bucle. Entonces, para n variables, que tienen como máximo d valores para una variable, entonces tenemos un límite de  : ${\displaystyle O(nd(nl)*d)=O(n^{2}d^{2})}$.

De manera similar, el análisis de complejidad del algoritmo de k -intercambiabilidad para el peor caso${\displaystyle O(n^{k-1})}$, con${\displaystyle (k-1)}$-tuplas de variables y${\displaystyle d^{k-1}}$, para${\displaystyle (k-1)}$-tuplas de valores, entonces el límite es  :${\displaystyle O(ndn^{kl}d^{k-1})=O(n^{k}d^{k})}$.

La figura muestra un ejemplo sencillo de coloración de grafos con colores que representan los vértices, de manera que no haya dos vértices unidos por una arista del mismo color. Se muestran los colores disponibles para cada vértice. Los colores amarillo, verde, marrón, rojo, azul y rosa representan el vértice Y y, por definición, son totalmente intercambiables. Por ejemplo, sustituir el verde por el granate en la solución naranja|X (naranja por X), verde|Y dará como resultado otra solución.

En Ciencias de la Computación, el algoritmo de intercambiabilidad se ha utilizado ampliamente en los campos de la inteligencia artificial , problemas de coloración de grafos , marcos de abstracción y adaptación de soluciones. ^{[ 2 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ]}