情報処理学会 第79回全国大会講演要旨

本研究では、制約充足問題における大域的な解の状態遷移、具体的には充足可能から充足不可能への状態遷移を可能とするような変数に着目し、このような制約充足問題における大域的な解に影響を及ぼす、バックボーン（充足可能となるすべての解で同じ割当をもつ変数）を包括するような変数をインフルエンシャル変数として定義する。さらに、インフルエンシャル変数の特定問題を定式化し、この問題を解く効率的なアルゴリズムを提案する。実験では、異なるサイズ及びグラフ構造の色塗り問題を用いて，インフルエンシャル変数を求め、そこから得られたデータを用いてインフルエンシャル変数の特性等についての考察を行う。