ZDDと列挙問題―最新の技法とプログラミングツール

摘要

列挙問題とは，与えられた条件を満たす対象(解)をすべて求める問題であり，電力網解析など社会のさまざまな問題への応用がある．さまざまな組合せ列挙問題に対して，問題の解集合を表現するデータ構造ZDDを高速に求める方法(トップダウンZDD構築法)を通して元の問題を効率的に解く汎用的な手法の研究が近年盛んに行われている.本論文ではトップダウンZDD構築に焦点を絞り，基礎となるアルゴリズムから，複雑な問題制約に対処するための発展的手法，プログラミングツールTdZddの基本的な使い方，さらに，具体的な応用問題を例にしたプログラミングまで解説する.