木探索と制約伝播

領域変数と制約を使って問題を表現したら、今度は変数の値を見つけねばなりません。（場合によっては、可能な値の集合を見つけるだけでもいいかもしれません。）値を見つけるのは制約伝播を伴った木探索によって行われます。

これは以下のようにして実行されます。

レベル n:

まだ即値化されていない（＝値が1つに決まっていない）領域変数 var を選択します。まだ即値化されていない変数がなければ問題は解けたことになります。
チョイスポイントを設定して、このレベルでのすべての領域変数の状態を記憶します。
領域に含まれる値valを選択し、変数 var をこの値に即値化してみます。
即値化の結果について以下の判断を行います。
- 即値化が失敗した場合(つまり、制約伝播によって矛盾が検出された場合)、直近のチョイスポイントに戻り、すべての領域変数の状態をこのチョイスポイントが設定されたときの状態に戻します(この「戻って復元する」プロセスをバックトラックと呼びます)。
- 即値化が失敗し、かつ varについてすべての可能な値をすでに試した場合には、レベルn-1 のチョイスポイントにバックトラックします。(もし n = 1 ならこの問題には解がないことになります)。
- 上記のいずれでもない場合には、次の n + 1 レベルを実行します。

iZ-Cライブラリでは、この基本的な木探索のアルゴリズムはiZ-Cの機能を使ってC言語で15行で書かれています。 (リファレンスマニュアルの 7.コンテキストを参照)。

この木探索では、制約伝播が上記のステップ3の選択された領域変数を選択された値に即値化してみるところで起きます。この制約伝播のメカニズムは、領域変数 var の領域に変化が起きたことをきっかけにして起動されます。このとき領域変数 \(V_{i}\) が制約 \(C_{i,j}\) によって変数 var に結びつけられていれば、変数var の新しい領域と制約 \(C_{i,j}\) に応じて変数 \(V_{i}\) の値が変化します。同様にして今度は変数 \(V_{i}\) が制約伝播のきっかけになるので、このメカニズムは再帰的に実行されます。

例として、2つの領域変数A と Bが以下のようにいずれも初期値として領域1..8 を持つとしたとき、以下の制約が設定されるものとしましょう。

A: {1..8}
B: {1..8}
A = B + 2

この制約が設定されると、以下のように領域変数の領域が変化します。

A: {3..8}
B: {1..6}

さらに A の領域を変更してみます。

A \(\neq\) 5

すると、制約伝播によりB \(\neq\) 3 となります。

また、B の領域を以下のように変化させると、

B \(\le\) 3

制約伝播により A \(\le\) 5 となります。

iZ-Cを使ったプログラム例と出力例を以下に示します。

プログラム例:

#include "iz.h"

int main(int argc, char **argv)
{
  CSint *A, *B;

  cs_init();

  A = cs_createNamedCSint(1, 8, "A");
  B = cs_createNamedCSint(1, 8, "B");

  cs_printf("%T\n%T\n", A, B);

  cs_Eq(A, cs_Add(B, CSINT(2)));
  cs_printf("\nAfter 'A = B + 2':\n%T\n%T\n", A, B);

  cs_NEQ(A, 5);
  cs_printf("\nAfter 'A != 5':\n%T\n%T\n", A, B);

  cs_LE(B, 3);
  cs_printf("\nAfter 'B <= 3':\n%T\n%T\n", A, B);

  cs_end();

  return 0;
}

出力例:

A: {1..8}
B: {1..8}

After 'A = B + 2':
A: {3..8}
B: {1..6}

After 'A != 5':
A: {3, 4, 6..8}
B: {1, 2, 4..6}

After 'B <= 3':
A: {3, 4}
B: {1, 2}

iZ-Cでは制約伝播は、制約を設定したとき（上の例ではcs_Add 制約を設定したとき）、あるいは CSint型の変数に何か変化が起きたときに自動的に実行されます。

iZ-Cには既述の木探索のメカニズムが、組み込みの関数として含まれています。 cs_search()はそうした関数の1つですが、引数としてfindFreeVar() 関数をとり、これによってCSint 型変数を選択する順序(既述の木探索のステップ1を参照)を制御することができるようになっています。

cs_search()関数の使い方を示すために、「覆面算」の問題に戻ります。

コード:

void printSolution(CSint **allvars, int nbVars)
{
  cs_printf("  %D\n", L1);
  cs_printf("* %D\n", L2);
  cs_printf("-----\n");
  cs_printf("  %D\n", L3);
  cs_printf(" %D \n", L4);
  cs_printf("%D  \n", L5);
  cs_printf("-----\n");
  cs_printf("%D  \n", L6);
  cs_printStats();
}

int main(int argc, char **argv)
{
  cs_init();

  constraints();
  cs_search(Digit, NB_DIGITS, cs_findFreeVarNbElements);
  printSolution(Digit, NB_DIGITS);

  cs_end();

  return 0;
}

出力:

  179
* 224
-----
  716
 358
358
-----
40096

Nb Fails = 114
Nb Choice Points = 181
Heap Size = 1024

出力された解は、114回のバックトラック（フェイルの回数）と181個のチョイスポイントののちに見つかりました。ここでcs_search()の引数として渡されているcs_findFreeVarNbElements() 関数はiZ-Cの組み込み関数で、即値化されていないCSint 型変数のうちもっとも領域の小さいもの、言い換えれば要素数の最も少ないものを返します。この戦略は、多くの場合に効率的ですが、自分で findFreeVar()を書き換えれば、別の戦略を実装することもできます。

また、選られた解が唯一のものであるかどうかが知りたくなるかもしれません。この場合にはcs_search()のかわりにcs_findAll()関数を使えば答を得ることができます。

コード:

int main(int argc, char **argv)
{
  cs_init();

  constraints();
  cs_findAll(Digit, NB_DIGITS, cs_findFreeVarNbElements, printSolution);
  cs_printStats();

  cs_end();

  return 0;
}

出力:

  179
* 224
-----
  716
 358
358
-----
40096

Nb Fails = 114
Nb Choice Points = 181
Heap Size = 1024

Nb Fails = 1436
Nb Choice Points = 2199
Heap Size = 2048

この「覆面算」が唯一の解を持つことがわかるまでに 1436 回のバックトラックが必要でした。なお、cs_findAll() の4番目の引数は解が1つ見つかるたびに呼ばれます。

この小さな例でもわかる通り、制約による問題解決は以下の 3ステップよりなります。

領域変数を宣言します。
領域変数間の制約を表現します。
制約を充たす変数の値を見つけます。

iZ-Cは...

第1の点については - CSint 型の変数を提供します。
第2の点については - 多くの組み込みの制約を提供するとともに、新しい利用者定義の制約を定義する方法も提供します (「デモンを用いた制約の定義」を参照してください)。
第３の点については - 組み込みの木探索の関数を提供するとともに、新しい利用者提供のヒューリスティクスを定義する方法も提供します (リファレンスマニュアルの「ヒューリスティクスと生成のメカニズム」および「コンテキスト」を参照してください)。