制約充足問題の地形の解析
横尾 真
コンピュータソフトウェア(ソフトウェア科学会論文誌), Vol. 16, No.3, 1999.


制約充足問題を解く完全な探索アルゴリズムに関しては, 相転移が生じる付近の問題がもっとも難しいことは良く知られている. 一方, 山登り型の探索アルゴリズムに関しても, 相転移の付近の問題が, 解の個数は 多いにも関わらず, より制約の強い解のある問題よりも難しくなる. 本論文ではこのような逆説的な状況が生じる理由を, 状態の評価値によって 形成される状態空間の地形を網羅的に解析することにより説明する. 解析結果は, 制約を加えることにより解の個数は減少するが, 局所最適 の個数も減少し, 結果として解に到達可能な状態が増加すること, また, 局所最適の個数が減少するのは, 互いに隣接した局所最適の集合(盆地) が, より小さな部分に分割されることに起因することを示している.