AI ( Parallel graph search ) : 並列グラフ探索の参考文献

趣味で, 並列グラフ探索について調べてみました. 手法は大きく分けて 2 通りあります.

• 中央集権型アプローチ
  • プロセッサ間で, ノードの Open list を共有メモリ上に共有します.
• 分散型アプローチ
  • プロセッサごとに Open list を持って, 良いノードの情報を交換し合います.
  • 情報の共有方法としては, Blackboard 型, Random 型, Ring 型があります.

以下に参考文献をピックアップします.

• 論文
  • "Parallel Best-First Search of State-Space Graphs: A Summary of Results (1988)". Vipin Kumar , K. Ramesh, V. Nageshwara Rao.
    • 並列グラフ探索の各手法の説明と, 測定結果について書いてあります.
    • http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.6224
  • "Parallel Astar Search on Message-Passing Architectures". Z. Cvetanovic, C. Nofsinger.
    • メッセージパッシングによる分散型の A* の手法とパフォーマンスの測定について書いてあります.
    • https://bioinformatics.cs.vt.edu/~guos/parallel/00205103.pdf

• 本
  • "並行コンピューティング技法 ―実践マルチコア/マルチスレッドプログラミング". Clay Breshears, 千住 治郎.
    • Chapter 10 に深さ優先探索をスレッドで並列化したコードがあります.
  • "Introduction to Parallel Computing". Ananth Grama, George Karypis, Vipin Kumar , Anshul Gupta.
    • Chapter10, Chapter11 にグラフ探索, 並列グラフ探索について書いてあります.
  • "Algorithms Sequential & Parallel: A Unified Approach". Laurence Boxer, Russ Miller.
    • Chapter 12 に並列グラフ探索について書いてあります.