解探索とヒューリスティクス

iZ-Cが提供する解探索・生成メカニズムの基本原理は、以下の通りです。

  1. まだ即値化されていないCSint型変数を、CSint型変数の集合 allvarsから1つ見つけます。

  2. 見つけた変数 var の領域から値val を選んで、以下のようにしてこの値で即値化してみます。

    cs_EQ(var, val).

    即値化に失敗した場合は cs_NEQ(var, val) としてステップ2に戻ります。 即値化に成功した場合にはステップ1に行きます。

基本的な解探索

この関数は、allvars から参照可能なすべてのCSint型変数を即値化しようとします。解がなければFALSEを返します。 findFreeVar関数はallvarsの中から即値化されていないCSint型変数を1つ見つけて返すための関数です。

IZBOOL cs_Vsearch(int nbVars, CSint *vint, ...)

cs_Vsearch()は可変長引数をうけつけます(引数として渡される変数の数は第1引数 nbVarsで指定されるものとします)。

組み込みの選択関数

CSint *cs_findFreeVar(CSint **allvars, int nbVars)

allvars 中のCSint型変数で、即値化されていないもののうち、最初に見つかった(=添字番号が小さい) ものを返します。

CSint *cs_findFreeVarNbElements(CSint **allvars, int nbVars)

即値化されていないCSint型変数のうち、領域の要素数が最も少ないものを返します。 そのような変数が複数ある場合には、最初に見つかった (= 添字番号が小さい) ものを返します。

CSint *cs_findFreeVarNbElementsMin(CSint **allvars, int nbVars)

即値化されていないCSint型変数のうち、領域の要素数が最も少ないものを返します。 そのような変数が複数ある場合には、領域の最小値が最も小さいものを返します。

CSint *cs_findFreeVarNbConstraints(CSint **allvars, int nbVars)

即値化されていないCSint型変数のうち、設定されている制約の数が最も多いものを返します。

例えば、cs_findFreeVarNbElements() は以下のように定義できるでしょう。:

CSint *cs_findFreeVarNbElements(CSint **allvars, int nbVars) {
  int i;
  int nbElements, nbElementsOpt;
  CSint *varOpt = NULL;

  nbElementsOpt = INT_MAX;
  for (i = 0; i < nbVars; i++) {
    nbElements = cs_getNbElements(allvars[i]);
    if ((nbElements > 1) && (nbElements < nbElementsOpt)) {
      nbElementsOpt = nbElements;
      varOpt = allvars[i];
    }
  }
  return(varOpt);
}

フェイル数とチョイスポイント数

以下の関数を用いれば、フェイル数やチョイスポイント数を用いたヒューリスティクスを書くこともできます。

int cs_getNbFails()

この関数が呼ばれた時点までに発生したフェイルの数を返します。 フェイルを発生させる関数としては、以下があります。

int cs_getNbChoicePoints()

この関数が呼ばれた時点までに発生したチョイスポイントの数を返します。チョイスポイントを発生させる関数は、 cs_getNbFails() と同じです。

複雑な解探索関数

IZBOOL cs_searchCriteria(CSint **allvars, int nbVars, int (*findFreeVar)(CSint **allvars, int nbVars), int (*criteria)(int index, int val))

cs_search()ではCSint型変数 var が選ばれると、varの領域に含まれない値を飛ばしながら値を昇順に (cs_getMin(var) から cs_getMax(var) へと)試していきます。

cs_searchCriteria()を使えば、この選択の順序を制御することができます。 criteria()関数の返り値が最小になる値が最初に選ばれます。

IZBOOL cs_searchMatrix(CSint ***matrix, int NbRows, int NbCols, int (*findFreeRow)(CSint ***matrix, int NbRows, int NbCols), int (*findFreeCol)(int row, CSint **Row, int NbCols), int (*criteria)(int row, int col, int val))

cs_search()cs_searchCriteria() はCSint型変数のベクトルについて解を生成するために使われます。

cs_searchMatrix() はマトリックスに対して同じ目的で使われます。 findFreeRow()は選択したい行のインデックスを返します。 行が選ばれるとfindFreeCol() が選択された列のインデックスを返します。 CSint型変数 (Col, Row) が選択されるとcriteria()関数の返り値が最小になる値が選ばれます。

IZBOOL cs_searchFail(CSint **allvars, int nbVars, CSint* (*findFreeVar)(CSint **allvars, int nbVars), int NbFailsMax)

cs_searchFail() はバックトラックの回数がNbFailsMaxを超えたら停止し。FALSEを返す(つまりフェイルする)ことを除けば cs_search() と同じです。

NbFailsを調べれば、フェイルが発生した理由がバックトラックの制限によるものかどうかを知ることができます。 (cs_getNbFails() 関数を参照。)

IZBOOL cs_searchCriteriaFail(CSint **allvars, int nbVars, int (*findFreeVar)(CSint **allvars, int nbVars), int (*criteria)(int index, int val), int NbFailsMax)

cs_searchCriteriaFail()はバックトラックの回数がNbFailsMaxを超えたら停止し。FALSEを返す(つまりフェイルする)ことを除けば cs_searchCriteria()と同じです。

NbFailsを調べれば、フェイルが発生した理由がバックトラックの制限によるものかどうかを知ることができます。 (cs_getNbFails() 関数を参照。)

IZBOOL cs_searchMatrixFail(CSint ***matrix, int NbRows, int NbCols, int (*findFreeRow)(CSint ***matrix, int NbRows, int NbCols), int (*findFreeCol)(int row, CSint **Row, int NbCols), int (*criteria)(int row, int col, int val), int NbFailsMax)

cs_searchMatrixFail() はバックトラックの回数がNbFailsMaxを超えたら停止し FALSE を返す(つまりフェイルする)ことを除けば cs_searchMatrix()と同じです。

NbFailsを調べれば、フェイルが発生した理由がバックトラックの制限によるものかどうかを知ることができます。 (cs_getNbFails() 関数を参照。)

IZBOOL cs_findAll(CSint **allvars, int nbVars, CSint* (*findFreeVar)(CSint **allvars, int nbVars), void (*found)(CSint **allvars, int nbVars))

可能な解をすべて探索します。解が1つ見つかるたびにfound()関数が呼ばれます。 典型的なケースとしてfound()関数は解を表示するのに使われます。:

void found(CSint **allvars, int nbVars) {
  static NbSolutions = 0;
  printf("Solution %d\n", ++NbSolutions);
  cs_printf("%A\n\n", allvars, nbVars);
}
IZBOOL cs_minimize(CSint **allvars, int nbVars, CSint* (*findFreeVar)(CSint **allvars, int nbVars), CSint *cost, void (*found)(CSint **allvars, int nbVars, CSint *cost))

costを最小化する解を見つけようとします。 最小化のステップ毎にfound()関数が呼び出されます。 典型的なケースとして、found()関数はそのステップで得られた解を表示するのに使われます。:

void found(CSint **allvars, int nbVars, CSint *cost) {

  static NbSolutions = 0;

  printf("Solution %d\n", ++NbSolutions);
  cs_printf("%A\n", allvars, nbVars);
  cs_printf("Cost = %T\n\n", cost);
}

cs_minimize() は以下のように定義できます。:

IZBOOL cs_minimize(CSint **allvars, int nbVars, CSint* (*findFreeVar)(CSint **allvars, int nbVars),  CSint *cost, void (*found)(CSint **allvars, int nbVars, CSint *cost)) {
  char gFirst, g;
  gFirst = g = cs_search(allvars, nbVars, findFreeVar);
  while (g) {
    int currentCost = getMin(cost);
    found(allvars, nbVars, cost);
    cs_restoreAll();
    g = (cs_LT(cost, currentCost) && cs_search(allvars, nbVars, findFreeVar));
  }
  return gFirst;
}