并行深度优先搜索

Question

我正在实现一个深度优先搜索算法，用于寻找迷宫的出口，目前使用的是单线程。

我计划通过创建多个线程来提高效率，这些线程将使用相同的单线程算法搜索树，但在遇到交叉口时，我会随机选择下一步走向。

例如，当线程遇到可以向东或向西走的交叉口时，其中一半线程向东走，另一半线程向西走。直到其中一个线程找到了解决方案路径为止，这样持续进行。

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

- Kingamere

---

迷宫可能有循环吗？ - ajb

no cycles or loops - Kingamere

这将是一个搜索，应该能够正常工作。它不会按照标准定义成为深度优先搜索，但这并不重要。如果迷宫是一棵树，那么实现起来就很简单。如果它是一个图，则同步变得很重要。 - Gene

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

- piegames

Answer 2

[更新1]

这是我的提案，使用线程同步（但根据我们与@IraBaxter的讨论，我不确定我的方法是否有任何优势）：

当算法开始时，只需要一个线程，直到到达第一个分叉点。当这个线程到达那里时，它应该将所有可能的结果（左、右、中间）放入堆栈中并停止自己。然后，由于堆栈中有一些元素，几个线程被激活以从存储在堆栈中的边缘开始。当这些线程中的每一个到达分叉点时，所有结果都被放入堆栈中，并且线程停止自己（不是同时停止，而是在需要时停止），并从堆栈中取出边缘。如此循环进行。每当任何线程停止（无论是因为分叉还是死路）时，它都会切换到等待堆栈中的边缘模式（如果堆栈不为空，则取出一个）。每当向堆栈添加某个边缘时，线程都会被通知堆栈非空。

我在这里使用了“边缘”一词，意思是分叉点的位置加上从给定分叉点出发的方向。堆栈使您获得了深度优先算法的属性。

PS：通过减少同步点的数量，可以优化这种方法。我们可以为每个线程收集分叉边缘，并且在它到达死路之前不停止该线程。我们从此工作列表中排除了该线程决定在每个分支上继续的那些边缘。然后，当线程到达死路时，我们将本地工作列表迁移到全局工作列表中。因此，同步用于空闲线程从全局工作列表中开始。

- rsutormin

---

你正在“堆栈”中积累分支（我认为你指的是任意一组未探索的分支；这通常称为“工作列表”）。为了以线程安全的方式执行此操作，您需要同步集合访问。如果生成分支的成本很小（对于N拼图甚至国际象棋而言），同步成本将淹没此算法，并且串行DFS将更快。 - Ira Baxter

@IraBaxter，你可能是对的。那么如果我们减少同步点的数量呢？我们可以为每个线程收集分叉边并将其放入单独的工作列表中，在线程到达死胡同之前不停止该线程。我们从这个工作列表中排除了该线程决定在每个分支上走的那些边。然后当线程到达死胡同时，我们将本地工作列表迁移到全局工作列表中。因此，同步用于空闲线程从全局工作列表中的点开始。 - rsutormin

在我看来，更明智的做法是从搜索树的顶部开始并行搜索，并为每个找到的分支进行分叉。一旦发生了足够数量的顶级分叉以使所有处理器保持繁忙状态，只需让每个处理器在其所拥有的子树上运行DFS即可。因此，您在树的顶部具有带有同步成本的工作列表，但在分配给处理器的子树中，运行DFS（与单线程情况下一样便宜）。同步开销比率变得非常小，因为搜索树通常呈指数增长。 - Ira Baxter

@IraBaxter，但你提出的问题是树可能不平衡，因此如果某个线程完成其子树，则无法帮助其他线程。 - rsutormin

现在没有时间来描述解决方案，但是这里有一个链接，可以了解背景思想，然后使用工作并行DFS：https://dev59.com/questions/dnVD5IYBdhLWcg3wHn2d#1344944 - Ira Baxter