"Snake" -Rekonfigurationsproblem

13

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)lp1,...,plu1,...,ulp1ee

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.

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

Marzio De Biasi
quelle
1
Ob das Problem in kann nichts damit zu tun haben, ob Kiesel erlaubt sind oder nicht: Wenn das Schlangenproblem ohne Kiesel in , dann ist es auch das Schlangenproblem mit Kiesel, da wir als Zertifikat angeben können, in welcher Reihenfolge Die Punkte werden aufgenommen, der Zustand der Schlange kurz bevor sie einen Punkt erreicht, und in den Zuständen nach dem Aufnehmen des Punktes. Unter der Annahme, dass Snake Problem ohne Kiesel in , gibt es ein Zertifikat, das uns sagt, wie wir die Bewegungen "dazwischen" machen sollen. N P e N PNPNPeNP
Tom van der Zanden
Können Sie eine bessere und klarere Definition für die Zielkonfiguration bereitstellen? zB was meinst du mit vollständiger Beschreibung der Schlangenposition?
Saeed
@Saeed: Die Zielkonfiguration ist einfach die Endposition der Kieselsteine ​​(dh der Schlange). Ich werde eine Zahl hinzufügen, um das Problem zu klären.
Marzio De Biasi
Ihre Frage war klar genug, aber ich habe die Terminologie in meinem Kommentar verwechselt. Es sollte überall "Punkte" statt "Kiesel" lesen.
Tom van der Zanden
@TomvanderZanden: ok danke, ich stimme dir zu (siehe auch meinen Kommentar zu Zimmuxs Antwort). Ich schrieb "... mit oder ohne Punkte ...", um zu sagen, dass sie irrelevant sind; aber es war nicht klar genug; Deshalb habe ich die Frage bearbeitet und genauer formuliert.
Marzio De Biasi

Antworten:

8

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

12223132NCL-Geräte

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. Kante umkehren

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

Schlange und Schlange oder

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.

Übergreifender Teilbaum Planarer Zyklus

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

Tim
quelle
Groß! :-) :-) :-)
Marzio De Biasi