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