Tiefe erste Suche parallel

Question

Ich implementiere ein DFS, um den Ausgang eines Labyrinths zu finden, und derzeit ist es single-threaded.

Ich plane, es effizienter zu machen, indem ich mehrere Threads erzeuge, die den Baum mit demselben Singlethread-Algorithmus durchsuchen, aber ich bin randomisiert, in welche Richtung ich gehen soll, wenn ich auf eine Kreuzung stoße.

Zum Beispiel stoßen die Threads auf eine Kreuzung, wo sie nach Osten oder Westen gehen können. Die Hälfte von ihnen geht nach Osten und die andere Hälfte nach Westen. Dies wird fortgesetzt, bis einer der Threads den Lösungspfad findet.

Ist dies ein gültiger Weg, um DFS parallel zu implementieren?

Answer 1

[UPDATE1]

Hier mein Vorschlag mit Thread-Synchronisation ist (aber auf der Grundlage unserer Diskussion mit @IraBaxter bin ich nicht mehr sicher, dass meine Art und Weise irgendwelche Vorteile gibt):

Wenn Algorithmus beginnt nur ein Thread wird benötigt, bis Sie zur ersten Gabel kommen. Wenn dieser eine Thread dort ankommt, sollte er alle möglichen Ergebnisse (links, rechts, Mitte) zum Stack machen und sich selbst stoppen. Da es einige Elemente im Stapel gibt, werden mehrere Threads aktiviert, um von den im Stapel gespeicherten Kanten zu starten. Wenn jeder dieser Threads einen Fork erreicht, werden alle Ergebnisse auf den Stack gelegt und Threads stoppen sich selbst (nicht alle auf einmal, jeder tut wenn es nötig ist) und nehmen Kanten vom Stack. Und so weiter. Jedes Mal, wenn ein Thread angehalten wird (unabhängig von der Gabel oder der Sackgasse), wechselt er in den Modus, der auf Kanten im Stapel wartet (oder nimmt einen, wenn der Stapel nicht leer ist). Und jedes Mal, wenn eine Kante zu dem Stapel hinzugefügt wird, werden Threads über die Nicht-Leere des Stapels benachrichtigt.

Ich benutzte den Begriff "Kante" hier in der Bedeutung der Position der Gabel plus Richtung, wo von der gegebenen Gabel zu gehen. Stack gibt Ihnen die Tiefeneigenschaft des Algorithmus.

PS: Es ist möglich, diesen Ansatz zu optimieren, indem die Anzahl der Synchronisationspunkte reduziert wird. Wir können Forking-Kanten in separaten Arbeitslisten für jeden Thread sammeln und stoppen diesen Thread nicht, bis er die Sackgasse erreicht. Aus diesem Arbeitsvorrat schließen wir die Kanten aus, an denen sich dieser Thread für jede Gabel entschieden hat. Dann migrieren wir den lokalen Arbeitsvorrat zum globalen, wenn der Thread die Sackgasse erreicht. Daher wird die Synchronisation für Leerlauf-Threads verwendet, um von Punkten aus der globalen Arbeitsliste zu starten.

Answer 2

Wenn Sie rekursive parallele Arbeit in Java zu tun, verwenden Sie die Gabel und API in Java eingeführt Join 7.

public class MazeNode { 
    // This class represents a Path from the start of your maze to a certain node. It can be a) a dead end, b) the exit, c) have child Paths 
    ... 
} 

public class MazeTask extends RecursiveTask<MazeNode> 
{ 
    private MazeNode node; 

    MazeTask(MazeNode node) { 
    this.node = node; 
    } 


    // Returns null or the exit node 
    @Override 
    protected MazeNode compute() {  
    if (node.isDeadEnd()) 
    return null; 
    else if (node.isExit()) 
    return node; 
    else { // node has ways to go 
    // implement as many directions as you want 
    MazeTask left = new MazeTask(node.getLeft()); 
    MazeTask right = new MazeTask(node.getRight()); 

    left.fork(); // calculate in parallel 

    MazeNode rightNode = right.compute(); // calculate last Task directly to save threads 
    MazeNode leftNode = left.join(); // Wait for the other task to complete and get result 

    if (rightNode != null) 
     return rightNode; 
    else 
     return leftNode; // This assumes there is only one path to exit 
    } 
} 


public static void main(String[] args) { 
    MazeNode maze = ... 
    MazeNode exit = new ForkJoinPool().invoke(new MazeTask(maze)); 
}