ローカル一貫性

制約充足において、局所一貫性条件は、変数または制約のサブセットの一貫性に関連する制約充足問題の特性です。これらを使用すると、検索空間を縮小し、問題を解決しやすくなります。ノード一貫性、アーク一貫性、パス一貫性など、さまざまな種類の局所一貫性条件が活用されます。

すべてのローカル整合性条件は、問題の解を変えずに問題自体を変える変換によって強制することができます。このような変換は制約伝播と呼ばれます。制約伝播は、変数のドメインを縮小したり、制約を強化したり、新しい制約を作成したりすることで機能します。これにより、探索空間が縮小され、一部のアルゴリズムで問題を簡単に解決できるようになります。制約伝播は、一般には不完全ですが、特定のケースでは完全な、不満足性チェッ​​カーとしても使用できます。

ローカル一貫性条件は、さまざまなクラスにグループ化できます。元のローカル一貫性条件では、一貫性のあるすべての部分割り当て (特定の種類) を別の変数に一貫して拡張できることが要求されます。方向一貫性では、指定された順序に従って、他の変数が割り当て内の変数よりも大きい場合にのみ、この条件を満たす必要があります。関係一貫性には、複数の変数への拡張が含まれますが、この拡張は、指定された制約または制約セットを満たすためにのみ必要です。

この記事では、制約充足問題は、変数のセット、ドメインのセット、および制約のセットとして定義されます。変数とドメインは関連付けられており、変数のドメインには、変数が取ることができるすべての値が含まれます。制約は、スコープと呼ばれる一連の変数と、制約を満たす評価のセットから構成されます。

この記事で言及されている制約充足問題は、特殊な形式であると仮定されています。変数のすべてのシーケンスが最大で 1 つの制約または正確に 1 つの制約のスコープである場合、問題は正規化形式または正規形式にあります。バイナリ制約に対してのみ行われる正規性の仮定は、標準化された形式につながります。これらの条件は、変数のシーケンス上のすべての制約を 1 つに結合するか、変数のシーケンスのすべての値によって満たされる制約を追加することによって常に強制できます。

この記事で使用されている図では、2 つの変数間のリンクが欠如しているため、これら 2 つの変数間に制約が存在しない、またはすべての値によって満たされる制約が存在することを示しています。^{[説明が必要]}

「標準的な」ローカル一貫性条件はすべて、すべての一貫性のある部分評価を別の変数に拡張して、結果として生じる割り当てが一貫性を持つようにする必要があります。部分評価は、割り当てられた変数のサブセットを範囲とするすべての制約を満たす場合に一貫性があります。^{[説明が必要]}

ノードの一貫性を保つには、変数のすべての単項制約が変数のドメイン内のすべての値によって満たされることが必要であり、その逆も同様です。この条件は、各変数のドメインを、その変数のすべての単項制約を満たす値に縮小することで簡単に適用できます。その結果、単項制約は無視され、ドメインに組み込まれていると想定できます。

たとえば、のドメインとの制約を持つ変数が与えられた場合、ノード一貫性によりドメインが に制限され、制約は破棄されます。この前処理手順により、後の段階が簡素化されます。 ${\displaystyle V}$${\displaystyle \left\{1,2,3,4\right\}}$${\displaystyle V\leq 3}$${\displaystyle \left\{1,2,3\right\}}$

制約充足問題の変数は、その変数の許容値のそれぞれが 2 番目の変数の許容値と一致する場合、別の変数と弧整合しています。正式には、のドメイン内の すべての値に対して、との間の 2 項制約を満たすようなのドメイン内の値が存在する場合、変数は別の変数と弧整合しています。すべての変数が他のすべての変数と弧整合している場合、問題は弧整合しています。 ${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle a}$${\displaystyle x_{i}}$${\displaystyle b}$${\displaystyle x_{j}}$${\displaystyle (a,b)}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$

たとえば、変数の範囲がドメイン 1 から 3 にわたる制約を考えてみましょう。は 3 になることは決してないため、3 から 内の値への弧は存在せず、したがって削除しても問題ありません。同様に、は 1 になることは決してないため、弧は存在せず、したがって削除できます。 ${\displaystyle x<y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle y}$

アーク一貫性は、特定のバイナリ制約を基準にして定義することもできます。バイナリ制約は、1 つの変数のすべての値が 2 番目の変数の値を持ち、制約を満たす場合、アーク一貫性があります。このアーク一貫性の定義は上記と似ていますが、制約に固有のものです。この違いは、特に正規化されていない問題に関係します。上記の定義では 2 つの変数間のすべての制約が考慮されるのに対し、この定義では特定の制約のみが考慮されます。

変数が別の変数とアーク整合しない場合は、そのドメインからいくつかの値を削除することで整合させることができます。これは、アーク整合を強制する制約伝播の形式です。つまり、変数のドメインから、他の変数の値に対応しないすべての値を削除します。削除された値はいずれにしても解にはならないため、この変換により問題の解が維持されます。

制約伝播は、すべての変数ペアに対してこの削除を繰り返すことで、問題全体をアーク整合させることができます。このプロセスでは、特定の変数ペアを複数回考慮する必要がある場合があります。実際、変数のドメインから値を削除すると、他の変数がその変数とアーク整合しなくなる可能性があります。たとえば、がとアーク整合しているが、アルゴリズムが のドメインを縮小した場合、とのアーク整合は保持されなくなり、再度強制する必要があります。 ${\displaystyle x_{3}}$${\displaystyle x_{2}}$${\displaystyle x_{2}}$${\displaystyle x_{3}}$${\displaystyle x_{2}}$

最も単純なアルゴリズムは、変数のペアを循環してアークの一貫性を強制し、サイクル全体でドメインが変更されなくなるまでサイクルを繰り返します。AC -3 アルゴリズムは、最後に分析されてから変更されていない制約を無視することで、このアルゴリズムを改良しています。特に、最初はすべての制約を含む制約セットで動作し、各ステップで制約を取得してアークの一貫性を強制します。この操作によって別の制約でアークの一貫性違反が発生する可能性がある場合は、その制約を分析する制約セットに戻します。このように、制約にアークの一貫性が強制されると、その変数の 1 つのドメインが変更されない限り、この制約は再び考慮されません。

パス一貫性はアーク一貫性に似た特性ですが、変数を 1 つだけではなくペアで考慮します。変数のペアは、ペアの各矛盾のない評価が他の変数に拡張されてすべてのバイナリ制約が満たされる場合、3 番目の変数とパス一貫性があります。正式には、と がとパス一貫性を持つのは、との間のバイナリ制約を満たすすべての値のペアに対して、との間の制約、およびとの間の制約を満たすような値が のドメインに存在する場合です。 ${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle x_{k}}$${\displaystyle (a,b)}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle c}$${\displaystyle x_{k}}$${\displaystyle (a,c)}$${\displaystyle (b,c)}$${\displaystyle x_{i}}$${\displaystyle x_{k}}$${\displaystyle x_{j}}$${\displaystyle x_{k}}$

パスの一貫性を強制する制約伝播の形式は、制約からいくつかの満足する割り当てを削除することによって機能します。実際、パスの一貫性は、バイナリ制約から別の変数に拡張できないすべての評価を削除することによって強制できます。アークの一貫性に関しては、この削除ではバイナリ制約を複数回考慮する必要がある場合があります。アークの一貫性に関しては、削除された値は解に含まれないため、結果として生じる問題は元の問題と同じ解を持ちます。

パスの一貫性を強制する制約伝播の形式により、新しい制約が導入される可能性があります。2 つの変数がバイナリ制約によって関連付けられていない場合、任意の値のペアを許可する制約によって仮想的に関連付けられます。ただし、一部の値のペアは制約伝播によって削除される可能性があります。結果として生じる制約は、すべての値のペアによって満たされなくなります。したがって、仮想の単純な制約ではなくなります。

「パス一貫性」という名前は、変数のペアとそれらの間のパスを含む元の定義に由来しており、変数のペアと単一の変数を含む定義ではありません。 2 つの定義は単一の変数のペアに対しては異なりますが、問題全体を指す場合は同等です。

アークとパスの一貫性は、変数の組を1 つまたは 1 組の代わりに使用することで、非バイナリ制約に一般化できます。変数の組は、一貫性を保ちながら、変数のすべての一貫した評価を他の変数の値で拡張できる場合、別の変数と -一貫性があります。この定義は、明らかな方法で問題全体に拡張されます。強い-一貫性は、すべての に対する -一貫性です 。 ${\displaystyle i-1}$${\displaystyle i}$${\displaystyle i-1}$${\displaystyle i}$${\displaystyle j}$${\displaystyle j\leq i}$

2 一貫性の特定のケースは、アーク一貫性と一致します (この記事では、すべての問題はノード一貫性があると想定されています)。一方、3 一貫性は、すべての制約がバイナリである場合にのみパス一貫性と一致します。これは、パス一貫性には 3 値制約が含まれないのに対し、3 一貫性には含まれるためです。

アーク一貫性を一般化する別の方法は、ハイパーアーク一貫性または一般化アーク一貫性であり、制約を満たすために単一の変数の拡張可能性を必要とします。つまり、変数のすべての値が制約を満たすような方法で制約の他の変数に拡張できる場合、変数は制約とハイパーアーク一貫性があります。

制約の伝播 (ローカル整合性の形式を強制) により、空ドメインまたは不満足な制約が生成される場合があります。この場合、問題には解決策がありません。逆は一般には当てはまりません。つまり、不一致なインスタンスは、空ドメインまたは不満足な制約がないにもかかわらず、アーク整合性またはパス整合性がある場合があります。

実際、ローカル一貫性は、変数のグループの一貫性にのみ関連しています。たとえば、アーク一貫性は、変数のすべての一貫した評価が別の変数に一貫して拡張できることを保証します。ただし、変数の単一の値が他の 2 つの変数に拡張される場合、これらの 2 つの値が互いに一貫しているという保証はありません。たとえば、はおよび と一致する可能性がありますが、これら 2 つの評価は互いに一致しない可能性があります。 ${\displaystyle x_{1}=1}$${\displaystyle x_{2}=1}$${\displaystyle x_{3}=1}$

ただし、制約の伝播は、場合によっては充足可能性を証明するために使用できます。円弧が一貫しており、空のドメインがないバイナリ制約のセットは、制約のネットワークにサイクルが含まれている場合にのみ矛盾する可能性があります。実際、制約がバイナリで非巡回グラフを形成する場合、値は常に制約間で伝播できます。つまり、変数のすべての値について、それを含む制約内のすべての変数はその制約を満たす値を持ちます。結果として、割り当てられていない変数を繰り返し選択し、制約間で再帰的に伝播することで、ソリューションを見つけることができます。このアルゴリズムは、制約のネットワークにサイクルが存在することを意味するため、すでに割り当てられている変数に値を割り当てようとしません。

同様の条件がパスの一貫性にも当てはまります。アークの一貫性とパスの一貫性を強制することで満足可能性を確立できる特殊なケースは次のとおりです。

1. アークの一貫性を強制すると、サイクルのないバイナリ制約(バイナリ制約のツリー)で作成された問題の満足度が確立されます。
2. パスの一貫性を強制すると、バイナリドメインを持つバイナリ制約（サイクルを含む可能性あり）の充足可能性が確立されます。
3. 強い一貫性を強制することで、変数を含む問題の満足度が確立されます。${\displaystyle n}$${\displaystyle n}$

相対的一貫性に関する一部の定義または結果は、特殊な場合にのみ当てはまります。

ドメインが整数で構成されている場合、境界一貫性を定義できます。この形式の一貫性は、ドメインの極値、つまり変数が取り得る最小値と最大値の一貫性に基づいています。

制約が代数的またはブール型の場合、アーク一貫性は新しい制約を追加するか、古い制約を構文的に変更することと同等であり、これは制約を適切に構成することによって実行できます。

いくつかの種類の制約はよく使用されます。たとえば、一部の変数がすべて異なるという制約はよく使用されます。このような制約に対してアークの一貫性を強制するための効率的な特殊なアルゴリズムが存在します。

複数の変数が異なることを強制する制約は、通常、またはと記述されます。この制約は、異なる変数のすべてのペアが等しくないこと、つまり、すべての に対して であることに相当します。変数のドメインが単一の値に縮小されると、アーク一貫性を強制するときに制約の伝播によって、この値を他のすべてのドメインから削除できます。特殊な制約を使用すると、個々のバイナリ不等式には当てはまらない特性を活用できます。 ${\displaystyle \mathop {\rm {alldifferent}} (x_{1},\ldots ,x_{n})}$alldifferent([X1,...,Xn])${\displaystyle x_{i}\not =x_{j}}$${\displaystyle i\not =j}$

最初の特性は、すべての変数のドメイン内の要素の総数が、少なくとも変数の数以上でなければならないということです。より正確には、アークの一貫性が強制された後、割り当てられていない変数の数は、それらのドメインの和集合内の値の数を超えてはなりません。そうでない場合、制約を満たすことはできません。この条件は、形式の制約で簡単に確認できますalldifferentが、不等式ネットワークのアークの一貫性には対応していません。単一の制約の 2 番目の特性は、alldifferentハイパーアークの一貫性が、二部マッチングアルゴリズムを使用して効率的に確認できることです。特に、2 つのノード セットとして変数と値を使用してグラフが構築され、特殊な二部グラフマッチング アルゴリズムがそれに対して実行され、そのようなマッチングの存在が確認されます。^[1]

よく使用される別の種類の制約は ですcumulative。これは、スケジュールと配置の問題のために導入されました。たとえば、 は、開始時刻、期間、および使用するリソースの量を持つアクティビティcumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L)が存在する条件を形式化するために使用できます。制約は、使用可能なリソースの合計量が であることを示します。累積制約専用の制約伝播手法が存在し、どの変数ドメインがすでに単一の値に縮小されているかに応じて、異なる手法が使用されます。 msidiriL

制約論理プログラミングで使用される 3 つ目の特殊な制約は ですelement。制約論理プログラミングでは、リストは変数の値として許可されます。 がリストであり、 がこのリストの 番目の要素であるelement(I, L, X)場合、制約は満たされます。これらの制約には、特殊な制約伝播ルールが存在します。たとえば、と が単一値ドメインに縮小される場合、 の一意の値を決定できます。より一般的には、 の不可能な値はのドメインから推論でき、その逆も同様です。 LXILIXX${\displaystyle I}$

方向性一貫性は、アーク、パス、および一貫性のバリエーションであり、指定された変数の順序に従って変数に値を割り当てるアルゴリズムによって使用されるように調整されています。方向性のない一貫性と似ていますが、いくつかの変数への一貫した割り当てが、順序に従ってそれらよりも大きい別の変数に一貫して拡張できることのみを必要とします。 ${\displaystyle i}$

アルゴリズムが の順序で変数を評価する場合、一貫性は、より低いインデックスの変数の値がすべてより高いインデックスの変数の値と一貫していることを保証する場合にのみ役立ちます。 ${\displaystyle x_{1},\ldots ,x_{n}}$

変数の値を選択する際、割り当てられていない変数のすべての値と矛盾する値は無視できます。実際、これらの値がすべて現在の部分評価と矛盾しない場合でも、アルゴリズムは後で割り当てられていない変数の矛盾しない値を見つけることができません。一方、すでに評価されている変数との一貫性を強制する必要はありません。アルゴリズムが現在の部分評価と矛盾する値を選択した場合、いずれにしても矛盾が検出されます。

変数の評価順序が であると仮定すると、制約充足問題は、すべての変数が となる他の任意の変数と弧整合している場合、方向性弧整合であると言えます。方向性パス整合性も同様ですが、2 つの変数はの場合にのみ、とパス整合している必要があります。強い方向性パス整合性とは、方向性パス整合性と方向性弧整合性の両方を意味します。他の形式の整合性についても同様の定義が可能です。 ${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle i<j}$${\displaystyle x_{i},x_{j}}$${\displaystyle x_{z}}$${\displaystyle i,j<z}$

方向性アーク一貫性を強制する制約伝播は、最後の変数から最初の変数まで反復処理し、各ステップでそれより低いインデックスのすべての変数のアーク一貫性を強制します。変数の順序が の場合、このアルゴリズムは から までの変数を反復処理します。変数 については、 より低いインデックスのすべての変数のアーク一貫性を で強制します。 ${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle x_{n}}$${\displaystyle x_{1}}$${\displaystyle x_{j}}$${\displaystyle j}$${\displaystyle x_{j}}$

方向性パス一貫性および強い方向性パス一貫性は、アーク一貫性と同様のアルゴリズムによって強制できます。これらは、から までの変数を処理します。すべての変数について、を持つ2 つの変数が考慮され、 を持つそれらのパス一貫性が強制されます。問題におよびの制約が含まれていない場合、またはと の間に制約が含まれていない場合、操作は必要ありません。ただし、と の間に制約がない場合でも、自明な制約が想定されます。制約の伝播によって、満足する割り当てのセットが削減される場合、実質的に新しい非自明な制約が作成されます。強い方向性パス一貫性を強制する制約の伝播は似ていますが、アーク一貫性も強制します。 ${\displaystyle x_{n}}$${\displaystyle x_{1}}$${\displaystyle x_{z}}$${\displaystyle x_{i},x_{j}}$${\displaystyle i,j<z}$${\displaystyle x_{z}}$${\displaystyle x_{i}}$${\displaystyle x_{z}}$${\displaystyle x_{j}}$${\displaystyle x_{z}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$

方向の一貫性は、制約を満たす部分的なソリューションが、より高いインデックスの別の変数に一貫して拡張できることを保証します。ただし、異なる変数への拡張が互いに一貫していることは保証されません。たとえば、部分的なソリューションは、変数または変数 に一貫して拡張できますが、これら 2 つの拡張は互いに一貫していません。 ${\displaystyle x_{i}}$${\displaystyle x_{j}}$

これが起きないケースが 2 つあり、どのドメインも空でなく、どの制約も満たされない場合、方向性の一貫性によって満足可能性が保証されます。

最初のケースは、変数の順序付けによって制約の順序付きグラフの幅が 1 になるバイナリ制約問題です。このような順序付けは、制約のグラフがツリーである場合にのみ存在します。この場合、グラフの幅は、ノードが結合される下位ノード (順序付けによる) の最大数を制限します。方向性アークの一貫性により、変数への一貫した割り当てはすべて上位ノードに拡張できることが保証され、幅 1 により、ノードが複数の下位ノードに結合されないことが保証されます。その結果、下位変数が割り当てられると、その値は、結合される上位変数すべてに一貫して拡張できます。この拡張によって後で不整合が発生することはありません。実際、グラフの幅は 1 であるため、他の下位変数はその上位変数に結合されません。

その結果、制約問題が変数の順序に関して幅 1 を持ち (対応するグラフがツリーであることを意味する)、問題が同じ順序に関して方向的にアーク一貫性がある場合、順序に従って変数を反復的に割り当てることによって、解決策 (存在する場合) を見つけることができます。

ドメインが空でなく、制約が満たされない場合に方向性の一貫性が満足可能性を保証する 2 番目のケースは、強い方向性パス一貫性を使用してグラフが幅2 を誘導したバイナリ制約問題の場合です。実際、この形式の一貫性は、変数または変数のペアへのすべての割り当てがより高い変数に拡張できることを保証し、幅 2 は、この変数が別のより低い変数のペアに結合されないことを保証します。

幅ではなく誘導幅が考慮される理由は、方向性パスの一貫性を強制すると制約が追加される可能性があるためです。実際、2 つの変数が同じ制約内になく、より高い変数との制約内にある場合、それらの値のペアの一部がパスの一貫性に違反する可能性があります。このようなペアを削除すると、新しい制約が作成されます。その結果、制約の伝播により、グラフに元のグラフよりも多くのエッジがある問題が発生する可能性があります。ただし、これらすべてのエッジは同じノードの 2 つの親の間にあるため、必然的に誘導グラフ内にあります。幅 2 は、すべての一貫性のある部分評価をソリューションに拡張できることを保証しますが、この幅は生成されたグラフに相対的です。結果として、強い方向性パスの一貫性でソリューションの存在を保証するには、誘導幅が 2 である必要があります。

方向性-一貫性は、変数へのすべての一貫した割り当てが、順序がより高い別の変数に一貫して拡張できることを保証します。強い方向性-一貫性は同様の方法で定義されますが、最大で変数のすべてのグループが考慮されます。問題が強く方向性-一貫性があり、幅が 未満で、空の定義域や満たされない制約がない場合は、解が存在します。 ${\displaystyle i}$${\displaystyle i-1}$${\displaystyle i}$ ${\displaystyle i-1}$${\displaystyle i}$${\displaystyle i}$

すべての問題を強く方向性一貫性のあるものにすることができますが、この操作により、対応するグラフの幅が広くなる可能性があります。方向性一貫性を強制する制約伝播手順は、方向性アーク一貫性およびパス一貫性に使用される手順に似ています。変数は、順序に従って最後から最初まで順に検討されます。変数 について、アルゴリズムは、インデックスが より小さく、制約 にあるすべての変数グループを検討します。これらの変数の との一貫性はチェックされ、これらすべての変数間で制約から満足する割り当てを削除することによって強制される可能性があります(存在する場合、またはそうでない場合は新しい割り当てを作成します)。 ${\displaystyle i}$${\displaystyle x_{k}}$${\displaystyle i-1}$${\displaystyle k}$${\displaystyle x_{k}}$${\displaystyle x_{k}}$${\displaystyle i}$

この手順により、強く方向性のある一貫性のあるインスタンスが生成されます。ただし、インスタンスに新しい制約が追加される場合もあります。その結果、元の問題の幅が であっても、結果のインスタンスの幅は大きくなる可能性があります。この場合、どのドメインも空でなく、どの制約も満たされない場合でも、方向性のある強い一貫性は満足可能性を意味しません。 ${\displaystyle i}$${\displaystyle i}$

ただし、制約の伝播では、現在考慮している変数よりも低い変数にのみ制約が追加されます。その結果、アルゴリズムが一度この変数を処理すると、その変数に対する制約は変更または追加されません。固定の を考慮する代わりに、考慮する各変数の親の数にそれを変更できます (変数の親とは、変数よりもインデックスが低く、変数と制約内にある変数です)。これは、各ステップで特定の変数のすべての親を考慮することに相当します。言い換えると、最後の変数から最初の変数までの各変数について、そのすべての親が、 と一致する値にその値を制限するための新しい制約に含められます。このアルゴリズムは、 の値が各ノードの親の数に変更された以前のアルゴリズムの修正と見なすことができるため、適応一貫性 と呼ばれます。 ${\displaystyle i}$${\displaystyle x_{i}}$${\displaystyle x_{i}}$${\displaystyle i}$

このアルゴリズムは、問題の誘導幅に等しい強い方向性一貫性を強制します。結果として得られるインスタンスは、ドメインまたは制約が空にされていない場合にのみ満足可能です。この場合、割り当てられていない変数を任意の値に繰り返し設定し、この部分的な評価を他の変数に伝播することで、簡単にソリューションを見つけることができます。このアルゴリズムは、強い方向性一貫性を強制することで導入される制約の数によってサイズが指数関数的に増加する可能性があるため、常に多項式時間であるとは限りません。ただし、強い方向性一貫性を強制することでインスタンスが超多項式的に拡大されない場合は、問題は多項式時間で解決できます。結果として、インスタンスが定数で制限された誘導幅を持つ場合は、多項式時間で解決できます。 ${\displaystyle i}$${\displaystyle i}$

バケット除去は、充足可能性アルゴリズムです。適応一貫性の再定式化として定義できます。その定義では、制約のコンテナであるバケットを使用し、各変数には関連するバケットがあります。制約は常に、最も高い変数のバケットに属します。

バケット削除アルゴリズムは、最高値から最低値まで順に処理を進めます。各ステップで、この変数のバケット内の制約が考慮されます。定義により、これらの制約は より低い変数のみに関係します。アルゴリズムは、これらの低い変数間の制約を変更します (存在する場合、そうでない場合は新しい制約を作成します)。特に、のバケット内の制約と矛盾しないように、それらの値を に拡張できるようにします。この新しい制約 (存在する場合) は、適切なバケットに配置されます。この制約は より低い変数のみに関係するため、 より低い変数のバケットに追加されます。 ${\displaystyle x_{i}}$${\displaystyle x_{i}}$${\displaystyle x_{i}}$${\displaystyle x_{i}}$${\displaystyle x_{i}}$${\displaystyle x_{i}}$

このアルゴリズムは、適応的な一貫性を強制することと同等です。どちらも変数とそのすべての親との一貫性を強制し、変数が考慮された後に新しい制約が追加されないため、バックトラックなしで解決できるインスタンスが結果として得られます。

これらによって生成されるインスタンスのグラフは誘導グラフのサブグラフであるため、誘導幅が定数で制限されている場合、生成されるインスタンスのサイズは元のインスタンスのサイズの多項式になります。結果として、インスタンスの誘導幅が定数で制限されている場合、2 つのアルゴリズムによって多項式時間で解決できます。

一貫性のこれまでの定義はすべて割り当ての一貫性に関するものですが、関係的一貫性は、特定の制約または制約セットの満足のみを伴います。より正確には、関係的一貫性は、すべての一貫性のある部分的割り当てが、特定の制約または制約セットが満たされるように拡張できることを意味します。形式的には、変数の制約は、その変数のいずれかへのすべての一貫性のある割り当てがそのような方法で拡張できる場合、その変数の 1 つと関係的アーク一貫性があります。「通常の」一貫性と関係的アーク一貫性の違いは、後者は拡張された割り当てが特定の制約を満たすことのみを必要とするのに対し、前者は関連するすべての制約を満たすことを必要とすることです。 ${\displaystyle C}$${\displaystyle X}$${\displaystyle x}$${\displaystyle X\backslash \{x\}}$${\displaystyle x}$${\displaystyle C}$${\displaystyle i}$

この定義は、複数の制約と複数の変数に拡張できます。特に、リレーショナル パスの一貫性はリレーショナル アークの一貫性に似ていますが、1 つの制約の代わりに 2 つの制約が使用されます。2 つの制約は、考慮されている 1 つの変数を除くすべての変数への一貫した割り当てが、2 つの制約が満たされるように拡張できる場合、変数とリレーショナル パスが一貫しています。

制約が 2 つ以上ある場合、関係-一貫性が定義されます。関係-一貫性には、制約のセットと、これらすべての制約のスコープ内にある変数が関係します。特に、これらの制約は、そのスコープ内にある他のすべての変数へのすべての一貫した割り当てが、これらの制約を満たすような方法で変数に拡張できる場合、変数と関係 -一貫性があります。すべての制約セットが、そのすべてのスコープ内にあるすべての変数と関係 -一貫性がある場合、問題は -関係 -一貫性があります。強い関係 -一貫性は上記のように定義されます。つまり、すべての に対して関係 -一貫性があるという特性です。 ${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle k}$${\displaystyle k<m}$

関係一貫性は、1 つの変数だけでなく、複数の変数に対して定義することもできます。制約のセットは、変数のサブセットへのすべての一貫した割り当てが、すべての制約を満たすすべての変数の評価に拡張できる場合、関係一貫性があります。この定義は、評価が拡張可能であると想定される変数が、関連する制約のすべてのスコープ内にあるとは限らないため、上記を正確に拡張するものではありません。 ${\displaystyle m}$${\displaystyle (i,m)}$${\displaystyle i}$

変数の順序が指定されている場合、関係の一貫性は、評価される変数が順序内の他の変数に従うように拡張可能である必要がある場合に限定されます。この修正された条件は、方向性のある関係の一貫性と呼ばれます。

制約充足問題は、関係的に一貫していて、空ドメインや充足不可能な制約を持たず、それでも充足不可能である場合があります。ただし、これが不可能な場合もあります。

最初のケースは、ドメインに最大 個の要素が含まれる場合の、強いリレーショナル -一貫性の問題です。この場合、変数の一貫性のある評価は、常に 1 つの他の変数に拡張できます。 がそのような評価で が変数である場合、変数が取り得る値は 個のみです。そのような値がすべて評価と矛盾する場合、評価とその可能な値の 1 つによって違反される制約 (必ずしも一意ではない) が存在します。その結果、評価を拡張してこれらすべての- 以下の制約を満たすことはできず、強いリレーショナル -一貫性の条件に違反します。 ${\displaystyle m}$${\displaystyle m}$${\displaystyle k}$${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$${\displaystyle x_{k+1}}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$

2 番目のケースは、ドメインではなく制約の尺度に関連しています。制約は、1 つの変数を除くすべての変数に対する評価が、他の変数のすべての可能な値またはその最大限その値によって制約を満たすように拡張できる場合、- タイトです。- タイト制約を持つ問題は、それらが強く関係的に- 一貫性 がある場合にのみ満足可能です。${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m+1}$

3 番目のケースは、行凸行列で表すことができるバイナリ制約の場合です。バイナリ制約は、2 次元行列 で表すことができます。ここで、 は、の定義域の - 番目の値と の定義域の - 番目の値が制約を満たすかどうかによって 0 または 1 になります。この行列の行は、そこに含まれる 1 が連続している場合に凸です (正式には、2 つの要素が 1 の場合、その間にあるすべての要素も 1 です)。行列のすべての行が凸である場合、その行列は行凸です。 ${\displaystyle M}$${\displaystyle M_{ij}}$${\displaystyle i}$${\displaystyle x_{i}}$${\displaystyle j}$${\displaystyle x_{j}}$

強い関係パス一貫性を充足可能性と同等にする条件は、すべての制約が行凸行列によって表されるような変数の順序が存在する制約充足問題の条件です。この結果は、共通要素をペアで持つ凸行の集合は、グローバルに共通する要素も持つという事実に基づいています。変数の評価を考えると、- 番目の変数の許容値は、いくつかの制約からいくつかの行を選択することによって与えられます。特に、1 つの変数の中のすべての変数について、その変数と 1 つを関連付ける制約を表す行列内のその値に関連する行は、後者の許容値を表します。これらの行は凸であり、パス一貫性のためにペアで共通要素を持つため、共有される共通要素も持ちます。これは、他の変数と一致する最後の変数の値を表します。 ${\displaystyle k}$${\displaystyle k+1}$${\displaystyle k}$${\displaystyle k+1}$

あらゆる形式の局所的一貫性は制約伝播によって強制することができ、制約を満たす変数のドメインと割り当てのセットが削減され、新しい制約が導入されることがあります。制約伝播によって空ドメインまたは満足できない制約が生成される場合は常に、元の問題は満足できません。したがって、あらゆる形式の局所的一貫性は、満足可能性の近似として使用できます。より正確には、それらは不完全な満足不可能アルゴリズムとして使用できます。問題が満足不可能であることを証明できますが、一般に問題が満足可能であることを証明できないためです。このような近似アルゴリズムは、部分的なソリューションを拡張してすべての制約を満たすことができるかどうかを、さらに分析することなく判断するためのヒューリスティックとして、検索アルゴリズム (バックトラッキング、バックジャンピング、ローカル検索など) で使用できます。

制約伝播によって空ドメインや満たされない制約が生成されない場合でも、ドメインが縮小されたり、制約が強化されたりすることがあります。この場合、問題の検索空間が縮小され、問題を解決するために必要な検索の量も削減されます。

局所的一貫性は、いくつかの制限されたケースで充足可能性を証明します (制約充足の複雑さ#制限を参照)。これは、いくつかの特殊な種類の問題や、ある種の局所的一貫性の場合に当てはまります。たとえば、2 項非巡回問題に弧の一貫性を強制すると、問題が充足可能かどうかを判断できます。強い方向性の一貫性を強制すると、同じ順序に従って幅を誘導した問題の充足可能性を判断できます。適応的方向性の一貫性により、任意の問題の充足可能性を判断できます。 ${\displaystyle i}$${\displaystyle i-1}$

• ユニット伝播
• 制約プログラミング
• 制約論理プログラミング
• 先読み（バックトラッキング）

• 制約伝播 - 理論と実装の問題を詳しく概説した Guido Tack の論文

• ルクルトル、クリストフ (2009)。制約ネットワーク: 技術とアルゴリズム。 ISTE/ワイリー。  978-1-84821-106-3出版年月日
• Dechter, Rina (2003)。制約処理。Morgan Kaufmann。  1-55860-890-7出版年月日
• Apt, Krzysztof (2003).制約プログラミングの原理. Cambridge University Press.  0-521-82583-0出版年月日
• Marriott, Kim; Peter J. Stuckey (1998)。制約付きプログラミング: 入門。MIT プレス。  0-262-13341-5出版年月日