ZDDを用いた新たな列挙手法

摘要

近年，グラフ上の2点間のパスを列挙する高速なアルゴリズムがKnuthによって提案された．一般的な列挙アルゴリズムは解空間を探索し,解を一つ一つ出力するのに射し，KnuthのアルゴリズムはZero－Suppressed Binary Decision Diagram（ZDD）と呼ばれるデータ構造を用いて，全解をコンパクトに表現して出力する．我々はKnuthのアルゴリズムをフロンティア法と名付けて一般化し，様々なグラフ構造の列挙に適用した．本稿ではフロンティア法について解説し，リンクパズルの求解や配電網構成の列挙への応用を述べる．