Schritte, die das Verlassen eines Labyrinths garantieren

13

In einem zweidimensionalen Labyrinth können Sie 4 Befehle "Auf / Ab / Rechts / Links" eingeben. Wenn Sie das Labyrinth kennen, aber nicht wissen, wo sich die Person befindet, wie Sie die minimale Befehlsfolge finden, die das Verlassen des Labyrinths garantiert? Ich suche nach einer einzigen Folge von Befehlen, die funktionieren, egal wo im Labyrinth Sie anfangen.

Angenommen, wenn unser Partner bei einer Mauer auf der rechten Seite den Befehl "Nach rechts bewegen" erhält, bleibt er einfach dort, wo er ist.

Mit anderen Worten, wir erhalten ein Labyrinth und müssen eine Folge von Befehlen auswählen. Dann wird unser Partner irgendwo im Labyrinth platziert und folgt der Abfolge der Befehle, die wir im Voraus ausgewählt haben. Wir möchten, dass diese Reihenfolge sicherstellt, dass unser Partner entkommt, unabhängig davon, wo unser Partner ursprünglich platziert wurde. Beachten Sie, dass die zulässigen Befehle keine bedingten Anweisungen enthalten, sodass sie je nach Partner nicht einer anderen Reihenfolge folgen können.

Gibt es einen Polynom-Zeit-Algorithmus, um eine solche Sequenz mit einer Beschreibung des Labyrinths zu konstruieren?

Yuval Filmus erwähnt, dass dies ein Sonderfall eines Problems mit Synchronisationswörtern ist und mit universellen Durchquerungssequenzen zusammenhängen könnte. Ich fand auch ein Papier, das relevant zu sein scheint:

Das simultane Labyrinth, das Problem löst . Stefan Funke, André Nusser, Sabine Storandt. AAAI 2017.

Leider scheint dies für allgemeine Grafiken ein ungelöstes Problem zu sein, aber ich frage mich, ob es für diesen speziellen Fall einen guten Algorithmus geben könnte. Ich habe einen Kandidatenansatz gefunden: Beschriften Sie jede Position mit der Anzahl der Mindestschritte, die zum Verlassen erforderlich sind, und verfolgen Sie jeden Agenten im Labyrinth. Auf diese Weise kann möglicherweise eine A * -Suche durchgeführt werden.

seilgu
quelle
Kommentare sind nicht für längere Diskussionen gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Diskrete Eidechse
Eppsteins Strategie für monotone Automaten besteht darin, Zustände zu gruppieren, sodass er nicht nach einem Pfad in der vollständigen Potenzmenge der Zustände sucht, sondern nach einem Pfad in einem Graphen mit nur polynomiell vielen Eckpunkten. Die natürlichste Verallgemeinerung von Intervallen auf 2D, die ich mir vorstellen kann, ist die konvexe Hülle, aber leider ist nicht klar, dass ihre Anzahl polynomiell wächst .
Peter Taylor

Antworten:

-1

EIN

vonbrand
quelle
Sie können Wandfolgen nicht als feste Folge von Kardinalrichtungen codieren. Die Auswahl hängt von den Wänden um Sie herum ab, was von der Frage ausdrücklich abgelehnt wird.
Curtis F
Wenn Sie den kürzesten Pfad kennen, können Sie ihn als "Nach links, dann geradeaus, dann ..." kodieren. Wenn Sie den kürzesten Weg nicht kennen, können Sie solche Anweisungen nicht für den kürzesten Ausweg geben. Wenn Sie keinen Pfad kennen, können Sie keine Anweisungen geben, um herauszukommen.
Vonbrand