java - 并行深度优先搜索

Question

我正在实现一个 DFS 来寻找迷宫的导出，目前它是单线程的。

我计划通过创建多个使用相同的单线程算法搜索树的线程来提高效率，但我会在遇到交叉点时随机选择进入哪个方向。

例如，线程遇到一个交叉点，在那里它们可以向东或向西。其中一半向东，一半向西。这一直持续到其中一个线程找到解决方案路径。

这是并行实现 DFS 的有效方法吗？

Answer 1

如果您在 Java 中执行递归并行工作，请使用 Java 7 中引入的 Fork 和 Join API。

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