pp293
和佐州洋
膨大かつ複雑なデータから有用な情報を抽出
グラフで記述された複雑なデータから有用な情報を抽出する重要性が，SNSや生命科学など分野を問わずに増している．列挙アルゴリズム，すなわち，与えられたデータから，制約を満たす部分構造を全て出力するアルゴリズムは，このような要請を実現するための基盤技術の一つである．本稿では，列挙アルゴリズムに関する評価方法，困難性の判定，及び，代表的な技法について，現在の状況を解説する．
小特集 グラフアルゴリズムの最先端 13. ZDDとフロンティア法を取り巻く研究動向 Research Trends in ZDD and Frontier-based Search
pp297
井上 武
制約条件を満たすグラフを全て列挙する
本稿では，ZDDと呼ばれる圧縮データ構造と，フロンティア法というグラフ列挙アルゴリズムを紹介し，最適化や故障解析などへの応用例を述べる．ZDDは，四半世紀前にVLSI論理設計分野で生まれた．現在では人工知能の知識コンパイル分野などを中心に研究されており，フロンティア法との出会いによってグラフ問題への有望なアプローチの一つとなっている．本稿で紹介する電力網最適化のように扱いにくい制約条件を持つ問題であっても，実行可能な部分グラフを圧縮データ構造として「列挙」していくことで解空間を構造化し，最適化を行える．また，グラフ列挙に関する多くの問題は#P完全であることが知られており，そのような問題への挑戦は計算機科学の観点から興味深い．本稿はZDDとフロンティア法の基礎を解説するとともに，実問題への適用事例を幾つか紹介する．