algorithm - 数独并行化与 MPI

Question

我想将我的数独求解程序与 MPI 并行化。当前的序列代码依赖于深度优先搜索的回溯。我做了一些研究，但我仍然不知道该怎么做。有人说程序必须进行广度优先搜索才能在主进程中获取一些数据，然后使用从进程处理这些数据。这样从属进程将使用此数据进行深度优先搜索。

我还看到一些深度优先搜索并行化示例使用工作共享或工作窃取方法。但是在数独的情况下，由于数独的求解方法，我不确定使用这种技术是否可以处理进程关系、工作队列和进程大小。

有任何想法吗？

谢谢你。

Answer 1

这不是与数独有关的答案，更多的是因为您指定串行算法使用深度优先搜索。深度优先搜索是一个众所周知的难以并行化的问题，尽管它看起来不是“本质上是串行的”。

然而，有并行的 DFS 实现。例如，这篇1987 年的论文提出了一种并行 DFS 算法。一般原则是每个处理器搜索一组不同的路径，直到它到达一个叶子（或任意搜索深度），当它完成它的路径子集时，选择一个新的未探索分支。

如果您热衷于实现并行 DFS，我建议您阅读该文章并尝试实现该算法。但是我认为可能有更智能的并行数独算法不使用 DFS，例如它可以使用约束传播来解决。