Vol.101 No.3 (2018/3)　目次へ

グラフアルゴリズムの最先端

小特集 13.

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

Research Trends in ZDD and Frontier-based Search

井上　武

井上　武　正員　日本電信電話株式会社NTT未来ねっと研究所

Takeru INOUE, Member (NTT Network Innovation Laboratories, NIPPON TELEGRAPH AND TELEPHONE CORPORATION, Yokosuka-shi, 239-0847 Japan).

電子情報通信学会誌　Vol.101 No.3 pp.297-301 2018年3月

©電子情報通信学会2018

abstract

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

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

1．は　じ　め　に

　制約条件を満たす部分グラフの列挙は，組合せ論やグラフ理論における基本問題の一つである．グラフ列挙に関する多くの問題は#P完全であることが知られている⁽¹⁾．#Pとは，NPに属する決定問題に対応した数え上げ問題の集合である．#P問題は対応するNP問題以上に難しく，計算機科学における極めて挑戦的な問題の一つである．初期に提案された列挙アルゴリズム⁽²⁾は，部分グラフを一つずつ出力し，一つ当りの計算時間でアルゴリズムの複雑さを解析していた．しかし，出力グラフ数は入力グラフの大きさに対して指数的に増加し得るため，かなり小さいグラフしか扱えなかった．

　近年，出力グラフ数に依存しないグラフ列挙アルゴリズム⁽³⁾^,⁽⁴⁾が提案された．その一つであるSimpath⁽⁴⁾は，指定された頂点間にある全てのパスを，ZDD（Zero-suppressed Dinary Decision Diagram）⁽⁵⁾という圧縮データ構造で出力する．ZDDは集合族（組合せの集合）を表すデータ構造であり，多くの組合せに共通して現れる部分的な組合せをまとめて表現することで，ある種の圧縮を行う．グラフを「頂点や辺の組合せ」として定義すれば，グラフの集まりを集合族と見ることができ，ZDDで圧縮できる．ZDDを用いた列挙アルゴリズムの計算量は，出力グラフ数ではなくZDDの大きさに依存するようになる．多くのグラフが同じ部分構造を共有していれば，圧縮が効いてアルゴリズムの効率が高まる．以降，本稿で「列挙」というときは，グラフを一つずつ並べるのではなく，グラフの集合を表すZDDの構築を意味する．フロンティア法⁽⁶⁾により，グラフ種ごとに設計されていた列挙アルゴリズムが一般化され，実問題に現れる複雑な条件にも対応できるようになった．

続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。また、会員になると豊富な豪華特典が付いてきます。

続きを読む(PDF)　　　バックナンバーを購入する　　　　入会登録

電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌会誌アプリのお知らせ

電子情報通信学会 - IEICE会誌アプリをダウンロード

小特集 13. ZDDとフロンティア法を取り巻く研究動向

1．は じ め に

1．は　じ　め　に