制約学習

制約充足バックトラッキングアルゴリズムにおいて、制約学習は効率を向上させる手法です。これは、矛盾が発見されるたびに新しい制約を記録することで機能します。この新しい制約により、将来の部分評価で矛盾が発見され、それ以上の探索を行わなくても済むため、探索空間が縮小される可能性があります。この手法を命題充足可能性に適用した場合、節学習と呼ばれます。

意味

バックトラッキングアルゴリズムは、未割り当ての変数を選択し、その変数に値を割り当てることで得られる問題を再帰的に解きます。現在の部分解に矛盾が見つかった場合、アルゴリズムは再帰的に期待される通り、以前に割り当てられた変数に戻ります。制約学習アルゴリズムは、バックトラッキングを行う前に、新しい制約の形で何らかの情報を記録しようとする点が異なります。これにより、後続の探索でこの新しい制約と矛盾する別の部分解に遭遇する可能性があるため、探索回数を削減できます。アルゴリズムが新しい制約を学習した場合、元のバックトラッキングアルゴリズムでは後続の探索を行うところを、この解からバックトラッキングを行います。

部分解が矛盾している場合、問題のインスタンスは、すべてのインスタンスに対して同時に真となることはできないという制約を暗示しています。しかし、この制約を記録しても意味がありません。バックトラックの進行により、この部分解は再び遭遇することはないからです。 ${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$ ${\displaystyle x_{i}=a_{i}}$ ${\displaystyle i\in [1,k]}$

一方、この評価のサブセットが矛盾している場合、対応する制約は後続の探索において有用となる可能性があります。これは、同じ部分評価のサブセットが探索で再び出現する可能性があるためです。例えば、アルゴリズムは、以前の部分評価のサブセットを拡張する評価に遭遇する可能性があります。このサブセットが矛盾しており、アルゴリズムがこの事実を制約の形で保存している場合、新しい部分評価を拡張して解を形成できないと結論付けるために、それ以上の探索は必要ありません。 ${\displaystyle x_{2}=a_{2},x_{5}=a_{5},x_{k-1}=a_{k-1}}$

検索は行き詰まりました。	との値のみによって不整合が発生する可能性があります。この事実は新しい制約に格納できます。 ${\displaystyle x_{1}}$ ${\displaystyle x_{4}}$	アルゴリズムが と の同じ値に再度到達すると、新しい制約によって検索がブロックされます。 ${\displaystyle x_{1}}$ ${\displaystyle x_{4}}$

制約学習の効率

制約学習による効率性の向上は、2つの要素の間でバランスが取れています。一方では、記録された制約が頻繁に違反されるほど、バックトラッキングによって無駄な探索を回避できる頻度が高くなります。現在の部分解の小さな矛盾したサブセットは、違反されやすい制約に対応するため、通常は大きなサブセットよりも優れています。他方では、現在の部分評価の小さな矛盾したサブセットを見つけるには時間がかかる場合があり、その利点とその後の探索時間の短縮が釣り合わない可能性があります。

しかし、学習された制約において考慮すべき特徴はサイズだけではありません。実際、探索空間の特定の状態においては、小さな制約は、その制約に違反する値が再び出現しないため、役に立たない場合があります。そのような場合には、違反する値が現在の部分的な割り当てにより近い、より大きな制約が優先される可能性があります。

さまざまな制約学習手法が存在し、記録された制約の厳密さと制約を見つけるコストが異なります。

グラフベース学習

アルゴリズムによって のすべての値が と矛盾することが証明された場合、この評価は矛盾しません。そうでない場合、アルゴリズムはまったく評価を行わないからです。結果として、 の値によって違反される制約には、すべてが含まれます。 ${\displaystyle x_{k+1}}$ ${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$ ${\displaystyle x_{k+1}}$ ${\displaystyle x_{k+1}}$ ${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$ ${\displaystyle x_{k+1}}$

結果として、矛盾した評価は、 の真理値評価を、という制約内にある変数に制限することになります(ただし、この制約には未割り当ての変数は含まれません)。 ${\displaystyle x_{1},\ldots,x_{k}}$ ${\displaystyle x_{k+1}}$

これらの部分評価を表す制約を学習することをグラフベース学習と呼びます。これはグラフベースバックジャンピングと同じ原理に基づいています。これらの手法が「グラフベース」と呼ばれるのは、制約充足問題に関連付けられたグラフから得られる、同じ制約内の変数のペアに基づいているためです。

ジャンプバック学習

ジャンプバック学習は、衝突ベースのバックジャンプによって発見される矛盾した割り当てを制約として保存することに基づいています。部分的な割り当てに矛盾が見つかった場合、このアルゴリズムは、変数のインスタンス化順序に基づく順序付けに従って、最小となる違反制約を選択します。この制約に含まれる変数に限定された評価は矛盾しており、通常は完全な評価よりも短くなります。ジャンプバック学習はこの事実を新しい制約として保存します。

制約の順序は、変数の代入順序に基づきます。特に、2つの制約のうち最も小さい制約とは、最後にインスタンス化された非共通変数を持つ制約です。矛盾する代入が発生した場合、ジャンプバック学習はこの順序に従って最小となる違反制約を選択し、現在の代入をその変数に制限します。この代入の矛盾を表す制約は保存されます。

制約の維持

制約学習アルゴリズムは、与えられた矛盾する部分評価に対応する制約の選択だけでなく、どの制約を保持し、どの制約を破棄するかの選択においても異なります。

一般的に、すべての矛盾を制約の形で学習し、それを無期限に保持すると、利用可能なメモリが枯渇し、部分評価の整合性チェックのコストが増加する可能性があります。これらの問題は、学習した制約の一部のみを保存するか、制約を定期的に破棄することで解決できます。

境界学習では、制約が表す矛盾した部分評価が指定された制約数より小さい場合にのみ、制約を保存します。関連性境界学習では、探索空間の現在の時点において関連性がないと判断された制約は破棄されます（または全く保存されません）。特に、現在の部分評価と異なる変数の数が指定された固定数以下である矛盾した部分評価を表す制約はすべて破棄されるか、保存されません。

参照

• 先読み（バックトラッキング）
• バックジャンプ

参考文献

• デヒター、リナ(2003).制約処理. モーガン・カウフマン.ISBN 1-55860-890-7