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 tokens.
Dado un gráfico , un estado inicial de tokens está definido por un subconjunto de los vértices del gráfico; dejar. Mover una ficha desde el vértice al vértice es válido si y están unidos por un camino en que no contiene ningún otro token; tenga en cuenta que la distancia recorrida dentro del gráfico es intrascendente, y mover una ficha a través de múltiples bordes de forma secuencial se considera un solo movimiento. Un estado final deseado se define como otro subconjunto. El objetivo es minimizar el número de movimientos válidos para alcanzar el estado final desde el estado inicial. [1]
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 rectangulares sin agujeros. El rompecabezas de este tipo más famoso, el de los 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 del token es que en el problema de reconfiguración del token original, los tokens son indistinguibles. Como resultado, si el gráfico está conectado, el problema de reconfiguración del token siempre se puede resolver; este no es necesariamente el caso de los rompecabezas de bloques deslizantes.
Complejidad
Calinescu, Dumitrescu y Pach han mostrado varios resultados con respecto a 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 movimientos, con un máximo de un movimiento por ficha. Además, se puede encontrar una solución óptima en el tiempo lineal en el tamaño del árbol. Claramente, el primer resultado se extiende a gráficos arbitrarios; el último no lo hace.
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. Haga esto de forma recursiva: considere cualquier hoja del árbol más pequeño en el gráfico que contiene tanto el conjunto inicial como el deseado. Si una hoja de este árbol está en ambos, retírela y vuelva a bajar. Si una hoja está solo en el conjunto inicial, busque una ruta desde ella hasta un vértice en el conjunto deseado que no pase por ningún otro vértice en el conjunto deseado. Elimina esta ruta (será el último movimiento) y vuelve hacia abajo. El otro caso, donde la hoja está en el conjunto deseado solamente, es simétrico. Para extender a un algoritmo que logre el óptimo, considere cualquier token tanto en el conjunto inicial como en el deseado. Si eliminarlo dividiría el gráfico en subárboles, todos los cuales tienen el mismo número de elementos de los conjuntos inicial y deseado, hágalo y repita. Si no existe tal token, entonces cada token debe moverse exactamente una vez, por lo que la solución que mueve todos los tokens exactamente una vez debe ser óptima.
Si bien el algoritmo para encontrar el óptimo en los árboles es el tiempo lineal, encontrar el óptimo para los gráficos generales es NP-completo, un salto en la dificultad. Está en NP; el certificado es una secuencia de movimientos, que tiene como máximo un tamaño lineal, por lo que queda por demostrar que el problema también es NP-hard. Esto se hace mediante la reducción de la cobertura del conjunto .
Considere una instancia de cobertura de conjunto, donde deseamos cubrir todos los elementos en un universo usando subconjuntos de utilizando el número mínimo de subconjuntos. Construya una gráfica de la siguiente manera:
Haz un vértice para cada uno de los elementos del universo y cada uno de los subconjuntos. Conecte un vértice de subconjunto a un vértice de elemento si el subconjunto contiene ese elemento. Crea un largo camino de tamañoy adjunte un extremo a cada vértice de subconjunto. El conjunto inicial es la ruta agregada más cada vértice de subconjunto, y el conjunto final es cada vértice de subconjunto más cada vértice de elemento.
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 a cada uno de los vértices del elemento, y lo hacemos moviendo algunos de los tokens de vértice del subconjunto. Después de hacerlo, cada ficha del camino largo debe moverse una vez. Por tanto, el coste ó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). Así que tenemos una reducción de tiempo polinomial desde la cobertura del conjunto, que es NP-completo, hasta la reconfiguración del token. Por lo tanto, la reconfiguración de tokens también es NP-completa en gráficos generales.
Aproximación
El problema de reconfiguración del token 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, desde la cobertura del conjunto. Sin embargo, el problema de la cobertura del conjunto se limita a subconjuntos de un tamaño máximo de 3, que es un problema difícil de APX. [3]
Usando exactamente la misma estructura que la anterior, obtenemos una reducción L , ya que la distancia de cualquier solución al óptimo es igual entre la instancia de cobertura establecida y el problema de reconfiguración del token transformado. El único cambio es la suma de la cantidad de elementos del universo. Además, la cobertura óptima 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 reducción L son.
De hecho, se puede modificar la reducción para que funcione también para la reconfiguración del token etiquetado. Para hacerlo, adjunte un nuevo vértice a cada uno de los vértices del subconjunto, que no es un vértice inicial ni deseado. Rotula los vértices del camino largo del 1 aly haga lo mismo con los vértices del elemento. Ahora, la solución consiste en 'mover a un lado' cada token de vértice de subconjunto elegido, colocar correctamente los vértices etiquetados de la ruta y devolver los tokens de vértice del subconjunto a las ubicaciones iniciales. Esta es una reducción en L con.
Calinescu, Dumitrescu y Pach también han demostrado que existe una aproximación 3 para la reconfiguración de tokens sin etiquetar, por lo que el problema también está en APX y, por lo tanto, en APX completo. La prueba es mucho más complicada y aquí se omite.
Referencias
- ^ Demaine, Erik (otoño de 2014). "Límites inferiores algorítmicos: diversión con las notas de la lección 11 de pruebas de dureza" (PDF) .
- ^ Calinescu, Gruia; Dumitrescu, Adrian; Pach, János (2006). Reconfiguraciones en gráficos y cuadrículas . LATIN 2006: Informática Teórica, VII Simposio Latinoamericano, Valdivia, Chile, 20 al 24 de marzo de 2006, Actas . Apuntes de conferencias en Ciencias de la Computación. 3887 . págs. 262-273. doi : 10.1007 / 11682462_27 . ISBN 978-3-540-32755-4.
- ^ Papadimitriou, Christos H .; Yannakakis, Mihailis (1991). "Clases de optimización, aproximación y complejidad" . Revista de Ciencias de la Computación y Sistemas . 43 (3): 425–440. doi : 10.1016 / 0022-0000 (91) 90023-X .