あらまし
二分決定グラフによる離散構造処理の概観
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による組合せ集合の代数処理について述べ，次に文字列集合や順列集合への発展について述べる．更に最近注目されているグラフ列挙の手法や，その適用例である「おねえさんの問題」など，本研究分野における最近の展開について紹介する．
ログイン
メニュー
Online ISSN:2188-2355
…ジュニア会員・学生員にお勧めの記事