制約学習

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

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

部分的な解決法が矛盾している場合、問題インスタンスは、同時にすべてに当てはまることはできないという制約を意味します。ただし、バックトラックの進行方法により、この部分的な解決法は再び発生することはないため、この制約を記録しても役に立ちません。 ${\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}}$

制約学習の効率性の向上は、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 つの制約のうち最も小さい制約は、最新の非共通変数が最初にインスタンス化された制約です。矛盾した割り当てに達すると、ジャンプバック学習はこの順序に従って最小となる違反制約を選択し、現在の割り当てをその変数に制限します。この割り当ての矛盾を表す制約が保存されます。

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

一般に、すべての矛盾を制約の形で学習し、それを無期限に保持すると、使用可能なメモリが使い果たされ、部分評価の一貫性をチェックするコストが増加する可能性があります。これらの問題は、学習した制約の一部だけを保存するか、時々制約を破棄することで解決できます。

制限付き学習では、制約が表す矛盾した部分評価が指定された制約数より小さい場合にのみ制約が保存されます。関連性制限付き学習では、検索空間の現在のポイントで関連性がないと判断された制約は破棄されます (またはまったく保存されません)。特に、指定された固定数の変数以下の現在の部分評価と異なる矛盾した部分評価を表すすべての制約は破棄されるか、保存されません。

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

• Dechter, Rina (2003)。制約処理。Morgan Kaufmann。  1-55860-890-7出版年月日