Ein Labyrinth mit Multicores lösen?

Question

Diese Frage ist chaotisch, ich brauche keine funktionierende Lösung, ich brauche etwas Pseudo-Code.

Wie würde ich dieses Labyrinth lösen? Dies ist eine Hausaufgabenfrage. Ich muss von Punkt Grün zu Rot kommen. Bei jeder Gabel muss ich einen Faden spawnen und in diese Richtung gehen. Ich muss herausfinden, wie ich zu rot komme, aber ich bin nicht sicher, wie ich Wege vermeiden kann, die ich bereits genommen habe (das Beenden mit jedem Pfad ist in Ordnung, ich darf nur nicht im Kreis fahren).

Hier ist ein Beispiel für mein Problem, ich beginne mit der Bewegung nach unten und ich sehe eine Gabel, so geht man nach rechts und man geht nach unten (oder dieser Thread kann es nehmen, es spielt keine Rolle). Jetzt ignorieren wir den Rest der Gabeln und sagen, dass derjenige, der nach rechts geht, gegen die Wand schlägt, nach unten geht, gegen die Wand schlägt und nach links geht, dann nach oben geht. Der andere Thread geht runter, trifft die Wand und geht dann ganz nach rechts. Der untere Pfad wurde zweimal genommen, indem an verschiedenen Seiten begonnen wurde.

Wie kann ich diesen Pfad markieren? Brauche ich ein Schloss? Ist das der einzige Weg? Gibt es eine locklose Lösung?

Implementierung weise ich dachte, ich könnte das Labyrinth so etwas haben. Ich mag die Lösung nicht, weil es viele Sperren gibt (vorausgesetzt, ich sperre vor jedem Lesen und Schreiben des haveTraverse-Mitglieds). Ich brauche nicht die MazeSegment-Klasse unten, ich habe es nur als Beispiel geschrieben. Ich darf das Labyrinth bauen, wie ich will. Ich dachte, vielleicht braucht die Lösung keine Verbindungspfade, und das macht mich nervös. Vielleicht könnte ich die Map aufteilen, anstatt das Format unten zu verwenden (was einfach zu lesen und zu verstehen ist). Aber wenn ich wüsste, wie man es aufteilt, würde ich wissen, wie man es geht, also das Problem.

Wie gehe ich dieses Labyrinth effizient?

Der einzige Hinweis, den ich erhalte, war nicht versuchen, Speicher zu sparen, indem Sie es wiederverwenden, Kopien machen. Allerdings war das auf ein Problem mit der Bestellung einer Liste zurückzuführen und ich denke nicht, dass der Hinweis ein Hinweis dafür war.

class MazeSegment 
{ 
    enum Direction { up, down, left, right} 
    List<Pair<Direction, MazeSegment*>> ConnectingPaths; 
    int line_length; 
    bool haveTraverse; 
} 

MazeSegment root; 

class MazeSegment 
{ 
    enum Direction { up, down, left, right} 
    List<Pair<Direction, MazeSegment*>> ConnectingPaths; 
    bool haveTraverse; 
} 

void WalkPath(MazeSegment segment) 
{ 
    if(segment.haveTraverse) return; 
    segment.haveTraverse = true; 
    foreach(var v in segment) 
    { 
     if(v.haveTraverse == false) 
      spawn_thread(v); 
    } 
} 

WalkPath(root); 

Answer 1

Sie können dies mit tun die üblichen "lesen, neuen Wert berechnen, Vergleichs- und swap, wiederholen, bis CAS erfolgreich" Methode Lock-freie Programmierung gefunden häufig in.

Alle Gitterquadrate in Ihrem Labyrinth Start sollte einen Zeiger halten, der die Richtung darstellt, um sich zu bewegen, um den Ausgang zu erreichen. Anfangs sind sie alle "unbekannt".

Gehen Sie das Labyrinth aus dem Ausgang. Verwenden Sie auf jedem erreichten Quadrat Vergleich und Tauschen, um "Unbekannt" durch die Richtung des zuvor bearbeiteten Vierecks zu ersetzen. Wenn CAS fehlschlägt, hast du eine Schleife, bereinige diese Verzweigung. Wenn CAS erfolgreich ist, fahren Sie fort. Wenn Sie dem Eingang eine Richtung zuweisen, können Sie nun dem Pfad zum Ausgang folgen.

Answer 2

Aus der Hand, Ihre oben angegebene Struktur, kann ich dies sieht die Lösung durch ein Hinzufügen von 'int gesehen' zu jedem MazeSegement statt 'bool haveTraverse'. Sie könnten dann ein ineinandergreifendes Inkrement für die Variable 'Gesehen' verwenden, während Sie die ConnectedPaths durchlaufen und nur einen Thread erzeugen, um den Pfad aufzunehmen, wenn das 'Gesehen' Inkrement 1 zurückgibt (vorausgesetzt, dass Seen auf 0 initialisiert wird).

So wird der Code so etwas wie

void WalkPath(MazeSegment segment) 
{ 
    foreach(var v in segment.ConnectedPaths) 
    { 
     if(Interlocked.Increment(&v.Path.Seen) == 1) 
      spawn_thread(v.Path); 
    } 
} 

Andere Themen, die den gleichen Weg gehen könnte versuchen sollte, etwas> 1 erhalten. Da interlocked.increment ein thread-sicheres Inkrement garantiert, müssen wir uns nicht darum sorgen, dass 2 Threads das Ergebnis '1' erhalten, also sollte nur ein Thread einen bestimmten Pfad nehmen.

Answer 3

Parallel Breitensuche

Suche nach parallel oder Multi-Thread-Brot ersten Traversal, das ist im Grunde, was Sie tun. Jedes Mal, wenn Sie zu einer Verzweigung in Ihrem Labyrinth kommen (wo Sie einen von mehreren Pfaden nehmen können), erstellen Sie einen neuen Arbeitsthread, um die Suche in jedem der möglichen Pfade fortzusetzen und einen Bericht darüber zurückzugeben, welcher Sie bis zum Ende führt.

Es ist vergleichbar mit "einfachen" Breite ersten Suchen, außer die Teilbäume können parallel gesucht werden.

Wenn dies eine reine Baumdatenstruktur wäre, müssten Sie nicht sperren, aber da es sich um einen Graphtravers handelt, müssen Sie Ihre besuchten Knoten verfolgen. Also muss der Code, der das Flag "besucht" jedes Knotens setzt, mit einer Sperre geschützt werden.

Hier ist ein gutes Beispielprogramm. Es verwendet Audio-Feedback, also achten Sie darauf, dass Ihre Lautsprecher eingeschaltet sind.

http://www.break.com/games/maze15.html

Answer 4

Erstellen Sie eine Klasse (Worker) Instanzen von denen einen Pfad bisher genommen halten, und kann nur advance() durch einen geraden Korridor bei gegebener Richtung. Platzieren Sie an jeder Kreuzung das Worker-Objekt, das den Pfad vor der Kreuzung enthält, und erstellen Sie zwei (oder drei) neue Objekte, wobei eine Kopie dieses Pfads und verschiedene Kurven verwendet werden.

Setzen Sie diese Worker-Objekte in eine Warteschlange. Beachten Sie, dass jeder von ihnen unabhängig von einem anderen ist, so dass Sie mehrere von ihnen aus der Warteschlange und advance() parallel nehmen können. Sie können einfach so viele Threads erstellen oder einen Pool von Threads entsprechend der Anzahl der Kerne verwenden, die Sie haben. Sobald einer der Arbeiter zum Zielquadrat vorrückt, geben Sie die Pfade aus, die er hält, es ist eine Lösung.

Ziehen Sie in Erwägung, das Labyrinth von Ausgang zu Eingang zu überqueren. In einem echten Labyrinth sollen Sackgassen die Bewegung von Eingang zu Ausgang verlangsamen, aber selten umgekehrt.

Erwägen, einen Schleifenerkennungsmechanismus, z. Vergleichen Sie Schnittpunkte, aus denen Ihr Weg besteht, mit einer Kreuzung, auf die Sie treffen.

Verwenden Sie eine handgefertigte verknüpfte Liste, um den Pfad darzustellen. Beachten Sie, dass das Einfügen eines neuen Kopfes in eine verknüpfte Liste den Rest davon nicht ändert, sodass Sie den Schwanz mit anderen Instanzen teilen können, die ihn nicht verändern. Dies reduziert den Speicherbedarf und die Zeit, die benötigt werden, um einen Arbeiter zu spawnen (nur bei ziemlich großen Labyrinthen bemerkbar).