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

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

まだ即値化されていないCSint型変数 var を、CSint型変数の集合 allvars から1つ見つけます。即値化されていない変数が見つからなければ(全ての変数が即値化されていれば)、探索は終了です。
見つけた変数 var の領域を縮小します。例えば、値 val を選んで、以下のようにしてこの値で即値化してみます。: cs_EQ(var, val)
- 領域の縮小に失敗した場合は、ステップ 2に戻って別の縮小方法を試します。例えば、別の値 val2 を選択します。
- 即値化に成功した場合にはステップ1に行きます。

基本的な解探索

IZBOOL cs_search(CSint **allvars, int nbVars, CSint *(*findFreeVar)(CSint **allvars, int nbVars)): この関数は、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()

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

cs_search()
cs_searchFail()
cs_Vsearch()
cs_searchCriteria()
cs_searchCriteriaFail()
cs_searchValueSelectorFail()
cs_searchValueSelectorRestartNG()
cs_searchMatrix()
cs_searchMatrixFail()
cs_findAll()
cs_minimize()

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_searchValueSelectorFail(CSint **allvars, const CSvalueSelector **selectors, int nbVars, int (*findFreeVar)(CSint **allvars, int nbVars), int NbFailsMax, const CSsearchNotify *notify)

cs_searchValueSelectorFaill() は、findFreeVar で allvars から選択した変数に対して、selectors で指定された方法で領域を縮小して探索を行います。selectors は cs_getValueSelector() あるいは cs_createValueSelector() で生成される CSvalueSelector 型の変数へのポインタの配列で、探索対象の CSint型変数 var の配列と同じサイズ(すなわち nbVars)である必要があります。

NbFailsMax の利用方法は cs_searchFail() と同じです。

notify は CSsearchNotify 型の変数へのポインタであり、ここにセットされたコールバック関数が探索の各フェーズで呼び出されます。詳細は cs_createSearchNotify() を参照してください。

IZBOOL cs_searchValueSelectorRestartNG(CSint **allvars, const CSvalueSelector **selectors, int nbVars, int (*findFreeVar)(CSint **allvars, int nbVars), int (*maxFailFunction)(void *state), void *maxFailState, int nbFailsMax, CSnoGoodSet *ngs, const CSsearchNotify *notify)

cs_searchValueSelectorRestartNG() は、cs_searchValueSelectorFail() に対してリスタートおよび NoGood の機能を付加したものです。maxFailFunction が探索の開始時に呼び出され、許容されるフェイルの上限が決定されます。探索のフェイル数がこの上限に到達すると、全ての探索を再度実行し直します。 maxFailFunction の呼び出し時には引数として maxFailState が与えられます。

探索の再実行では、再び同じフェイルが発生しないようにするために、フェイルが発生した条件(NoGood)を cs_createNoGoodSet() で生成された変数 ngs に記録します。(実行速度やメモリの制限から記録される NoGood は発生したフェイルの一部分のみです)

ngs および notify の機能が不要な場合は NULL を渡すことができます。

典型的な呼び出し方は以下のようになります:

static int findFreeVarIndex(CSint **allvars, int nbVars) {
    for (int i = 0; i < nbVars; i++) {
        if (cs_isFree(allvars[i]))
            return i;
    }

    return -1;
}

static int nextFail(void* state) {
    int* pn = (int*)state;
    int ret = *pn;

    *pn = ret + 10;

    return ret;
}

/* ... */
    const CSvalueSelector** vs = malloc(sizeof(CSvalueSelector*) * nbVars);
    CSnoGoodSet* ngs = cs_createNoGoodSet(allvars, nbVars, NULL, 0, NULL, NULL);
    CSsearchNotify* notify = cs_createSearchNotify(NULL);

    int fail = 10;

    for (int i = 0; i < nbVars; i++) {
        vs[i] = cs_getValueSelector(CS_VALUE_SELECTOR_MIN_TO_MAX);
    }

    cs_searchValueSelectorRestartNG(allvars, vs, nbVars, findFreeVarIndex, nextFail, &fail, 100000, ngs, notify);
/* ... */

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;
}

解探索関数の中断

void cs_cancelSearch(void): 現在実行中の探索を安全な位置で中断します。この関数は探索を実行しているスレッドとは別のスレッドから呼び出すことが可能です。必要があれば cs_restoreContextUntil() を使用してコンテキストを復帰してください。

領域縮小方法の指定

以下の探索関数では、CSvalueSelector型の変数を引数に渡すことで、領域の縮小方法として即値化(領域から値を1つ選択する)以外の方法を指定することができます。

cs_searchValueSelectorFail()
cs_searchValueSelectorRestartNG()

組み込みの領域縮小方法の指定

const CSvalueSelector *cs_getValueSelector(int vs)

組み込みの領域縮小を実施するための CSvalueSelector を得ます。vs としては以下の値を指定できます。

CS_VALUE_SELECTOR_MIN_TO_MAX: 領域の最も小さい値から順に試す。

CS_VALUE_SELECTOR_MAX_TO_MIN: 領域の最も大きい値から順に試す。

CS_VALUE_SELECTOR_LOWER_AND_UPPER: 最小値と最大値の平均値以下を試し、次にその値より大きい値を試す。

CS_VALUE_SELECTOR_UPPER_AND_LOWER: 最小値と最大値の平均値以上を試し、次にその値より小さい値を試す。

CS_VALUE_SELECTOR_MEDIAN_AND_REST: 変数の領域の中央の値を試し、次に中央の値を取り除く。

ユーザ定義の領域縮小方法

組み込みの領域縮小方法外に、ユーザ独自の領域縮小方法指定を定義することもできます。このためには、cs_createValueSelector() で独自定義の関数を登録した CSvalueSelector 型の変数を生成し、CSvalueSelection 型の変数を解探索関数に返す必要があります。

CSvalueSelector *cs_createValueSelector(IZBOOL (*init)(int index, CSint **vars, int size, void *pData), IZBOOL (*next)(CSvalueSelection *r, int index, CSint **vars, int size, void *pData), IZBOOL (*end)(int index, CSint **vars, int size, void *pData))

独自の領域縮小方法を CSvalueSelector 型変数として定義します。init, next, end はそれぞれ初期化、領域縮小方法の取得、終了処理を行う関数をそれぞれ指定します。これらの関数の引数および返り値は以下の通りです。

init (一つの変数の領域縮小を開始する前に一回だけ呼ばれる関数)
- index : 領域縮小対象となる変数の配列vars 内の添え字
- vars : 探索対象となる変数の配列
- size : vars のサイズ
- pData : ポインタまたは整数を格納できる領域へのポインタ。状態を保持するための変数として利用できる。
- 返り値: 成功ならば TRUE
next (一つの変数の領域縮小を順次試していくために呼ばれる関数)
- r : 領域の縮小方法を受け取る CSvalueSelection 型変数へのポインタ。
- index : 領域縮小対象となる変数の配列vars 内の添え字
- vars : 探索対象となる変数の配列
- size : vars のサイズ
- pData : ポインタまたは整数を格納できる領域へのポインタ。状態を保持するための変数として利用できる。
- 返り値: 有効な r を返した場合は TRUE
end (一つの変数の領域縮小を終了する前に一回だけ呼ばれる関数)
- index : 領域縮小対象となる変数の配列vars 内の添え字
- vars : 探索対象となる変数の配列
- size : vars のサイズ
- pData : ポインタまたは整数を格納できる領域へのポインタ。状態を保持するための変数として利用できる。メモリをmallocなどで割り当てていた場合は解放する必要がある。
- 返り値: 成功ならば TRUE

返された CSvalueSelector 型変数は、不要になったら cs_freeValueSelector() で解放する必要があります。

void cs_freeValueSelector(CSvalueSelector *vs): cs_createValueSelector() で生成された CSvalueSelector 型の変数を解放します。

領域縮小方法に関連する型および関数

type CSvalueSelection

CSvalueSelection 型は変数の領域を縮小する方法を表現するもので、以下のように定義されています。:

typedef struct {
  int method;
  int value;
} CSvalueSelection;

valueフィールドに指定された値を使用して methodフィールドで指定された方法で変数の領域を縮小することを表現します。

method フィールドは以下の値をとります。

CS_VALUE_SELECTION_EQ: value に即値化することで領域を縮小する。

CS_VALUE_SELECTION_NEQ: value を取り除くことで領域を縮小する。

CS_VALUE_SELECTION_LE: value 以下とすることで領域を縮小する。

CS_VALUE_SELECTION_LT: value より小さくすることで領域を縮小する。

CS_VALUE_SELECTION_GE: value 以上とすることで領域を縮小する。

CS_VALUE_SELECTION_GT: value より大きくすることで領域を縮小する。

IZBOOL cs_initValueSelector(const CSvalueSelector *vs, int index, CSint **vars, int size, void *pData)

size 個の要素を持つ配列 vars の添え字 index で指定された CSint型変数に対して、領域の縮小を行うための準備を行います。 pData は、ポインタと int を格納するために十分な大きさを持ったメモリ領域へのポインタです。

成功した場合は TRUE が返されます。

IZBOOL cs_selectNextValue(CSvalueSelection *r, const CSvalueSelector *vs, int index, CSint **vars, int size, void *pData)

size 個の要素を持つ配列 vars の添え字 index で指定された CSint型変数に対して、領域の縮小方法を :c:type:CSvalueSelection: 型変数 r に返します。 pData には cs_initValueSelector() で渡したポインタを指定します。

この関数は呼び出される度に次の領域の縮小方法を r に返そうとし、返せた場合は戻り値が TRUE です。全ての領域の縮小方法を返し終わっていたら FALSE を返します。

IZBOOL cs_endValueSelector(const CSvalueSelector *vs, int index, CSint **vars, int size, void *pData)

cs_initValueSelector() で開始された領域の縮小方法の列挙を終了します。 pData には cs_initValueSelector() で渡したポインタを指定します。

成功した場合は TRUE が返されます。

IZBOOL cs_selectValue(CSint *v, const CSvalueSelection *vs): vs で指定された領域の縮小操作を CSint型変数 v に適用します。成功した場合は TRUE が返されます。

NoGood の管理

cs_searchValueSelectorRestartNG() ではフェイルした変数と値の組合せを NoGood として CSnoGoodSet型の変数に保存します。

CSnoGoodSet *cs_createNoGoodSet(CSint **vars, int size, IZBOOL (*prefilter)(CSnoGoodSet *ngs, CSnoGood *ng, CSint **vars, int size, void *ext), int maxNoGood, void (*destructorNotify)(CSnoGoodSet *ngs, void *ext), void *ext)

フェイルが発生した変数と値の組合せを記録するための領域を作成します。

引数の意味はそれぞれ以下の通りです。

vars : 解探索関数に与える CSint型変数の配列です。
size : 解探索関数に与える CSint型変数の配列のサイズです。
prefilter : NoGood を登録するかどうかを判定する関数を指定します。関数が TRUE を返した場合は NoGood が登録されます。prefilter に NULL を指定した場合は常に登録されます。
maxNoGood : 登録できる NoGood の最大数です。最大数に到達した場合、重要でない NoGood から削除されます。
destructorNotify : cs_createNoGoodSet() で作成された領域は cs_restoreContext() などで現在のコンテキストから戻る際に自動的に解放されますが、その時に destructorNotify で指定された関数が呼び出されます。関数呼び出しが不要な場合は NULL を指定します。
ext : prefilter および destructorNotify の引数として使用されます。

prefilter 呼び出し時の引数はそれぞれ以下の通りです。

ngs : この cs_createNoGoodSet() 呼び出しで作成された領域です。
ng : 登録しようとしている NoGood へのポインタです。
vars, size および ext : この cs_createNoGoodSet() 呼び出し時に使用されたものです。

destructorNotify 呼び出し時の引数はそれぞれ以下の通りです。

ngs : この cs_createNoGoodSet() 呼び出しで作成された領域です。
vars, size および ext : この cs_createNoGoodSet() 呼び出し時に使用されたものです。

int cs_getNbNoGoods(CSnoGoodSet *ngs): ngs に登録されている NoGood の数を返します。

int cs_getNbNoGoodElements(CSnoGood *ng): ng に登録されている要素の数を返します。一つの要素は以下から構成され、cs_getNoGoodElementAt() で取得することが可能です。

void cs_getNoGoodElementAt(int *pIndex, CSvalueSelection *vs, CSnoGood *ng, int index)

ng に登録されている index 番目の要素を確認します。

pIndex に cs_createNoGoodSet() の引数 vars 内での位置が格納されます。
vs に領域縮小方法 (何をした時にフェイルしたか) が格納されます。

void cs_filterNoGood(CSnoGoodSet *ngs, IZBOOL (*filter)(CSnoGoodSet *ngs, CSnoGood *elem, CSint **vars, int size, void *ext), void *ext): ngs に登録されている NoGood 全体をスキャンし、filter 関数が FALSE を返した NoGood を削除します。 filter に渡される引数は cs_createNoGoodSet() の prefilter に渡されるものと同じです。

void cs_addNoGood(CSnoGoodSet *ngs, int *index, CSvalueSelection *vs, int size): ngs に NoGood を追加します。index および vs はそれぞれ変数を指定する添え字と変数の領域縮小方法を指定する配列で、要素は size 個です。

void cs_setMaxNbNoGoods(CSnoGoodSet *ngs, int max): ngs に保存できる NoGood の個数を max 個に変更します。

探索状態の通知

CSsearchNotify 型の変数を引数としてとる解探索関数は、コールバック関数の呼び出しを通じて探索中の状態を通知することができます。

CSsearchNotify *cs_createSearchNotify(void *ext)

解探索関数に渡すための CSsearchNotify 型変数を生成します。引数 ext はコールバック関数の呼び出し時に渡されます。

返されたCSsearchNotify 型変数は、不要になったら cs_freeSearchNotify() で解放する必要があります。

void cs_freeSearchNotify(CSsearchNotify *notify): cs_createSearchNotify() で生成された CSsearchNotify 型変数を解放します。

void cs_searchNotifySetSearchStart(CSsearchNotify *notify, void (*searchStart)(int maxFails, CSint **allvars, int nbVars, void *ext))

解探索の開始時に呼び出される関数 searchStart を登録します。

cs_searchValueSelectorRestartNG() では、リスタートの単位ごとに呼び出されます。

searchStart には以下が引数として渡されます。

maxFails : これから行う探索に許されるフェイル数の上限
allvars : 解探索関数に渡された領域変数の配列
nbVars : 解探索関数に渡された領域変数の配列のサイズ
ext : cs_createSearchNotify() に渡されたポインタ

void cs_searchNotifySetSearchEnd(CSsearchNotify *notify, void (*searchEnd)(IZBOOL result, int nbFails, int maxFails, CSint **allvars, int nbVars, void *ext))

解探索の終了時に呼び出される関数 searchEnd を登録します。

cs_searchValueSelectorRestartNG() では、リスタートの単位ごとに呼び出されます。

searchEnd には以下が引数として渡されます。

result : 解が見つかったら TRUE さもなければ FALSE
nbFails : 探索中に起こったフェイルの数
maxFails : 探索に許されていたフェイル数の上限
allvars : 解探索関数に渡された領域変数の配列
nbVars : 解探索関数に渡された領域変数の配列のサイズ
ext : cs_createSearchNotify() に渡されたポインタ

void cs_searchNotifySetBeforeValueSelection(CSsearchNotify *notify, void (*beforeValueSelection)(int depth, int index, const CSvalueSelection *vs, CSint **allvars, int nbVars, void *ext))

領域縮小を行う直前に呼び出される関数 beforeValueSelection を登録します。

beforeValueSelection には以下が引数として渡されます。

depth : 探索の深さ
index : 選択した変数の添え字
vs : 領域縮小方法
allvars : 解探索関数に渡された領域変数の配列
nbVars : 解探索関数に渡された領域変数の配列のサイズ
ext : cs_createSearchNotify() に渡されたポインタ

void cs_searchNotifySetAfterValueSelection(CSsearchNotify *notify, void (*afterValueSelection)(IZBOOL result, int depth, int index, const CSvalueSelection *vs, CSint **allvars, int nbVars, void *ext))

領域縮小を行なった結果を通知するための関数 afterValueSelection を登録します。

afterValueSelection には以下が引数として渡されます。

result : 領域縮小ができたら TRUE、フェイルしたら FALSE
depth : 探索の深さ
index : 選択した変数の添え字
vs : 領域縮小方法
allvars : 解探索関数に渡された領域変数の配列
nbVars : 解探索関数に渡された領域変数の配列のサイズ
ext : cs_createSearchNotify() に渡されたポインタ

void cs_searchNotifySetEnter(CSsearchNotify *notify, void (*enter)(int depth, int index, CSint **allvars, int nbVars, void *ext))

領域縮小を行う変数が決定した時に呼び出される関数 enter を登録します。

enter には以下が引数として渡されます。

depth : 探索の深さ
index : 選択した変数の添え字
allvars : 解探索関数に渡された領域変数の配列
nbVars : 解探索関数に渡された領域変数の配列のサイズ
ext : cs_createSearchNotify() に渡されたポインタ

void cs_searchNotifySetLeave(CSsearchNotify *notify, void (*leave)(int depth, int index, CSint **allvars, int nbVars, void *ext))

一つの変数について、全ての領域縮小を試した後に呼び出される関数 leave を登録します。

leave には以下が引数として渡されます。

depth : 探索の深さ
index : 選択した変数の添え字
allvars : 解探索関数に渡された領域変数の配列
nbVars : 解探索関数に渡された領域変数の配列のサイズ
ext : cs_createSearchNotify() に渡されたポインタ

void cs_searchNotifySetFound(CSsearchNotify *notify, IZBOOL (*found)(int depth, CSint **allvars, int nbVars, void *ext))

全ての変数を即値化できた時に呼び出される関数 found を登録します。

found には以下が引数として渡されます。

depth : 探索の深さ
allvars : 解探索関数に渡された領域変数の配列
nbVars : 解探索関数に渡された領域変数の配列のサイズ
ext : cs_createSearchNotify() に渡されたポインタ

found が TRUE を返すと、解探索関数は TRUE を返して終了します。FALSE を返した場合、探索を続行します。

リスタートを行う解探索関数では、同じ解について found が複数回呼び出される可能性があることに注意してください。