あらまし

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

川原　純 斎藤　寿樹 湊　真一 

Vol.95 No.6pp.505-511

発行日:2012/06/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特集　広がる列挙の技術──列挙による問題解決アプローチ──

専門分野:

キーワード:
フロンティア法, ZDD, 部分グラフの列挙, リンクパズル, 電力網, 

本文:PDF(698.9KB)>>

記事を購入

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

ログイン

 > 

パスワードを忘れた場合は

メニュー

Online ISSN:2188-2355

…ジュニア会員・学生員に
　お勧めの記事