深さの最初の並行検索

Question

私は迷路の出口を見つけるためにDFSを実装しており、現在はシングルスレッドです。

同じシングルスレッドアルゴリズムを使用してツリーを検索するいくつかのスレッドを作成することでより効率的にする予定ですが、交差点に出くわすときにどの方向に入るかをランダム化しています。

たとえば、スレッドは、東または西に行くことができる交差点に遭遇します。彼らの半分は東へ行き、半分は西へ行く。これは、スレッドの1つが解のパスを見つけるまで続きます。

DFSを並列に実装する有効な方法ですか？

Answer 1

[UPDATE1]ここ

は、スレッドの同期と私の提案である（しかし@IraBaxterとの議論に基づいて、私は私の方法は、任意の利点を与えることはもうわからない）：

アルゴリズムは一つだけを開始するとあなたが最初にフォークするまでスレッドが必要です。この1つのスレッドがそこに着くと、それはすべての可能な結果（左、右、中央）をスタックして停止する必要があります。スタックにいくつかの要素があるので、いくつかのスレッドがスタックに格納されたエッジから開始するように起動されます。これらのスレッドがそれぞれフォークに到達すると、すべての結果がスタックに置かれ、スレッドが停止します（一度にすべてではなく、それぞれが必要なときに実行されます）。等々。スレッドが停止するたびに（フォークまたはデッドエンドに関係なく）、スタック内のエッジを待っているモードに切り替わります（スタックが空でない場合は1を取ります）。スタックに何らかのエッジが追加されるたびに、スレッドはスタックの非空白について通知されます。

ここでは、指定されたフォークからどこに行くのかフォークの位置の意味で「エッジ」という用語を使用しました。 Stackは、アルゴリズムの深さ優先プロパティを提供します。

PS：同期点の数を減らすことでこのアプローチを最適化することは可能です。すべてのスレッドについて別々のワークリストにフォークエッジを収集し、行き止まりに達するまでこのスレッドを停止しないでください。この作業リストから、このスレッドが各フォークに行くことを決めたエッジを除外します。次に、スレッドがデッドエンドに達したときに、ローカルワークリストをグローバルワークリストに移行します。アイドル状態のスレッドは、グローバルワークリストのポイントから開始するために同期が使用されます。あなたはJavaで再帰的な並列作業を行う場合

Answer 2

、フォークを使用して迷路のサイクルを持ってもらえ

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)); 
}