数独ソルバー プログラムを MPI で並列化したいと考えています。現在のシリアル コードは、深さ優先検索によるバックトラッキングに依存しています。私はいくつかの研究をしましたが、私はまだそれを行う方法がわかりません。プログラムは幅優先検索を実行してマスター プロセスでデータを取得し、このデータでスレーブ プロセスを使用する必要があると言う人もいます。スレーブプロセスがこのデータを使用して深さ優先検索を行うようにします。
また、深さ優先検索の並列化の例では、ワーク シェアリングやワーク スティーリングの手法が使用されていることもわかりました。しかし、数独の場合、数独の解決方法のために、この手法を使用してプロセスの関係、作業キュー、およびプロセスのサイズを処理できるかどうかはわかりません。
何か案は？
ありがとうございました。
これは、数独に関する回答ではなく、シリアル アルゴリズムが深さ優先検索を使用することを指定するという事実に関するものです。深さ優先探索は、「本質的にシリアル」に見えないにもかかわらず、並列化が難しいことが知られている問題です。
ただし、並列 DFS 実装があります。たとえば、この1987 年の論文では、並列 DFS アルゴリズムが紹介されています。一般的な原則は、各プロセッサがリーフ (または任意の検索深度) に到達するまで異なるパスのセットを検索し、パスのサブセットが完了すると、新しい未調査の分岐を選択することです。
並列 DFS を実装したい場合は、その記事を読んで、そのアルゴリズムを実装してみることをお勧めします。ただし、DFS を使用しないよりインテリジェントな並列数独アルゴリズムがおそらくあると思います。たとえば、制約伝播を使用して解決できます。