與MPI的數獨並行化

Question

我想將我的數獨解算程序與MPI並行化。當前的序列代碼依賴於深度優先搜索的回溯。我做了一些研究，但我仍然不確定如何去做。有些人說，程序必須進行廣度優先搜索才能在主進程中獲取一些數據，然後使用這些數據使用從進程。因此，從屬進程將使用這些數據進行深度優先搜索。

此外，我看到一些深度優先搜索並行化示例使用工作共享或工作竊取方法。但是在數獨的情況下，我不確定使用這種技術可以處理流程關係，工作隊列和流程規模，因爲數獨的解決方法。

任何想法？

謝謝。

Answer 1

這不是與Sudoku有關的答案，更重要的是您指定了串行算法使用深度優先搜索。深度優先搜索是一個已知爲difficult to parallelize的問題，儘管看起來並不是「固有串行」。

但是有並行的DFS實現。例如，這個1987 paper提出了一個並行DFS算法。總的原則是，每個處理器搜索不同的路徑集合，直到它到達一個葉子（或任意的搜索深度），並且當它完成時它是路徑的子集，選擇一個新的未探索分支。

如果您熱衷於實現並行DFS，我會建議您閱讀該文章並開始實施該算法。但是我認爲可能會有更多智能並行數獨算法不使用DFS，例如可以使用約束傳播來解決。