著者

戸田 貴久 斎藤 寿樹 岩下 洋哲 川原 純 湊 真一

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.34, no.3, pp.3_97-3_120, 2017-07-25 (Released:2017-08-09)

---

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

著者

戸田貴久

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2013-AL-145, no.3, pp.1-8, 2013-10-30

---

論理関数の CNF が与えられるとき,その論理式を表す二分決定グラフ BDD を構築するための新しい手法を提案する.CNF は従来から用いられている論理関数の伝統的な表現法の一つである.BDD には論理関数を操作するための様々な演算が備わっているので,CNF よりも BDD を用いる方が適切な多くの問題がある.しかし,CNF から BDD の構築は自明な計算ではない.本稿では,まず CNF を表す中間表現を計算し,それから BDD に変換する二段階の BDD 構築法を提案する.さらに,提案法で中間表現として用いられるデータ構造は,BDD 構築だけでなく,有向グラフ上の列挙問題など様々な問題に対して有用であることも示す.