Reconfiguración de tokens

En la teoría de la complejidad computacional y la combinatoria , el problema de reconfiguración de tokens es un problema de reconfiguración en un gráfico con un estado inicial y deseado para los tokens.

Dado un gráfico , un estado inicial de tokens se define por un subconjunto de los vértices del gráfico; sea . Mover un token de vértice a vértice es válido si y están unidos por una ruta en que no contiene ningún otro token; tenga en cuenta que la distancia recorrida dentro del gráfico es intrascendente y mover un token a través de múltiples aristas secuencialmente se considera un solo movimiento. Un estado final deseado se define como otro subconjunto . El objetivo es minimizar la cantidad de movimientos válidos para alcanzar el estado final desde el estado inicial. ^[1] ${\estilo de visualización G}$ $V\subconjunto V(G)$ $n=|V|$ $estilo de visualización v_{1}$ $estilo de visualización v_{2}$ $estilo de visualización v_{1}$ $estilo de visualización v_{2}$ ${\estilo de visualización G}$ $V'\subconjunto V(G)$

Motivación

El problema está motivado por los llamados rompecabezas deslizantes , que de hecho son una variante de este problema, a menudo restringidos a gráficos de cuadrícula rectangular sin agujeros. El rompecabezas más famoso de este tipo, el rompecabezas 15, es una variante de este problema en un gráfico de cuadrícula de 4 por 4 tal que . Una diferencia clave entre los rompecabezas de bloques deslizantes y el problema de reconfiguración de fichas es que en el problema de reconfiguración de fichas original, las fichas son indistinguibles. Como resultado, si el gráfico está conectado, el problema de reconfiguración de fichas siempre es solucionable; este no es necesariamente el caso de los rompecabezas de bloques deslizantes. $n=|V(G)|-1$

Complejidad

Calinescu, Dumitrescu y Pach han mostrado varios resultados relacionados con la optimización y aproximación de este problema en varios tipos de gráficos. ^[2]

Mejoramiento

En primer lugar, reduciendo al caso de los árboles, siempre hay una solución en , como máximo, un movimiento por ficha. Además, se puede encontrar una solución óptima en un tiempo lineal en el tamaño del árbol. Claramente, el primer resultado se extiende a grafos arbitrarios; el segundo, no. ${\estilo de visualización n}$

Un bosquejo del algoritmo óptimo para árboles es el siguiente. Primero, obtenemos un algoritmo que mueve cada nodo exactamente una vez, lo que puede no ser óptimo. Hazlo recursivamente: considera cualquier hoja del árbol más pequeño en el grafo que contiene tanto el conjunto inicial como el deseado. Si una hoja de este árbol está en ambos, elimínala y realiza una recursión hacia abajo. Si una hoja está solo en el conjunto inicial, encuentra un camino desde ella hasta un vértice en el conjunto deseado que no pase por ningún otro vértice en el conjunto deseado. Elimina este camino (será el último movimiento) y realiza una recursión hacia abajo. El otro caso, donde la hoja está solo en el conjunto deseado, es simétrico. Para extender a un algoritmo que logre el óptimo, considera cualquier token en los conjuntos inicial y deseado. Si eliminarlo dividiría el grafo en subárboles, todos los cuales tienen la misma cantidad de elementos de los conjuntos inicial y deseado, hazlo y realiza una recursión. Si no existe tal token, entonces cada token debe moverse exactamente una vez, y por lo tanto la solución que mueve todos los tokens exactamente una vez debe ser óptima.

Mientras que el algoritmo para encontrar el óptimo en árboles es de tiempo lineal, encontrar el óptimo para grafos generales es NP-completo, un salto en dificultad. Está en NP; el certificado es una secuencia de movimientos, que es como máximo de tamaño lineal, por lo que queda por demostrar que el problema también es NP-difícil. Esto se hace mediante reducción a partir del conjunto cover .

Consideremos un caso de cobertura de conjunto, en el que deseamos cubrir todos los elementos de un universo utilizando subconjuntos de la cantidad mínima de subconjuntos. Construyamos un gráfico de la siguiente manera: $v_{1},v_{2},\ldots ,v_{n}$ ${\estilo de visualización U}$ $S_{1},S_{2},\ldots ,S_{m}$ ${\estilo de visualización U}$

Crea un vértice para cada uno de los elementos del universo y cada uno de los subconjuntos. Conecta un vértice de un subconjunto a un vértice de un elemento si el subconjunto contiene ese elemento. Crea un camino largo de tamaño , y une un extremo a cada vértice del subconjunto. El conjunto inicial es el camino agregado más cada vértice del subconjunto, y el conjunto final es cada vértice del subconjunto más cada vértice del elemento. ${\estilo de visualización n}$

Para ver por qué esto es una reducción, considere la selección de qué tokens de vértice de subconjunto mover. Claramente, debemos abrir caminos hacia cada uno de los vértices de los elementos, y lo hacemos moviendo algunos de los tokens de vértice de subconjunto. Después de hacer esto, cada token en el camino largo debe moverse una vez. Por lo tanto, el costo óptimo es igual al número de subconjuntos seleccionados más el número de elementos (el último de los cuales es notablemente una constante). Por lo tanto, tenemos una reducción de tiempo polinomial desde la cobertura del conjunto, que es NP-completa, hasta la reconfiguración de tokens. Por lo tanto, la reconfiguración de tokens también es NP-completa en grafos generales.

Aproximación

El problema de reconfiguración de tokens es APX-completo , lo que significa que, en cierto sentido, es tan difícil de aproximar como cualquier problema que tenga un algoritmo de aproximación de factor constante . La reducción es la misma que la anterior, a partir de la cobertura de conjuntos. Sin embargo, el problema de la cobertura de conjuntos está restringido a subconjuntos de tamaño máximo 3, lo que es un problema APX-difícil. ^[3]

Utilizando exactamente la misma estructura que la anterior, obtenemos una L-reducción , ya que la distancia de cualquier solución desde el óptimo es igual entre la instancia de cobertura del conjunto y el problema de reconfiguración de tokens transformado. El único cambio es la adición del número de elementos en el universo. Además, el óptimo de cobertura del conjunto es al menos 1/3 del número de elementos, debido al tamaño del subconjunto acotado. Por lo tanto, las constantes de la L-reducción son . $\alpha = 1/4,\beta = 1$

De hecho, se puede modificar la reducción para que funcione también en la reconfiguración de tokens etiquetados. Para ello, se adjunta un nuevo vértice a cada uno de los vértices del subconjunto, que no es ni un vértice inicial ni deseado. Se etiquetan los vértices en la ruta larga del 1 al , y se hace lo mismo con los vértices del elemento. Ahora, la solución consiste en "hacer a un lado" cada token de vértice del subconjunto elegido, colocar correctamente los vértices etiquetados desde la ruta y devolver los tokens de vértice del subconjunto a las ubicaciones iniciales. Esta es una L-reducción con . ${\estilo de visualización n}$ $\alpha = 1/5,\beta = 2$

Calinescu, Dumitrescu y Pach también han demostrado que existe una aproximación 3 para la reconfiguración de tokens no etiquetados, por lo que el problema también está en APX y, por lo tanto, es APX-completo. La prueba es mucho más complicada y se omite aquí.

Referencias

^ Demaine, Erik (otoño de 2014). "Límites inferiores algorítmicos: diversión con las pruebas de dureza, notas de la clase 11" (PDF) .
^ Calinescu, Gruia; Dumitrescu, Adrian; Pach, János (2006). "Reconfiguraciones en grafos y cuadrículas". LATIN 2006: Informática teórica . Apuntes de clase en informática. Vol. 3887. págs. 262–273. doi :10.1007/11682462_27. ISBN 978-3-540-32755-4. {{cite book}}: |journal=ignorado ( ayuda )
^ Papadimitriou, Christos H.; Yannakakis, Mihailis (1991). "Optimización, aproximación y clases de complejidad". Revista de Ciencias de la Computación y de Sistemas . 43 (3): 425–440. doi :10.1016/0022-0000(91)90023-X.