弱コミットメント戦略を用いた制約充足問題の解法
情報処理学会論文誌, Vol.35, No.8. pp. 1540--1548, 1994.


制約充足問題の解を探索するバックトラッキングアルゴリズムにおいては, 探索途中で構成された部分解は, 解の一部分とならないことが判明しない限り 修正されることはない. このため, 探索中に解になり得ないような部分解を構成した場合, その部分解を含むすべての解に関する網羅的な探索が必要となり, 探索の効率は著しく低下する. そのような部分解を構成しないための, 変数の値の選択のヒューリスティックとして 制約違反最少化ヒューリスティックが提案されているが, 解になり得ない部分解を構成することを完全に避けることは 一般に不可能である.

本論文では, 部分解に弱くコミットする, 制約違反最少化ヒューリスティックを用いた新しい探索アルゴリズムを提案する. この方法によれば, 部分解が成長している間は, その部分解を変更しないが, ある変数に関して, 部分解と制約を満たす値が存在しない場合には, それまで構成された部分解を放棄し, 改めて部分解の構成を最初からやり直すことにより, 解になり得ない部分解に関する網羅的な探索を回避する.

確率的モデルおよび実験結果を用いて, バックトラッキングアルゴリズムに対する本アルゴリズムの優越性を示す. さらに, 実験結果を用いて, 近年, バックトラッキングアルゴリズムより効率的であることが示された, 状態空間探索型のアルゴリズムに対する 本アルゴリズムの優越性を示す.