超大規模なグラフ構造の効率的な処理技術
Vol.97 No.12pp.1097-1102
発行日:2014/12/01
Online ISSN:2188-2355
Print ISSN:0913-5693
種別:小特集 「フカシギの数え方」から広がるアルゴリズムの理工学――二分決定グラフによる離散構造処理と広がる応用分野――
専門分野:
キーワード:
グラフ探索, 並列化, 分散メモリ環境, 共有メモリ環境, 極小ヒッティング集合, 列挙,
本文:PDF(581.4KB)>>
あらまし:
本稿では,大規模グラフ処理に関する三つの異なる課題を挙げ,実用上の性能を向上させる手法について解説する.はじめに,列挙問題における網羅的な場合分け処理を二分決定グラフを用いて効率化させる方法について述べる.次にSimpathアルゴリズムの並列化においてメモリ共有環境の性質を考慮し性能を向上させる例について述べる.そして,ゲーム木探索の大規模並列化におけるGPS将棋の例を述べ,分散ハッシュ表を用いた並列探索手法についても述べる.