二分決定グラフによる離散構造処理の概観
Vol.97 No.12pp.1074-1079
発行日:2014/12/01
Online ISSN:2188-2355
Print ISSN:0913-5693
種別:小特集 「フカシギの数え方」から広がるアルゴリズムの理工学――二分決定グラフによる離散構造処理と広がる応用分野――
専門分野:
キーワード:
二分決定グラフ, BDD, ZDD, 離散構造, 理論演算,
本文:PDF(758.2KB)>>
あらまし:
論理関数や集合などの基本的な離散構造データを効率良く演算処理することは,様々な応用分野に共通する基盤技術として非常に重要である.本稿ではBDD(Binary Decision Diagram,二分決定グラフ)及びZDD(Zero-suppressed BDD,ゼロサプレス型BDD)を用いた離散構造データの処理技法を概観する.まずBDDによるブール演算処理,ZDDによる組合せ集合の代数処理について述べ,次に文字列集合や順列集合への発展について述べる.更に最近注目されているグラフ列挙の手法や,その適用例である「おねえさんの問題」など,本研究分野における最近の展開について紹介する.