Complejidad de un problema de red de conmutación

17

Una red de conmutación (se inventa el nombre) se realiza con tres tipos de nodos:

  • un nodo de inicio
  • un nodo final
  • uno o más nodos Switch

El nodo del interruptor tiene 3 salidas: izquierda, arriba, derecha; tiene dos estados L y R y un estado objetivo TL o TR . Cada interruptor se puede recorrer con las siguientes reglas:

  • siempre de izquierda a arriba; el estado del interruptor cambia a L
  • siempre de derecha a arriba; el estado del interruptor cambia a R
  • de arriba a izquierda solo si el interruptor está en estado L; el estado no cambia
  • de arriba a derecha si el interruptor está en estado R; el estado no cambia
  • nunca de izquierda a derecha o de derecha a izquierda

interruptor de nodo
Figura 1. Nodo de conmutación en estado L con estado objetivo TR

Estas propiedades también tienen:

  • 0, 1 o 2 de las salidas de un interruptor pueden aislarse (no conectadas a otro interruptor);
  • una ruta puede simplemente "tocar" un interruptor para cambiar su estado: ingrese desde la izquierda y salga desde la izquierda o ingrese desde la derecha y salga desde la derecha;
  • no hay restricciones en la cantidad de veces que se puede atravesar / tocar un interruptor.

El problema de decisión es: "¿Existe una ruta desde el nodo Inicio al nodo Final de manera que todos los estados finales de los conmutadores coincidan con el estado objetivo correspondiente?"

Obviamente, todos los interruptores que no están inicialmente en su estado objetivo deben atravesarse (o tocarse) al menos una vez;

Este es un dibujo rápido de una red trivial (hecha con Excel ... Haré una mejor):

ejemplo2

Una solución trivial es:

S -> 1 -> 2 -> 3 -> 2 -> E -> 1 -> E

EDITAR 2:

  1. ¿Se conoce este problema? ---> me diste la buena referencia a la tesis de Hearn (gráficos de restricción);

El problema está en ; antes de publicar un boceto de mi prueba de que está en NP, encontré un error; entonces las preguntas abiertas son nuevamente:nortePAGSPAGUNCmi=PAGSPAGUNCmi

2) ¿Es ?nortePAG

3) ¿Tiene el problema alguna posibilidad de ser ?nortePAG-Cometropaglmitmi

Marzio De Biasi
fuente
1
Le eché un vistazo rápido al documento sugerido (ahora lo leeré con más cuidado), pero mi problema parece diferente: los interruptores cambian su estado de acuerdo con la dirección en la que se atraviesan. En el artículo, los conmutadores son "fijos" y los problemas (más simples) son del tipo: "¿Existe una configuración de conmutador, de modo que ...".
Marzio De Biasi
44
@Vor: Esto parece estar estrechamente relacionado con los juegos de lógica de restricción de Demaine y Hearn (creo que la tesis de Hearn groups.csail.mit.edu/mac/users/bob/hearn-thesis-final.pdf es una muy buena reseña de este trabajo ) Me pregunto si uno podría resolver la complejidad de su problema utilizando sus técnicas. Parece que podría ser NEXP-complete ...
Joshua Grochow
3
Solo iba a señalar el trabajo de Hearn / Demaine; tenga en cuenta que ahora también está disponible como un libro, "Juegos, Rompecabezas y Computación" (ISBN 978-1-56881-322-6), y definitivamente se siente pertinente para esto pregunta.
Steven Stadnicki
2
@Kaveh: para mi nivel de experiencia es trivial en NPSPACE = PSPACE. Parece no poder "contar"; pero no veo ninguna prueba fácil de que si existe una solución, exista otra solución en la que cada interruptor se atraviese / toque solo un número constante de veces.
Marzio De Biasi
1
Solo una nota al margen: una versión más simple de este rompecabezas fue considerada también por Dillenburg y Nelson y se presenta en su Research Note Perimeter Search
Carlos Linares López el

Respuestas:

2

El problema es al menos NP-duro, por una reducción de 3-SAT.

Primero considere el problema de encontrar una ruta desde el Inicio hasta la Salida del siguiente gráfico dirigido con la restricción de que ninguna ruta puede visitar los tres nodos (cuadrados) de una cláusula:

3SAT

(X1X2X3)(X1¬X2X4 4)

Transformamos estos gráficos en una red de conmutación. Para esto utilizamos tres gadgets:

  1. Cada nodo circular y borde bidireccional se convierte en un alambre , formando las conexiones entre los interruptores.
  2. Cada borde dirigido se convierte en un dispositivo unidireccional que consiste en un solo interruptor (ver más abajo).
  3. Cada nodo cuadrado representa uno de los tres interruptores que forman parte de un gadget de Cláusula (ver más abajo).

En las siguientes ilustraciones, los interruptores se dibujan como dos flechas entrantes, una de las cuales está discontinua (deshabilitada). La dirección del objetivo se dibuja con un círculo negro (de modo que la flecha sólida eventualmente debe estar del lado del círculo).

Observación: Usaremos negrita para distinguir la Salida del gráfico de las salidas de los gadgets.

UNsisiUNX1X2X3X1X2X3

Gadget unidireccional Cláusula gadget

Recuerde que para el gráfico original, encontrar un camino que conduzca a la Salida y no visitó los tres nodos cuadrados de ninguna cláusula fue NP-completo. Ahora considere el problema de alcanzar la Salida del gráfico transformado sin preocuparse por las posiciones de destino de los interruptores.

Observe que cualquier ruta que sea una solución para el problema gráfico original también es una solución para el gráfico transformado. Por lo tanto, suponga que una ruta para el gráfico transformado no es una solución para el gráfico original. Esto puede suceder en dos casos:

  1. siUN
  2. Una ruta atraviesa las tres rutas de algún gadget de Cláusula .

En el primer caso, el dispositivo unidireccional debe haber sido atravesado en la dirección prevista, en cuyo caso el camino podría haber evitado atravesarlo en primer lugar.

Considere el segundo caso en el que la ruta atraviesa los tres interruptores de algún dispositivo de la Cláusula . Entonces ese gadget tendrá todos sus tres interruptores invertidos (ver más abajo). Aquí es donde hacemos uso de las posiciones de destino. Tenga en cuenta que la columna vertebral gris del gadget Clause ya no se puede alcanzar, lo que significa que los interruptores ya no se pueden dirigir a sus posiciones de destino. En este caso, decimos que este gadget de Cláusula es irrecuperable.

Cláusula de punto muerto

Queda por demostrar que para cualquier solución del problema gráfico original, los interruptores del gráfico transformado se pueden colocar en su posición de destino. Para esto, hacemos uso del hecho de que el cable de salida solo se puede alcanzar cuando hay una solución, o algún gadget de Cláusula se vuelve irrecuperable.

Para colocar los interruptores en su posición de destino, ahora podemos agregar dispositivos unidireccionales adicionales desde el cable de salida a la entrada de cada dispositivo unidireccional existente , así como a los tres cables de salida de todos los dispositivos de la cláusula . Luego, una vez que el token llega a la Salida , todos los One-way adicionales aparatos pueden ser atravesados (y de este modo ponen en su posición de destino), y también ponen los interruptores restantes en sus posiciones de destino (a menos que haya una cláusula irrecuperable). Finalmente, el token puede volver a la Salida y se resuelve el rompecabezas.

Deberíamos comentar que los gadgets de Cláusula solo pueden recuperarse cuando se ingresa desde una salida sin recorrer; y debido a los gadgets unidireccionales que se colocan entre la cláusula gadgets de y la siguiente variable, esto no puede suceder hasta que se llegue al cable de salida .

Por lo tanto, el problema de la red de conmutación es NP-hard.


Todavía no está claro si el problema está en NP o PSPACE-hard. Una reducción de la dureza NP que construye una red de conmutadores planos tendrá grandes implicaciones para las variantes restringidas de Sokoban, principalmente porque todos los conmutadores son equivalentes al dispositivo Sokoban a continuación.

Sokoban

Tim
fuente