あらまし

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