ZDDとフロンティア法を取り巻く研究動向

井上　武

あらまし

井上　武

Vol.101 No.3pp.297-301

発行日:2018/03/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特集　グラフアルゴリズムの最先端

専門分野:

キーワード:
データ構造, アルゴリズム, グラフ, 最適化, 列挙,

本文:PDF(631.8KB)>>

あらまし:
本稿では，ZDDと呼ばれる圧縮データ構造と，フロンティア法というグラフ列挙アルゴリズムを紹介し，最適化や故障解析などへの応用例を述べる．ZDDは，四半世紀前にVLSI論理設計分野で生まれた．現在では人工知能の知識コンパイル分野などを中心に研究されており，フロンティア法との出会いによってグラフ問題への有望なアプローチの一つとなっている．本稿で紹介する電力網最適化のように扱いにくい制約条件を持つ問題であっても，実行可能な部分グラフを圧縮データ構造として「列挙」していくことで解空間を構造化し，最適化を行える．また，グラフ列挙に関する多くの問題は#P完全であることが知られており，そのような問題への挑戦は計算機科学の観点から興味深い．本稿はZDDとフロンティア法の基礎を解説するとともに，実問題への適用事例を幾つか紹介する．

あらまし

ログイン

メニュー