Algorithmus: Finden des kürzesten Weges durch einen Dungeon in einem Spiel

8

Hintergrund

Ich habe kürzlich das PC-Spiel "Darkest Dungeon" gespielt. Im Spiel müssen Sie Dungeons erkunden, die aus verbundenen Räumen bestehen (siehe Abbildung unten). Darkest_Dungeon_Minimap

Hier sind die Regeln:

  • Sie beginnen in einem festen Raum (Eingang). Sie können nicht auswählen, wo Sie beginnen möchten.
  • Ziel ist es , jeden Raum mindestens einmal zu besuchen
  • Der Abstand zwischen benachbarten Räumen ist für alle Räume gleich.
  • Sie können Zimmer und Gehwege so oft besuchen, wie Sie möchten

Frage

Was ist der kürzeste Weg vom Eingang, der jeden Raum mindestens einmal besucht?

Unterfragen:

  • Welche Algorithmen könnten verwendet werden, um dieses Problem zu lösen?
  • Gibt es Implementierungen, die für jemanden wie mich kostenlos (und ziemlich einfach) zu verwenden sind?

Was ich versucht habe

Ich habe andere Fragen wie diese oder jene gefunden, ohne eine Antwort zu finden. Ich bin mit dem (grundlegenden) TSP vertraut und kann einfache TSPs codieren und lösen. Hamilton-Pfade haben mein Problem nicht gelöst, da mehrere Besuche nicht möglich sind. Das chinesische Postbotenproblem gilt auch hier nicht in seiner Grundform, da ich nicht jeden Rand besuchen muss.

Aktualisieren

Wie ich in den Kommentaren festgestellt habe, bin ich kein Informatiker und nicht daran interessiert, mathematische Aussagen zu beweisen (vielleicht werde ich diese Frage zu einem späteren Zeitpunkt über Stackoverflow stellen). Außerdem bin ich kein Programmierer und die Chancen, dass ich selbst eine Lösung codieren kann, sind ziemlich gering. Aber ich vermute, ich bin nicht der erste, der sich mit einem Problem dieser Art befasst.

Laut @Shreesh und @Dib könnte das folgende Verfahren angewendet werden:

  1. Erstellen Sie eine paarweise Abstandsmatrix mit allen Räumen und fügen Sie so Kanten zwischen allen Räumen hinzu.
  2. Lösen Sie TSP mit einem Standardlöser (z. B. concorde).
  3. Besuchen Sie ab dem Eingang alle Räume entsprechend der Lösung. Ersetzen Sie nicht benachbarte Räume durch den kürzesten Abstand zwischen diesen Räumen.

Wird dieses Verfahren die Antwort auf das Problem liefern?

algorithms graphs optimization shortest-path COOLSerdash
quelle
6
Ihr Problem scheint ein Sonderfall von TSP zu sein. In vielen Sonderfällen können Sie es besser machen als im allgemeinen Fall. Hast du in diese Richtung geschaut?
Yuval Filmus
@ YuvalFilmus Danke für deinen Kommentar. Ich habe versucht, diese Frage zu googeln, konnte aber keine direkte Lösung finden. Da ich kein Informatiker bin, sind akademische Arbeiten meist jenseits meines Verständnisses. Ich hoffte, dass diese Variante des TSP bekannt ist und dass es vielleicht bereits eine Lösung gibt. Ich werde wahrscheinlich einen Moderator bitten, diese Frage zu einem späteren Zeitpunkt auf Stackoverflow zu migrieren. Danke nochmal für deine Hilfe.
COOLSerdash
Danke für alle Kommentare, COOLSerdash. Ich denke, es wäre hilfreich, Ihre Frage so zu bearbeiten, dass alle Informationen, die Sie in den Kommentaren angegeben haben, in zusammengefasster Form enthalten sind.
DW
1
Es kann leicht mehr als einen "kürzesten Weg von ... mindestens einmal" geben, aber 1.2.3. bietet einen "kürzesten Weg von ... mindestens einmal".

Antworten:

3

Travelling Salesman Problem, auch wenn Sie das Wiederholen von Knoten zulassen, ist NP-schwer. Siehe Computerkomplexität von TSP .

Umans und Lenhart zeigen Härteergebnisse für Hamilton-Graphen in Solid-Grid-Graphen, 1997 .

TSP für Euklidealfall (oder Graphen mit Dreiecksungleichung) implizieren auch die NP-Härte von TSP mit Knotenwiederholung. TSP auch für Manhattan DistanzL1 (oder L∞) Metrik ist NP-vollständig. Siehe das Originalpapier von Papadimitriou zu diesem Thema .

Möglicherweise können Sie die NP-Härte von TSP für Ihren Fall nachweisen, indem Sie Bögen zu Knoten hinzufügen, die den entsprechenden Abstand als Länge des kürzesten Pfades zwischen Knoten haben, wodurch Wiederholungen der Knoten simuliert werden. TSP für Ihren speziellen Fall sieht aus wie ein NP-vollständiges Problem.

Schreiben Sie also entweder einen ausreichend guten (heuristisch gesehenen) exponentiellen Verzweigungs- und gebundenen Algorithmus, um eine kürzeste Tour zu berechnen (was bei kleinem Diagramm möglicherweise nicht so ineffizient ist), oder vergessen Sie die Optimierung und berechnen Sie eine ausreichend gute Näherung.

Shreesh
quelle
Danke für deine Antwort, Shreesh. Leider bin ich kein Informatiker und nicht daran interessiert, mathematische Aussagen zu beweisen (vielleicht werde ich diese Frage zu einem späteren Zeitpunkt im Stackoverflow veröffentlichen). Außerdem bin ich kein Programmierer und die Chancen, dass ich selbst eine Lösung codieren kann, sind ziemlich gering. Aber ich vermute, ich bin nicht der erste, der sich mit einem Problem dieser Art befasst. Danke noch einmal.
COOLSerdash
Ein einfacher Weg, dies zu tun, ist hinzufügen nC.2Kanten, die kürzesten Pfaden entsprechen, und lösen dann TSP mit einem vorhandenen Algorithmus. Wie Sie Concorde bereits kennen, wäre es einfach.
Shreesh
1
Wir haben hier ein Gitterdiagramm mit Einheitsgewichten. Ist der Verdacht, dass das Problem viel einfacher ist als selbst euklidischer TSP. (cc @COOLSerdash)
Raphael
Nein, wenn das Gitter dünn ist, haben wir im Grunde TSP mit Eckpunkten an rationalen Punkten und L.1metrisch. Wenn Ihr Gitter jedoch dicht ist, dh Sie müssen im Grunde fast jeden Punkt des Gitters besuchen, nein, Sie besuchen jeden Punkt des Gitters, dann gibt es ein sehr gutes ~n2Pfad. Sehen Sie hier und hier .
Shreesh
2

Sie können dies wie ein modifiziertes Problem bei der Planung der Pfadabdeckung behandeln, das Sie in wenigen einfachen Schritten lösen können:

1) Erstellen Sie aus den Gitterräumen einen ungewichteten ungerichteten Graphen. Pfadübergänge sind Knoten und kanten die Pfade zwischen diesen Knoten.

2) Finden Sie den minimalen Spannbaum von Ihrem Startpunkt aus mithilfe der Tiefensuche.

3) "Unterteilen" Sie das zugrunde liegende Raster so, dass Ihr minimaler Spannbaum zwei "Spuren" erstellt.

4) Gehen Sie von Ihrem Startpunkt aus im Uhrzeigersinn auf der rechten Spur von Knoten zu Knoten, bis Sie zum Startpunkt auf der komplementären Spur zurückkehren.

Auf diese Weise erhalten Sie einen minimalen Rundgang durch die Räume, der proportional zur Anzahl der Kacheln im Dungeon ist. Dies ist im Wesentlichen der Pfadplanungsalgorithmus für die Spiral Spanning Tree-Abdeckung, der auf eine reduzierte Einstellung angewendet wird. (Vgl. "Spiral-stc: Ein Online-Abdeckungsalgorithmus für Netzumgebungen durch einen mobilen Roboter")

GEL
quelle
Können Sie erklären, was es bedeutet, das Raster zu unterteilen? Was ist, wenn sich mein Diagramm nicht in einem Raster befindet? dh imgur.com/a/KlnPO
jdelman
1

Zusätzlich zu der obigen Antwort möchte ich auf einige bereits verfügbare TSP-Löser hinweisen.

  1. Concorde TSP Solver
  2. TSP-Löser von der Stony Brooks University
  3. TSP-Solver mit Google Direction API
  4. Und viele mehr .
Dib
quelle
Vielen Dank für Ihre Antwort. Aber wie gesagt, ich weiß bereits, wie man TSP mit concorde löst. Da mein Problem nicht direkt für den ursprünglichen TSP geeignet ist, weiß ich derzeit nicht, wie mir das helfen wird.
COOLSerdash
Der kürzeste Weg wäre der Weg, der jeden Raum genau einmal besucht. Durch Hinzufügen zusätzlicher Knoten können Sie Ihr Problem auf ein TSP-Problem reduzieren, dessen Antwort direkt auf Ihre Frage antworten würde.
Dib