Komplexität eines Switch-Netzwerkproblems

17

Ein Switch-Netzwerk (der Name wird erfunden) besteht aus drei Arten von Knoten:

  • ein Startknoten
  • ein Endknoten
  • ein oder mehrere Vermittlungsknoten

Der Vermittlungsknoten hat 3 Ausgänge: Links, Oben, Rechts; hat zwei Zustände L und R und einen Zielzustand TL oder TR . Jeder Schalter kann mit den folgenden Regeln durchlaufen werden:

  • immer von links nach oben; der Zustand des Schalters wechselt zu L
  • immer von rechts nach oben; der Zustand des Schalters wechselt auf R
  • nur von oben nach links, wenn sich der Schalter im Zustand L befindet; Der Zustand ändert sich nicht
  • von oben nach rechts, wenn sich der Schalter im Zustand R befindet; Der Zustand ändert sich nicht
  • niemals von links nach rechts oder von rechts nach links

Schalterknoten
Abbildung 1. Vermittlungsknoten in Zustand L mit Zielzustand TR

Diese Eigenschaften gelten auch:

  • 0, 1 oder 2 der Ausgänge eines Schalters können isoliert werden (nicht mit einem anderen Schalter verbunden);
  • Ein Pfad kann einen Schalter nur "berühren" , um seinen Status zu ändern: von links eingeben und von links beenden oder von rechts eingeben und von rechts beenden;
  • Es gibt keine Einschränkung, wie oft ein Schalter bewegt / berührt werden darf.

Das Entscheidungsproblem lautet: "Existiert ein Pfad vom Startknoten zum Endknoten, sodass alle Endzustände der Switches mit dem entsprechenden Zielzustand übereinstimmen?"

Offensichtlich müssen alle Schalter, die sich anfänglich nicht in ihrem Zielzustand befinden, mindestens einmal überfahren (oder berührt) werden.

Dies ist eine kurze Darstellung eines einfachen Netzwerks (erstellt mit Excel ... ich mache ein besseres):

example2

Eine triviale Lösung ist:

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

EDIT 2:

  1. Ist dieses Problem bekannt? ---> Sie gaben mir den guten Hinweis auf die Hearn-These (Constraint Graphs);

NPSPACE=PSPACE

NP

NP-complete

Marzio De Biasi
quelle
1
Ich habe einen kurzen Blick auf das vorgeschlagene Papier geworfen (jetzt lese ich es genauer durch), aber mein Problem scheint anders zu sein: Die Schalter ändern ihren Zustand in Abhängigkeit von der Richtung, in die sie durchlaufen werden. In dem Artikel sind die Schalter "behoben" und die (einfacheren) Probleme sind von der Art: "Existiert eine Schalterkonfiguration, so dass ...".
Marzio De Biasi
4
@Vor: Dies scheint eng mit den Constraint-Logik-Spielen von Demaine und Hearn zu verwandt zu sein (ich denke, Hearns These groups.csail.mit.edu/mac/users/bob/hearn-thesis-final.pdf ist eine sehr schöne Zusammenfassung dieser Arbeit ). Ich frage mich, ob man mit ihren Techniken die Komplexität Ihres Problems lösen kann. Es scheint, als wäre es NEXP-vollständig ...
Joshua Grochow
3
Ich wollte nur auf die Hearn / Demaine-Arbeit hinweisen - beachten Sie, dass sie jetzt auch als Buch "Games, Puzzles & Computation" (ISBN 978-1-56881-322-6) erhältlich ist, und es fühlt sich definitiv so an Frage.
Steven Stadnicki
2
@Kaveh: Für meinen Kenntnisstand ist es trivial in NPSPACE = PSPACE. Es scheint nicht in der Lage zu sein, "zu zählen"; Ich sehe jedoch keinen einfachen Beweis dafür, dass es eine andere Lösung gibt, wenn eine Lösung existiert, bei der jeder Schalter nur eine konstante Anzahl von Malen durchlaufen / berührt wird.
Marzio De Biasi
1
Nur eine Randnotiz: Eine einfachere Version dieses Puzzles wurde auch von Dillenburg und Nelson in Betracht gezogen und wird in ihrer Research Note Perimeter Search
Carlos Linares López,

Antworten:

2

Das Problem ist zumindest NP-schwer, durch eine Reduzierung von 3-SAT.

Betrachten wir zunächst das Problem, einen Weg von der Suche nach Beginn an den Ausgang des folgenden gerichteten Graphen mit der Einschränkung , dass kein Pfad (Quadrat) Knoten einer Klausel alle drei besuchen:

3SAT

(X1X2X3)(X1¬X2X4)

Wir transformieren diese Graphen in ein Switch-Netzwerk. Dafür verwenden wir drei Gadgets:

  1. Jeder Kreisknoten und jede bidirektionale Kante wird zu einem Draht , der die Verbindungen zwischen den Schaltern herstellt.
  2. Jede gerichtete Kante wird zu einem Einweg- Gadget, das aus einem einzelnen Schalter besteht (siehe unten).
  3. Jeder quadratische Knoten repräsentiert einen der drei Schalter, die Teil eines Klausel- Gadgets sind (siehe unten).

In den folgenden Abbildungen sind Schalter als zwei ankommende Pfeile dargestellt, von denen einer gestrichelt (deaktiviert) ist. Die Zielrichtung wird mit einem schwarzen Kreis gezeichnet (so dass sich der durchgezogene Pfeil eventuell auf der Seite des Kreises befinden muss).

Anmerkung: Wir werden Fettdruck verwenden , um den Ausgang des Diagramms von den Ausgängen der Minianwendungen zu unterscheiden .

ABBAX1X2X3X1X2X3

Einweg-Gadget Klausel-Gadget

Denken Sie daran, dass für das ursprüngliche Diagramm die Suche nach einem Pfad, der zum Ausgang führte und nicht alle drei quadratischen Knoten einer Klausel besuchte, NP-vollständig war. Betrachten Sie nun das Problem, den Ausgang des transformierten Graphen zu erreichen, ohne sich um die Zielpositionen der Schalter zu kümmern.

Beachten Sie, dass jeder Pfad, der eine Lösung für das ursprüngliche Diagrammproblem darstellt, auch eine Lösung für das transformierte Diagramm ist. Nehmen wir also an, ein Pfad für das transformierte Diagramm ist keine Lösung für das ursprüngliche Diagramm. Dies kann in zwei Fällen passieren:

  1. BA
  2. Ein Pfad durchläuft alle drei Pfade eines Klausel- Gadgets.

Im ersten Fall muss das Einweg- Gadget zuerst in die vorgesehene Richtung durchlaufen worden sein. In diesem Fall hätte der Pfad es genauso gut vermeiden können, es an erster Stelle zu durchlaufen.

Betrachten Sie also den zweiten Fall, in dem der Pfad alle drei Schalter eines Klausel- Gadgets durchläuft . In diesem Fall werden alle drei Schalter des Geräts umgedreht (siehe unten). Hier nutzen wir die Zielpositionen. Beachten Sie, dass das graue Rückgrat des Klausel- Gadgets nicht mehr erreicht werden kann, was bedeutet, dass die Schalter nicht mehr auf ihre Zielpositionen gerichtet werden können. In diesem Fall kann dieses Klausel- Gadget nicht wiederhergestellt werden.

Verklemmte Klausel

Es bleibt zu zeigen, dass für jede Lösung des ursprünglichen Diagrammproblems die Schalter des transformierten Diagramms in ihre Zielposition gebracht werden können. Dazu nutzen wir die Tatsache, dass der Ausgangsdraht nur erreicht werden kann, wenn es eine Lösung gibt oder ein Klausel-Gadget nicht mehr wiederherstellbar ist.

Um die Schalter in ihre Zielposition zu bringen, können wir jetzt zusätzliche Einweg- Gadgets vom Ausgangskabel zum Eingang jedes vorhandenen Einweg- Gadgets sowie zu den drei Ausgangskabeln aller Klausel- Gadgets hinzufügen . Sobald der Token den Ausgang erreicht , können alle zusätzlichen Einweg- Gadgets überquert (und dadurch in ihre Zielposition gebracht) und die verbleibenden Schalter in ihre Zielposition gebracht werden (es sei denn, es gibt eine nicht behebbare Klausel). Schließlich kann der Spielstein zum Ausgang zurückkehren und das Rätsel ist gelöst.

Wir möchten darauf hinweisen , dass Klausel- Minianwendungen nur wiederhergestellt werden können, wenn sie über einen nicht überquerten Exit eingegeben werden. Aufgrund der Einweg- Minianwendungen, die zwischen Klausel- Minianwendungen und der nächsten Variablen platziert sind, kann dies erst geschehen, wenn die Ausgangsleitung erreicht ist.

Daher ist das Switch-Netzwerk-Problem NP-schwer.


Es ist immer noch unklar, ob das Problem NP- oder PSPACE-schwer ist. Eine Reduzierung der NP-Härte beim Aufbau eines planaren Switch-Netzwerks hat große Auswirkungen auf eingeschränkte Varianten von Sokoban, da alle Switches dem folgenden Sokoban-Gadget entsprechen.

Sokoban

Tim
quelle