[2I4-OS-9a] AIと制約プログラミング

[2I4-OS-9a-02] 決定グラフ上での最適なk-集合選択問題を高速に解くアルゴリズム

〇伝住 周平¹、西野 正彬¹、安田 宜仁¹ (1. 日本電信電話(株) NTTコミュニケーション科学基礎研究所)

キーワード：ZDD、制約最適化問題、動的計画法

ZDDは集合族を圧縮して表現することのできるデータ構造であるとともに，集合演算など多くの操作を圧縮したまま行うことができる処理系である．これまでにも入力のZDDサイズに依存する時間で計算を実行する手法が数多く提案されてきた．しかし，複数の集合間の関係を考慮する目的関数が与えられた場合に，その関数を最大化するようにZDDから複数の集合を選択する問題についてはこれまで効率良い解法が知られていなかった．本稿ではZDD上で効率的に計算を行える目的関数の条件を明らかにし，与えられたZDD上での動的計画法によって最適化を行う新しい演算を提案する．本手法により目的関数を集合の各要素ごとに分解できるような問題に対してはZDDのサイズに依存した計算時間で解を求めることができるようになった．そのような問題としては集合間ハミング距離の総和が大きくなるように集合を選ぶ多様性最大化問題や各要素の数によってスコアが決まるような問題，（厳密）集合被覆問題などが考えられる．また，提案手法を実装し複数の ZDD に対して計算機実験を行いその性能を確認した．