- 後戻り法のアルゴリズム
- 一定の順序で変数を逐次的に具体化する
ことにより領域(解候補集合)を系統的に探索する手法．以下で特長つけられる．
- 任意の述語に対して引数として与えられた変数値が全て具体化されると， その真理値を決定する．
- ある述語が偽になると，その領域にまだ割り当てていない値が残ってい る変数で，最後に選択したものに後戻りし，その変数を次の値で具体化する．
- 以下を仮定すると後戻り法の最悪計算量は O(ae)となる．
- 制約ネットワークのアーク数:e
- 各領域Diの要素数: a(簡単のために全て同じとする)
...Return