制約充足問題

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

制約充足問題としてモデル化できる問題の例には次のものがあります。

これらには、 CP 、ASP、ブールSAT、SMTソルバーのチュートリアルが付属していることが多い。一般的に、制約問題ははるかに難しく、これらの単純なシステムでは表現できない場合もある。「現実世界」での例としては、自動計画[ 6 ] [ 7 ]語彙の曖昧性解消[ 8 ] [ 9 ]音楽学[ 10 ]製品構成[ 11 ]資源配分[ 12 ]などがあげられる。

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

正式な定義

正式には、制約充足問題は、トリプルとして定義され、[ 13 ]⟨X、D、C⟩{\displaystyle \langle X,D,C\rangle }

  • X＝{X1、…、Xn}{\displaystyle X=\{X_{1},\ldots,X_{n}\}}変数の集合であり、
  • D＝{D1、…、Dn}{\displaystyle D=\{D_{1},\ldots ,D_{n}\}}それぞれの価値領域の集合であり、
  • C＝{C1、…、Cメートル}{\displaystyle C=\{C_{1},\ldots ,C_{m}\}}制約のセットです。

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

評価が矛盾しない場合、それは一貫性があると言えます。評価がすべての変数を含む場合、それは完全です。評価が矛盾せず完全である場合、それは解です。そのような評価は制約充足問題 を解決したと言われます。

解決

有限領域における制約充足問題は、典型的には探索法を用いて解かれる。最もよく用いられる手法は、バックトラッキング、制約伝播、局所探索の変種である。これらの手法は、 VLNS法のように組み合わせられることも少なくなく、現在の研究では線形計画法などの他の技術も用いられている。[ 14 ]

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

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

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

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

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

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

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

機能上の問題

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

変種

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

動的CSP

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

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

柔軟なCSP

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

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

分散型CSP

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

参照

参考文献

  1. ^ルクトゥール、クリストフ (2013).制約ネットワーク：テクニックとアルゴリズム. Wiley. p. 26. ISBN 978-1-118-61791-5。
  2. ^ 「制約 - オープンアクセス出版の選択肢を含む」 springer.com 2019年10月3日閲覧。
  3. ^ Chandra, Satish; Gordon, Colin S.; Jeannin, Jean-Baptiste; Schlesinger, Cole; Sridharan, Manu; Tip, Frank; Choi, Youngil (2016). 「JavaScriptの静的コンパイルのための型推論」(PDF) . 2016 ACM SIGPLAN 国際オブジェクト指向プログラミング、システム、言語、アプリケーション会議論文集. pp.  410– 429. doi : 10.1145/2983990.2984017 . ISBN 978-1-4503-4444-9。
  4. ^ Jim, Trevor, Jens Palsberg. 「サブタイプ化を伴う再帰型システムにおける型推論」著者のウェブページで入手可能（1999年）。
  5. ^ Farhi, Edward; Aram W Harrow (2016). 「量子近似最適化アルゴリズムによる量子超越性」. arXiv : 1602.07674 [ quant-ph ].
  6. ^マリク・ガラブ、ダナ・ナウ、パオロ・トラヴェルソ（2004年5月21日）『自動プランニング：理論と実践』エルゼビア、1-12頁。ISBN 978-0-08-049051-9。
  7. ^ Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning、 2009-02-06 at the Wayback Machine Ian Miguel – スライド。
  8. ^ Demetriou, George C. 「 Prologにおける制約処理を用いた語彙の曖昧性解消（CHIP）」 計算言語学会ヨーロッパ支部第6回会議議事録。計算言語学会、1993年。
  9. ^マクドナルド、マリエレン・C.、マーク・S.・サイデンバーグ。「制約充足度に基づく語彙理解と文理解の説明」心理言語学ハンドブック（第2版）。2006年、581-611ページ。
  10. ^ Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. 「 GELISP：音楽的制約充足問題と探索戦略を表現するフレームワーク」Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327–331.
  11. ^制約満足アプローチを適用した製品構成問題の解決に基数ベースの構成ルールを適用する、Dong Yang & Ming Dong、 Journal of Intelligent Manufacturing volume 24、99～111ページ（2013）
  12. ^ Modi, Pragnesh Jay他「リソース割り当てに対する動的分散制約充足アプローチ」制約プログラミングの原理と実践に関する国際会議。Springer、ベルリン、ハイデルベルク、2001年。
  13. ^スチュアート・ジョナサン・ラッセル、ピーター・ノーヴィグ（2010年）『人工知能：現代的アプローチ』プレンティス・ホール、第6章、p. ISBN 9780136042594。
  14. ^ミラノ、ミケーラ、ヴァン・ヘンテンリック、パスカル編 (2011).ハイブリッド最適化：CPAIORの10年. 組合せ最適化問題のための制約プログラミングにおけるAIとOR技術の統合に関する国際会議. ニューヨーク: シュプリンガー. ISBN 9781441916440. OCLC  695387020 .
  15. ^ Barto, Libor; Brady, Zarathustra; Bulatov, Andrei; Kozik, Marcin; Zhuk, Dmitriy (2024-05-15). 「極小テイラー代数によるCSPへの3つの代数的アプローチの統合」. Theoretics . 3 11361. arXiv : 2104.11808 . doi : 10.46298/theoretics.24.14 . ISSN 2751-4838 . 
  16. ^ Bodirsky, Manuel; Grohe, Martin (2008). 「制約充足複雑性における非二分法」 . Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (編).オートマトン、言語、プログラミング. コンピュータサイエンス講義ノート. 第5126巻. ベルリン、ハイデルベルク: Springer. pp.  184– 196. doi : 10.1007/978-3-540-70583-3_16 . ISBN 978-3-540-70583-3。
  17. ^ Feder, Tomás; Vardi, Moshe Y. (1998). 「単調モナディックSNPと制約充足の計算構造：データログと群論による研究」 . SIAM Journal on Computing . 28 (1): 57– 104. doi : 10.1137/S0097539794266766 . ISSN 0097-5397 . 
  18. ^ Bulatov, Andrei (2017). 「非一様CSPの二分定理」.第58回IEEEコンピュータサイエンス基礎シンポジウム議事録, FOCS 2017. IEEEコンピュータソサエティ. pp.  319– 330. arXiv : 1703.03021 . doi : 10.1109/FOCS.2017.37 . ISBN 978-1-5386-3464-6。
  19. ^ Zhuk, Dmitriy (2020). 「CSP二分法予想の証明」. Journal of the ACM . 67 (5): 1– 78. arXiv : 1704.01914 . doi : 10.1145/3402029 .
  20. ^ Bodirsky, Manuel; Kára, Jan (2010-02-08). 「時間的制約充足問題の複雑性」 . J. ACM . 57 (2): 9:1–9:41. doi : 10.1145/1667053.1667058 . ISSN 0004-5411 . 
  21. ^ Bodirsky, Manuel; Pinsker, Michael (2011). 「グラフにおけるシェーファーの定理」.第43回計算理論シンポジウム (STOC '11) の議事録. Association for Computing Machinery . pp.  655– 664. arXiv : 1011.2894 . doi : 10.1145/1993636.1993724 . ISBN 978-1-4503-0691-1. S2CID  47097319 .
  22. ^ Bodirsky, Manuel; Jonsson, Peter; Pham, Trung Van (2017-08-02). 「系統発生制約充足問題の複雑性」 . ACM Trans. Comput. Logic . 18 (3): 23:1–23:42. arXiv : 1503.07310 . doi : 10.1145/3105907 . ISSN 1529-3785 . 
  23. ^マイケル・コンパッチャー;ファム、チュン・ヴァン (2017)。 「ポーズ制約を満たすための複雑さの二分法」。コンピュータサイエンスの理論的側面に関する第 34 回シンポジウム (STACS 2017)。情報学におけるライプニッツ国際論文集。 Vol. 66. ダグシュトゥール城 – Leibniz-Zentrum für Informatik。 47:1–47:12。土井：10.4230/LIPIcs.STACS.2017.47。ISBN 978-3-95977-028-6。
  24. ^ Bodirsky, Manuel; Martin, Barnaby; Pinsker, Michael; Pongrácz, András (2019年1月). 「同質グラフの縮約における制約充足問題」 . SIAM Journal on Computing . 48 (4): 1224– 1264. arXiv : 1602.05819 . doi : 10.1137/16M1082974 . ISSN 0097-5397 . 
  25. ^ Bodirsky, Manuel; Mottet, Antoine (2018-05-20)、「単項構造の一次縮約の二分法」、Logical Methods in Computer Science、14 (2) 3264、arXiv : 1601.04520、doi : 10.23638/LMCS-14(2:13)2018
  26. ^ Bodirsky, Manuel; Madelaine, Florent; Mottet, Antoine (2018-07-09). 「単調モナディックSNPの計算量二分法の普遍代数的証明」 .第33回ACM/IEEEコンピュータサイエンス論理シンポジウム議事録. LICS '18. ニューヨーク州ニューヨーク：Association for Computing Machinery. pp.  105– 114. arXiv : 1802.03255 . doi : 10.1145/3209108.3209156 . ISBN 978-1-4503-5583-4。
  27. ^ Barto, Libor; Kozik, Marcin (2014-01-01). 「局所整合性法によって解ける制約充足問題」 . J. ACM . 61 (1): 3:1–3:19. doi : 10.1145/2556646 . ISSN 0004-5411 . 
  28. ^ Bodirsky, Manuel (2021).無限領域制約充足の計算量. 論理学講義ノート. ケンブリッジ: ケンブリッジ大学出版局. ISBN 978-1-107-04284-1。
  29. ^マヌエル・ボディルスキー;ピンスカー、マイケル。アンドラーシュ州ポングラチュ（2021年3月）。「射影クローン準同型性」。記号論理ジャーナル。86 (1 ) : 148–161.arXiv : 1409.4601 。土井：10.1017/jsl.2019.23。hdl : 2437/268560。ISSN 0022-4812。 
  30. ^ Pinsker, Michael (2022-03-31). 「無限領域制約充足における現在の課題：無限の羊のジレンマ」. arXiv : 2203.17182 [ cs.LO ].
  31. ^ Kolaitis, Phokion G.; Vardi, Moshe Y. (2000). 「連言クエリの包含と制約充足」 . Journal of Computer and System Sciences . 61 (2): 302– 332. doi : 10.1006/jcss.2000.1713 .
  32. ^ Cai, Jin-Yi; Chen, Xi (2012). 「複素重みを持つCSPの計数計算の複雑さ」.第44回ACM計算理論シンポジウム (STOC '12) 論文集. pp.  909– 920. arXiv : 1111.2384 . doi : 10.1145/2213977.2214059 . ISBN 978-1-4503-1245-5. S2CID  53245129 .
  33. ^ミゲル、イアン（2001年7月）「動的で柔軟な制約充足とAIプランニングへの応用」（博士論文）エディンバラ大学情報学部. CiteSeerX 10.1.1.9.6733 . hdl : 1842/326 . 
  34. ^ Dechter, R. および Dechter, A.、「動的制約ネットワークにおける信念の維持」、Wayback Machineに 2012-11-17 にアーカイブ、AAAI-88 誌、37–42 ページ。
  35. ^動的制約充足問題における解の再利用、トーマス・シークス
  36. ^ Duffy, KR; Leith, DJ (2013年8月)、「分散型制約充足」、IEEE/ACM Transactions on Networking、21(4)、第21巻、pp.  1298– 1308、arXiv : 1103.3240、doi : 10.1109/TNET.2012.2222923、S2CID 11504393 

さらに読む

「 https://en.wikipedia.org/w/index.php?title=制約満足度問題&oldid =1334133666」より取得