Graph Gebäudealgorithmus gegeben einen unendlichen Spaziergang

Question

Ich brauche Hilfe schreiben eine belastbare, Mapping (Graphenbildung) Algorithmus. Hier ist das Problem:

Stellen Sie sich vor, Sie haben eine Text orientierte virtuelle Realität (TORG/MUD), wo Sie Bewegungsbefehle senden können (n, s, w, e, oben, unten, innen, ... usw.) über Telnet, um deinen Charakter von Raum zu Raum zu bewegen. Und der Server sendet nach jedem Bewegungsschritt eine entsprechende Raumbeschreibung zurück. Ihre Aufgabe besteht darin, ein Diagramm zu erstellen, das die zugrunde liegende Kartenstruktur darstellt, sodass Sie auf der Clientseite einfach ein DFS ausführen können, um herauszufinden, wie Sie von einem Raum zum anderen gelangen. Auch wollen Sie das System so zu gestalten, dass minimale Benutzereingabe

Hier erforderlich sind, um die Annahmen:

• Die zugrunde liegende Graph-Topologie auf dem Server ändern sich nie.

• Zimmerbeschreibungen sind nicht eindeutig. Die meisten Zimmer haben unterschiedliche Beschreibungen, aber einige der Zimmer haben genau die gleiche Beschreibung. Die Zimmerbeschreibung wird ab und zu (Tage oder Wochen) geändert

• Ihre Bewegung kann mit einer kleinen Wahrscheinlichkeit zufällig fehlschlagen und Sie erhalten eine Fehlermeldung anstelle der neuen Raumbeschreibung, wie "Sie hören auf zu warten damit der Wagen vorbeikommt "," Die Tür ist verschlossen ", und dein Charakter wird immer noch im aktuellen Raum sein.

• Sie können für jede Bewegung nicht den räumlichen Abstand der Einheit annehmen. Zum Beispiel haben Sie vielleicht eine Topologie wie die unten gezeigte, also wird es nicht funktionieren, die Einheitsdistanz für jedes benachbarte Zimmer anzunehmen und jedem Raum eine harte Koordinate zuzuweisen. Sie können jedoch annehmen, dass die relative Richtung konsistent ist, das heißt, es wird keine Schleife in einer topologischen Sortierung entlang X (Westen, Osten) und Y (Süden, Norden) geben.

• Ziel: Bei einem Ziel, das Sie schon einmal besucht haben, garantiert Ihnen der Algorithmus, Sie eventuell dorthin zu bringen, und findet den kürzesten Weg die meiste Zeit. Fehler sind erlaubt, aber der Algorithmus sollte in der Lage sein, die Fehler im laufenden Betrieb zu erkennen und zu korrigieren.

Beispiel grafische Darstellung:

A--B---B 
|  | <- k 
C--D-E-F 

Ich habe bereits implementiert eine sehr einfache Lösung, die die Raumbeschreibungen und konstruieren ein Diagramm aufzeichnen würde. Das folgende Beispiel zeigt eine Diagrammdarstellung, die mein Programm in json generiert. Die "Ausgänge" sind die Bewegungsrichtung, die der Knoten-ID zugeordnet ist. -1 repräsentiert einen nicht zugeordneten Raum. Wenn der Benutzer in eine Richtung läuft und in der Diagrammdarstellung eine -1 erkennt, versucht der Algorithmus, Knoten zu finden, die sich bereits im Diagramm befinden. Wenn Knoten mit derselben Beschreibung gefunden werden, wird der Benutzer aufgefordert, zu entscheiden, ob der neu gesehene Raum einer der alten Knoten ist. Wenn nicht, fügt es einen neuen Knoten hinzu und verbindet ihn mit dem Graphen.

"node": [ 
     { 
      "description": "You are standing in the heart of the Example city. There is a fountain with large marble statue in it...", 
      "exits": { 
       "east": -1, 
       "north": 31, 
       "south": 574, 
       "west": 42 
      }, 
      "id": 0, 
      "name": "cot", 
      "tags": [], 
      "title": "Center of Town", 
      "title_color": "\u001b[1m\u001b[36m Center of Town\u001b[0;37;40m" 
     }, 
     { 
     ... 

Diese einfache Lösung erfordert beim Erstellen des Graphen menschliche Eingangserkennungsschleifen. In dem oben gezeigten Diagramm wird beispielsweise angenommen, dass dieselben Buchstaben die gleiche Raumbeschreibung darstellen. Wenn Sie mit dem ersten B beginnen, und mit links, unten, rechts ... bis Sie die Bewegung k ausführen, sehen Sie nun wieder B, aber der Mapper kann nicht feststellen, ob es das B ist, das er vorher gesehen hat.

Kurz gesagt möchte ich in der Lage sein, einen resilienten Graphenbildungsalgorithmus zu schreiben, der in einem versteckten Zielgraphen einen Schritt macht (möglicherweise unendlich) und einen Graphen erzeugt (und ständig aktualisiert), der (hoffentlich) dem Ziel ähnlich ist Graph.Wir verwenden dann das generierte Diagramm, um die Navigation im Zieldiagramm zu erleichtern. Gibt es einen bestehenden Algorithmus für diese Kategorie von Problemen?

Ich habe auch darüber nachgedacht, einige maschinelle Lerntechniken auf dieses Problem anzuwenden, aber ich bin nicht in der Lage, ein konkretes Modell zu schreiben. Ich denke an die Definition einer Liste von Funktionen für jeden Raum, den wir sehen (Raumbeschreibung, Ausgänge, Nachbarknoten), und jedes Mal, wenn wir einen Raum sehen, versuchen wir den Graphknoten zu finden, der am besten zu den Features passt Einige Update-Regeln (wie Winnow oder Perceptron) aktualisieren die Beschreibung, die wir aufgrund einiger Fehlererkennungsmetriken sehen.

Alle Gedanken/Vorschläge würden sehr geschätzt werden!

Answer 1

Viele MU * s geben Ihnen eine Möglichkeit, eine eindeutige Kennung für Räume zu erhalten. (Auf MUSH und seinen Ablegern, das ist think %L.) Andere könnten eingerichtet werden, um Räume zu beschreiben, die Sie bereits in gekürzter Form besucht haben. Wenn nicht, müssen Sie feststellen, ob Sie schon einmal in einem Raum waren. Ein einfacher Weg wäre, einen Hash von genug Informationen über jeden Raum zu berechnen, um einen eindeutigen Schlüssel zu erhalten. Ein Labyrinth könnte jedoch absichtlich eingerichtet werden, um Sie dazu zu verleiten, zu denken, dass Sie sich an einem anderen Ort befinden. Wizardry insbesondere wurde entwickelt, um Old-School-Spieler Kartierung der Verlies ny Hand reißen ihre Haare machen, wenn sie realisiert ihre Karte musste falsch sein, und die Zork Serie hatte ein Puzzle, wo Objekte Sie fallen gelassen, um Ihren Platz zu markieren Das Labyrinth würde sich bewegen, während du woanders warst. In der Praxis lohnt es sich wahrscheinlich nicht, Ihr Werkzeug zur Lösung dieser Rätsel zu programmieren.

Sie sollten in der Lage sein, eine Tabelle aller kürzesten Pfade aller Paare zu memotisieren und sie so zu aktualisieren, dass sie dem Untergraphen entspricht, den Sie bei der Suche nach einem neuen Exit erkundet haben. Dies könnte als N × N Tabelle implementiert werden, wobei Zeile i, Spalte j sagen Ihnen, den nächsten Schritt auf dem kürzesten Weg vom Standort i zur Lage j. Normalerweise für einen gerichteten Graphen. Selbst wenn Dijkstras Algorithmus jedes Mal ausgeführt wird, sollte dies ausreichen, aber in der Praxis fügt jede Bewegung der Karte einen Raum hinzu und fügt keinen kürzeren Weg zwischen vielen anderen Räumen hinzu. Sie möchten automatisch Verbindungen zwischen Räumen zuordnen, die Sie bereits waren (es sei denn, sie sollten versteckt sein) und den Explorer nicht zwingen, jeden einzelnen Ausgang mühsam durchzugehen, um zu sehen, wohin er geht.

Wenn Sie die Karte entwerfen können, können Sie auch die Bereiche so anordnen, dass sie leicht zu navigieren sind. Dann können Sie Ihre Tabellen klein halten: Sie müssen nur Karten einzelner Bereiche enthalten, die Sie absichtlich ausgewählt haben ausgelegt als Labyrinthe zum Erkunden. Das heißt, wenn du von einem Verlies zum anderen gehen willst, musst du nur den nächsten Ausgang und dann die Richtungen zwischen den Verliesen auf der Weltkarte nachschlagen, nicht einen riesigen Tisch, der quadratisch mit der Anzahl der Orte im ganzen wächst Spiel. Wenn Sie beispielsweise die Welt als verschachtelte Hierarchie ausgelegt haben, in der sich ein Raum in einem Gebäude in einer Straße in einer Stadt in einer Region eines Landes auf einem Kontinent auf einem Planeten befindet, können Sie nur Orte speichern Ein Baum, und das Navigieren von einem Bereich zu den anderen ist nur eine Frage des Gehens den Baum hinauf, bis Sie einen Zweig auf dem Weg zu Ihrem Ziel erreichen.

Ich bin mir nicht sicher, wie maschinelles Lernen mit neuronalen Netzen oder so hier hilfreich wäre; Wenn die Art von Trick, nach der Sie suchen, die Möglichkeit ist, dass ein Raum, der derselbe zu sein scheint, wirklich ein Duplikat ist, besteht die Möglichkeit darin, mehrere mögliche Karten gleichzeitig zu verwalten die Annahme, dass scheinbar identische Räume Duplikate sind oder nicht, ein Garten verzweigter Pfade.