情報処理学会 第73回全国大会講演要旨

HDA*アルゴリズムは，代表的な最良優先探索であるA*アルゴリズムを
効果的に並列化するアルゴリズムである．しかし，A*は探索結果をす
べてメモリ上に保持するため，HDA*においてもメモリの省力化が課題
である．また，超大規模並列時にスケールが悪くなることが分かって
おり，並列オーバーヘッドの解析が望まれている．
本研究では，HDA*よりも少ないメモリ量で並列探索を行えるアルゴリ
ズムHash Distributed Constant Space A*(HDCSA*)を提案し，マル
チプルアラインメント問題に適用することでそのメモリ削減効果を実
験的に評価する．また，HDA*の並列探索中に発生するオーバーヘッド
を計測し，オーバーヘッドを低減させる，マルチプルアラインメント
依存および非依存の改良を行う予定である．