Forward Checking は、バックトラックにおけるテクニック。まずは、具体的に示す。 例えば、グラフ彩色問題において、ノード0,1,2があって、制約辺が(i,i+1 (mod 3)) (i=0,1,2)にあるとする。さらに、各ノードの持つ変数の定義域が{blue,red,green}とする。 …

貪欲アルゴリズムの証明方法を調べていた。参考は、アルゴリズムデザインで、試しに 硬貨のの種類と枚数 金額A が、与えられたとき、最小の硬貨の枚数で金額Aを達成したい。これを求めるアルゴリズムを求めよ。ただし、そのような支払方法は少なくとも一つは…