Forward Checking

Forward Checking は、バックトラックにおけるテクニック。まずは、具体的に示す。
例えば、グラフ彩色問題において、ノード0,1,2があって、制約辺が(i,i+1 (mod 3)) (i=0,1,2)にあるとする。さらに、各ノードの持つ変数の定義域が{blue,red,green}とする。
このとき、まずノード１において、blueを選択したとき、ノード2，3では、blueは制約に矛盾するので、削除する。次に、ノード２において、redを選択すると、ノード3で、redは矛盾するので削除する。で、最後にノード3でgreenが選択される。
このように、ある変数で選択したとき、将来に選択される変数において、矛盾する値を削除していく手法である。
以下、値の選択する手続きの擬似コード。x_iで、iが小さい順に値が選択されていくとする。そして、各変数の今、生き残っているドメインをD'_iとする。

while D'_iが空でない
　D'_iから値aを選択。D'_iからaを削除
　　　for 全てのk,i<k<=n
　　　　　for 全てのb in D'_k
　　　　　　　if(x_1からx_(i-1),x_i=a,x_k=b となる部分解が矛盾する)
　　　　　　　　　bをD'_kから削除
　　　　　end for
　　　　　if D'_kが空である
             D'_kをaを選択する前に戻す
          else
             return a
      end for
end while
return null

どうして、こんな話をいきなりするのかというと、constraint processingを読んでいるから。英語が厄介すぎて、なかなか分からなすぎてつらい。なので分かったところだけまとめていくことにする。

Constraint Processing (The Morgan Kaufmann Series in Artificial Intelligence)

posted with amazlet at 11.05.15

Rina Dechter
Morgan Kaufmann
売り上げランキング: 275987

Amazon.co.jp で詳細を見る