"Snake" -Rekonfigurationsproblem

Während ich einen kleinen Beitrag über die Komplexität der Videospiele Nibbler und Snake schreibe ; Ich fand heraus, dass beide als Rekonfigurationsprobleme auf ebenen Graphen modelliert werden können. und es ist unwahrscheinlich, dass solche Probleme im Bereich der Bewegungsplanung nicht gut untersucht wurden (stellen Sie sich zum Beispiel eine Kette von miteinander verbundenen Wagen oder Robotern vor). Die Spiele sind bekannt, dies ist jedoch eine kurze Beschreibung des zugehörigen Rekonfigurationsmodells:

SCHLANGENPROBLEM

Eingabe : Bei einem ebenen Graphen werden Kiesel auf Knoten , die einen einfachen Pfad bilden. Die Kieselsteine ​​stellen die Schlange dar , und der erste ist sein Kopf. Der Kopf kann von seiner aktuellen Position zu einem benachbarten freien Knoten bewegt werden, und der Körper folgt ihm. Einige Knoten sind mit einem Punkt markiert. wenn der Kopf einen Knoten mit einem Punkt erreicht, wird der Körper durch Erhöhung Kieseln in den folgenden Bewegungen des Kopfes. Der Punkt auf dem Knoten wird nach dem Durchlaufen der Schlange gelöscht.$G = (V,E)$$l$$p_1,...,p_l$$u_1,...,u_l$$p_1$$e$$e$

Problem : Wir fragen, ob die Schlange entlang des Graphen bewegt werden kann und eine Zielkonfiguration wobei die Zielkonfiguration die vollständige Beschreibung der Schlangenposition, dh der Position der Kieselsteine, ist.$T$

Es ist leicht zu beweisen, dass das SNAKE-Problem auf planaren Graphen mit maximalem Grad 3 NP-hart ist, selbst wenn keine Punkte verwendet werden, und auf SOLID-Gittergraphen, wenn wir eine beliebige Anzahl von Punkten verwenden können. Bei soliden Gitternetzdiagrammen ohne Punkte wird es kompliziert (dies hängt mit einem anderen offenen Problem zusammen).

Ich würde gerne wissen, ob das Problem unter einem anderen Namen untersucht wurde.
und insbesondere, wenn es einen Beweis dafür gibt, dass es sich um NP handelt ...

Bearbeiten: Das Problem erwies sich auch in ebenen Diagrammen als PSPACE-vollständig, und das Ergebnis scheint sehr interessant zu sein. Es bleibt daher zu prüfen, ob es sich um ein neues Problem handelt und ob bekannte Ergebnisse vorliegen.

Ein einfaches Beispiel (Kieselsteine ​​sind grün dargestellt, der Kopf der Schlange ist P1).

Wenn Sie eine Schlange von einer Position auf eine andere verschieben, ist PSPACE abgeschlossen. Snake ist trivial in PSPACE. Wir geben eine PSPACE-Härtereduktion aus Hearns Nondeterministic Constraint Logic.

Nichtdeterministische Beschränkungslogik

$1$$2$$\geq 2$$\geq 2$$3$$1$$3$$2$

Schlange

Bei unserer Konstruktion jagt der Kopf der Schlange in einiger Entfernung seinem Schwanz nach und muss denselben Zyklus mit geringfügigen Änderungen wiederholen. Wir betten jede Kante des Abhängigkeitsgraphen wie in der Abbildung ein (die Kanten sind rot dargestellt), wobei wir die Position der Schlange durch dicke Linien angeben. Eine Kante hat zwei Seiten (Scheitelpunkte) und die Schlange nimmt den zentralen Weg an dem Scheitelpunkt, auf den die Kante gerichtet ist.

Um eine Kante umzukehren, löscht die Schlange zuerst die Mittelroute und nimmt dann die Mittelroute, sobald ihr Kopf den gegenüberliegenden Scheitelpunkt erreicht.

$2$

Schließlich werden die schwarzen Linien aller Kantengeräte zu einem einzigen Zyklus verbunden, sodass der Kopf der Schlange seinem Schwanz nachjagt. Wenn wir zwischen zwei Kantengeräten den schwarzen Pfad ausreichend lang machen, muss die Schlange die schwarzen Pfade immer in derselben zyklischen Reihenfolge durchlaufen.

Um zu zeigen, dass die schwarzen Pfade immer plan konstruiert werden können, betrachten Sie einen übergreifenden Teilbaum (dicke Kanten in der Abbildung unten) des Abhängigkeitsgraphen. Dann können wir diesem Baum schwarze Kanten folgen lassen (siehe Abbildung unten), was zu einem ebenen Diagramm führt.

Die Zielposition der Schlange kann durch dieselbe Transformation abgeleitet werden. Daher ist die Neukonfiguration einer Schlange auch in ebenen Diagrammen mit PSPACE abgeschlossen.