抄録
F-034
グラフ彩色インスタンス生成のためのGAに基づく極小非可解構造の導出
○水野一徳・早川大貴・佐々木整（拓大）・西原清一（筑波大）
本研究では，制約充足問題の代表的な例題であるグラフ彩色問題について，その可解性を判別するのに非常に手間のかかる難しい実問題（インスタンス）を組織的に生成する方法を開発している．本方法は，極小非可解構造（MUS）を互いに繰り返し埋め込むことにより，任意に大きいかつ難しいインスタンスを安定的に生成するものである．本報告では，本方法におけるMUSを遺伝的アルゴリズムを用いて導出する方法を提案する．また，提案方法によって導出されたMUSを用いて生成したインスタンスが，ランダム生成されたインスタンスより難しいこと，そのインスタンスを解く計算量が問題サイズの指数オーダになることを実験的に示す．