制約プログラミング

定義 — 有限領域上の制約充足問題 (または CSP) は、次の 3 つ組によって定義されます。 ${\displaystyle ({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$

• ${\displaystyle {\mathcal {X}}=\{x_{1},\dots ,x_{n}\}}$問題の変数の集合です。
• ${\displaystyle {\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}}$は変数のドメインの集合、つまり、 である。${\displaystyle k\in [1;n]}$${\displaystyle x_{k}\in {\mathcal {D}}_{k}}$
• ${\displaystyle {\mathcal {C}}=\{C_{1},\dots ,C_{m}\}}$は制約のセットです。制約は、変数のセットと、変数に同時に許可される値のセットを定義する関係によって定義されます。${\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}$${\displaystyle {\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}}$${\displaystyle {\mathcal {R}}_{i}\subseteq {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}}$${\displaystyle {\mathcal {X}}_{i}}$

定義 —  CSP の割り当て (またはモデル)は、次の組み合わせによって定義されます。 ${\displaystyle {\mathcal {A}}}$${\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}$

• ${\displaystyle {\mathcal {X_{\mathcal {A}}}}\subseteq {\mathcal {X}}}$変数のサブセットです。
• ${\displaystyle {\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k }}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_ {k}}\}}$割り当てられた変数が取る値のタプルです。

特性 —  CSP の割り当て（部分的または全体的）と、などの制約が与えられた場合、制約の変数のすべての値が に属する場合にのみ、割り当ては制約を満たします。 ${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}$${\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$${\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}$${\displaystyle P}$${\displaystyle {\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle C_{i}}$${\displaystyle {\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}}$${\displaystyle C_{i}}$${\displaystyle {\mathcal {R}}_{i}}$

定義 —  CSP のソリューションは、問題のすべての制約を満たす全体的な割り当てです。