家系木に基づく列挙アルゴリズムの並列化手法の提案と線形拡張の列挙アルゴリズムの実装

摘要

家系木構造を用いた列挙アルゴリズムが広く研究され，要素一つあたり定数時間で出力できる高速なものも知られているが，構造によっては得られる要素の数が膨大であるため，高速な計算機を用いても全列挙には時間がかかってしまう.近年の計算機環境は，並列化によって高速化を実現するものが多くなっていることから，列挙アルゴリズムも並列化を行うことで，より高速な列挙を実現することが可能になると考えられる. 本研究では，家系木の分割手法の一つを提案し，家系木を用いた列挙アルゴリズムをMPI(Message Passing Interface)により並列化して実行できるフレームワークを提案する.また，本フレームワークの効果を検証するために，与えられた半順序集合から，全ての線形拡張を列挙するアルゴリズムを実装し，処理速度の評価を行った.