制約充足問題

制約充足問題( CSP ) は、状態がいくつかの制約または制限を満たす必要があるオブジェクトのセットとして定義される数学的な問題です。 CSP は、問題内のエンティティを変数に対する有限制約の均質なコレクションとして表し、制約充足法によって解決されます。 CSP は、その定式化の規則性により、一見無関係な多くのファミリーの問題を分析および解決するための共通の基礎が提供されるため、人工知能とオペレーションズ リサーチの両方で研究対象となっています。 CSP は多くの場合、非常に複雑であり、妥当な時間で解決するには、ヒューリスティックと組み合わせ検索方法の組み合わせが必要です。制約プログラミング(CP) は、このような種類の問題への取り組みに特に焦点を当てた研究分野です。^{[1] [2]}さらに、ブール充足可能性問題(SAT)、理論を法とする充足可能性(SMT)、混合整数計画法(MIP)、および解答セット プログラミング(ASP) はすべて、制約充足問題の特定の形式の解決に焦点を当てた研究分野です。

制約充足問題としてモデル化できる問題の例は次のとおりです。

• 型推論^{[3] [4]}
• 8つのクイーンのパズル
• 地図の色分け問題
• 最大カット問題^[5]
• 数独、クロスワード、太字、カックロ（クロスサム）、Numbrix / Hidato、その他多くの論理パズル

これらは、 CP 、ASP、ブールSAT、SMTソルバーのチュートリアルで提供されることが多い。一般的に、制約問題ははるかに難しく、これらの単純なシステムでは表現できない場合があります。「現実の」例としては、自動計画、^{[6] [7]} 語彙の曖昧さ解消、^{[8] [9]} 音楽学、^[10] 製品構成^[11]およびリソース割り当てなどがあります。^[12]

CSP の解の存在は、決定問題として考えることができます。これは、解が見つかるか、徹底的な探索後に解が見つからないかによって決定されます (十分に小さな問題では、確率的アルゴリズムは通常徹底的な結論に達することはありませんが、有向探索はしばしば徹底的な結論に達します)。場合によっては、他の数学的推論プロセスを通じて、CSP に事前に解があることがわかっていることがあります。

正式には、制約充足問題は3つの要素[ ^{13]として定義される。}${\displaystyle \langle X,D,C\rangle }$

• ${\displaystyle X=\{X_{1},\ldots ,X_{n}\}}$変数の集合であり、
• ${\displaystyle D=\{D_{1},\ldots ,D_{n}\}}$それぞれの価値領域の集合であり、
• ${\displaystyle C=\{C_{1},\ldots ,C_{m}\}}$制約のセットです。

各変数は、空でないドメイン の値を取ることができます。すべての制約は、ペア です。ここで、 はインデックスのセットであり、 は、インデックスを昇順で積った、対応するドメインの積の-項関係です。変数の評価は、変数のサブセットから、対応するドメインのサブセット内の特定の値のセットへの関数です。変数に割り当てられた値が関係 を満たす場合、評価は制約を満たします。 ${\displaystyle X_{i}}$${\displaystyle D_{i}}$${\displaystyle C_{j}\in C}$${\displaystyle \langle t_{j},R_{j}\rangle }$${\displaystyle t_{j}\subseteq \{1,2,\ldots ,n\}}$${\displaystyle k}$${\displaystyle R_{j}}$${\displaystyle k}$${\displaystyle \times _{i\in t_{j}}D_{i}}$${\displaystyle v}$${\displaystyle \langle t_{j},R_{j}\rangle }$${\displaystyle t_{j}}$${\displaystyle R_{j}}$

評価は、制約のいずれにも違反しない場合は一貫しています。評価は、すべての変数が含まれている場合、完全です。評価は、一貫性があり完全である場合、ソリューションです。このような評価は、制約充足問題を 解決すると言われています。

有限領域における制約充足問題は、通常、探索の形式を使用して解決されます。最もよく使用される手法は、バックトラッキング、制約伝播、および局所探索のバリエーションです。これらの手法は、 VLNS法のように組み合わせられることも多く、現在の研究では線形計画法などの他の技術も使用されています。^[14]

バックトラッキングは再帰アルゴリズムです。変数の部分的な割り当てを維持します。最初は、すべての変数は割り当てられていません。各ステップで、変数が選択され、すべての可能な値が順番に割り当てられます。各値について、部分的な割り当てと制約の一貫性がチェックされます。一貫性がある場合は、再帰呼び出しが実行されます。すべての値が試されると、アルゴリズムはバックトラックします。この基本的なバックトラッキング アルゴリズムでは、一貫性は、すべての変数が割り当てられているすべての制約が満たされることとして定義されます。バックトラッキングにはいくつかのバリエーションがあります。バックマーキングにより、一貫性のチェックの効率が向上します。バックジャンプにより、場合によっては「複数の変数」をバックトラックすることで、検索の一部を節約できます。制約学習により、後で検索の一部を回避するために使用できる新しい制約が推測され、保存されます。バックトラッキングでは、変数または値の選択の影響を予測するために先読みもよく使用され、サブ問題がいつ満たされるか、または満たされないかを事前に判断することがあります。

制約伝播技術は、制約充足問題を修正するために使用される手法です。より正確には、これらは、変数や制約のグループの一貫性に関連する条件である、ある種の局所的一貫性を強制する方法です。制約伝播にはさまざまな用途があります。まず、問題を同等だが通常はより簡単に解決できる問題に変換します。次に、問題の充足可能性または不充足性を証明できます。これは一般に発生するとは限りませんが、一部の制約伝播形式や特定の種類の問題では常に発生します。最もよく知られ、使用されている局所的一貫性の形式は、アーク一貫性、ハイパーアーク一貫性、およびパス一貫性です。最も一般的な制約伝播方法は、アーク一貫性を強制するAC-3 アルゴリズムです。

ローカル サーチ法は不完全な充足可能性アルゴリズムです。問題の解決策が見つかることもありますが、問題が充足可能であっても失敗する可能性があります。変数に対する完全な割り当てを反復的に改善することで機能します。各ステップで、少数の変数の値が変更され、全体的な目的は、この割り当てによって満たされる制約の数を増やすことです。最小競合アルゴリズムは、 CSP に固有のローカル サーチ アルゴリズムであり、その原則に基づいています。実際には、これらの変更がランダム選択によっても影響を受ける場合、ローカル サーチはうまく機能するようです。検索とローカル サーチの統合が開発され、ハイブリッド アルゴリズムにつながっています。

CSPは計算複雑性理論、有限モデル理論、普遍代数でも研究されています。CSPの複雑性に関する疑問は、基礎となる代数に関する重要な普遍代数的疑問につながることが判明しました。このアプローチはCSPへの代数的アプローチとして知られています。 ^[15]

すべての計算決定問題は無限テンプレートを持つCSPと多項式時間等価であるため、 ^{[16]一般的なCSPは任意の計算量を持つことができます。特に、} NP中間問題のクラス内にもCSPがあり、その存在はP≠NPという仮定の下でLadnerによって実証されました。

しかし、自然な応用から生じる CSP の大きなクラスは計算量二分法を満たしており、そのクラス内のすべての CSP はPかNP 完全のいずれかであることを意味します。したがって、これらの CSP は、 NP 中間問題を回避するNPの既知の最大のサブセットの 1 つを提供します。計算量二分法は、ブール CSP、つまり 2 要素の領域上の CSP で、利用可能なすべての関係がブール演算子である場合に、シェーファーによって最初に証明されました。この結果は、さまざまなクラスの CSP、最も顕著なのは有限領域上のすべての CSP に一般化されています。この有限領域二分法予想は、最初に Tomás Feder と Moshe Vardi によって定式化され、^[17]最終的に Andrei Bulatov ^[18]と Dmitriy Zhuk によって 2017 年に独立して証明されました。 ^[19]

複雑性の二分法が確認されている他のクラスは

• のすべての一階 簡約、^[20]${\displaystyle (\mathbb {Q} ,<)}$
• 可算ランダムグラフのすべての一階縮約、^[21]
• すべてのC関係のクラスのモデルコンパニオンのすべての一階還元、 ^[22]
• 普遍同次ポセットのすべての一階縮約、^[23]
• 同次無向グラフのすべての一階縮約、^[24]
• すべての単項構造のすべての一階縮約、^[25]
• 複雑性クラスMMSNPのすべてのCSP。^[26]

扱いやすいことが知られているCSPのほとんどのクラスは、制約のハイパーグラフが制限された木幅を持つものである^[27]か、制約は任意の形式を持つが、制約関係の集合の等式的に非自明な多型が存在するものである^{[28] 。}

有限領域二分法予想^[29]は、有限境界を持つ同次構造の縮約のすべてのCSPに対して定式化されており、そのような構造のCSPがPに属するのは、その多型クローンが等式的に非自明である場合のみであり、そうでない場合はNP困難であると述べている。

このような無限領域CSPの複雑さやその他の一般化（値CSP、定量化CSP、約束CSP）は、現在でも活発に研究されている分野です。^[30] [1][2]

すべてのCSPは結合クエリ包含問題として考えることもできる。^[31]

同様の状況が関数クラスFPと#Pの間にも存在します。ラドナーの定理の一般化により、FP ≠ #P である限り、FP にも#P 完全にも問題は存在しません。決定の場合と同様に、#CSP の問題は一連の関係によって定義されます。各問題はブール式を入力として受け取り、タスクは満足する割り当ての数を計算することです。これは、より大きなドメイン サイズを使用し、各満足する割り当てに重みを付け、これらの重みの合計を計算することでさらに一般化できます。複雑な重み付き #CSP 問題は、FP または #P 困難のいずれかであることが知られています。^[32]

制約充足問題の古典的なモデルは、静的で柔軟性のない制約のモデルを定義します。この硬直したモデルは、問題を簡単に表現することが難しいという欠点があります。^[33]さまざまな問題にモデルを適応させるために、基本的なCSP定義のいくつかの修正が提案されています。

動的CSP ^[34] ( DCSP ) は、問題の元の定式化が何らかの形で変更された場合に役立ちます。これは通常、考慮すべき制約のセットが環境によって変化するためです。^[35] DCSPは静的CSPのシーケンスと見なされ、各CSPは前のCSPの変換であり、変数と制約を追加 (制限) したり削除 (緩和) したりできます。問題の初期定式化で見つかった情報は、次の定式化を改良するために使用できます。解決方法は、情報の転送方法に応じて分類できます。

• Oracles : シーケンス内の前の CSP に対して見つかったソリューションは、現在の CSP を最初から解決するためのヒューリスティックとして使用されます。
• ローカル修復: 各 CSP は、前の CSP の部分解から開始して計算され、ローカル検索で矛盾する制約を修復します。
• 制約の記録: 矛盾する決定のグループの学習を表すために、検索の各段階で新しい制約が定義されます。これらの制約は、新しい CSP 問題に引き継がれます。

従来の CSP では、制約を厳格に扱います。つまり、制約は必須(各ソリューションはすべての制約を満たす必要があります) かつ柔軟性がありません(完全に満たされなければ完全に違反するという意味)。柔軟な CSPでは、これらの前提を緩和し、制約を部分的に緩和して、ソリューションがすべての制約に従わなくてもよいようにします。これは、プリファレンス ベースの計画におけるプリファレンスに似ています。柔軟な CSP には、次の種類があります。

• MAX-CSP では、いくつかの制約に違反することが許可され、ソリューションの品質は満たされた制約の数によって測定されます。
• 重み付け CSP は、制約の各違反が事前に定義された優先順位に従って重み付けされる MAX-CSP です。したがって、重み付けが大きい制約を満たすことが優先されます。
• ファジー CSP は、制約の満足度が変数の値の連続関数であり、完全に満たされた状態から完全に違反した状態まで変化するファジー関係として制約をモデル化します。

DCSP ^[36]では、各制約変数は別々の地理的位置を持つと考えられています。変数間の情報交換には強い制約が課せられ、制約充足問題を解決するには完全に分散されたアルゴリズムを使用する必要があります。

• 制約複合グラフ
• 制約プログラミング
• 宣言型プログラミング
• 制約付き最適化(COP)
• 分散制約最適化
• グラフ準同型
• ユニークなゲームの推測
• 重み付き制約充足問題(WCSP)

• YouTube での制約充足の簡単な紹介
• マヌエル・ボディルスキー（2021）。無限領域制約充足の複雑性。ケンブリッジ大学出版局。https://doi.org/10.1017/9781107337534
• Steven Minton、Andy Philips、Mark D. Johnston 、 Philip Laird ( 1993)。「競合の最小化: 制約充足とスケジュールの問題に対するヒューリスティック修復法」。Journal of Artificial Intelligence Research。58 ( 1–3): 161–205。CiteSeerX 10.1.1.308.6637。doi : 10.1016 /0004-3702(92)90007-k。S2CID 14830518  。 
• ツァン、エドワード (1993)。制約充足の基礎。アカデミック プレス。  0-12-701610-4出版年月日
• Chen, Hubie (2009年12 月)。「論理、複雑性、代数の出会い」。ACMコンピューティング調査。42 (1): 1–32。arXiv : cs/0611018。doi : 10.1145 /1592451.1592453。S2CID 11975818  。
• Dechter, Rina (2003)。制約処理。Morgan Kaufmann。  1-55860-890-7出版年月日
• アプト、クリストフ（2003）。制約プログラミングの原理。ケンブリッジ大学出版局。ISBN 9780521825832。  0-521-82583-0出版年月日
• ルクルトル、クリストフ (2009)。制約ネットワーク: 技術とアルゴリズム。 ISTE/ワイリー。  978-1-84821-106-3出版年月日
• Tomás Feder、「制約満足度：個人的な観点」、原稿。
• 制約アーカイブ
• モデル RB の強制満足 CSP ベンチマークは 2021-01-25 にWayback Machineでアーカイブされました
• ベンチマーク – CSPインスタンスのXML表現
• XCSP3 – CSPインスタンスを表現するために設計されたXMLベースのフォーマット
• 制約伝播 - 理論と実装の問題を詳しく概説した Guido Tack の論文