Omezení programování - Constraint programming

Definice  -  Problém uspokojení omezení na konečných doménách (nebo CSP) je definován tripletem, kde: ${\ displaystyle ({\ mathcal {X}}, {\ mathcal {D}}, {\ mathcal {C}})}$

• ${\ displaystyle {\ mathcal {X}} = \ {x_ {1}, \ tečky, x_ {n} \}}$ je sada proměnných problému;
• ${\ displaystyle {\ mathcal {D}} = \ {{\ mathcal {D}} _ {1}, \ dots, {\ mathcal {D}} _ {n} \}}$ je sada domén proměnných, tj. pro vše, co máme ; ${\ displaystyle k \ v [1; n]}$${\ displaystyle x_ {k} \ in {\ mathcal {D}} _ {k}}$
• ${\ displaystyle {\ mathcal {C}} = \ {C_ {1}, \ tečky, C_ {m} \}}$ je soubor omezení. Omezení je definováno sadou proměnných a relací, která definuje sadu hodnot povolených současně pro proměnné : ${\ displaystyle C_ {i} = ({\ mathcal {X}} _ {i}, {\ mathcal {R}} _ {i})}$${\ displaystyle {\ mathcal {X}} _ {i} = \ {x_ {i_ {1}}, \ tečky, x_ {i_ {k}} \}}$${\ displaystyle {\ mathcal {R}} _ {i} \ podmnožina {\ mathcal {D}} _ {i_ {1}} \ times \ dots \ times {\ mathcal {D}} _ {i_ {k}} }$${\ displaystyle {\ mathcal {X}} _ {i}}$

Definice  -  Přiřazení (nebo model) CSP je definováno dvojicí, kde: ${\ 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}}}} \ podmnožina {\ mathcal {X}}}$ je podmnožinou proměnné;
• ${\ 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}} \}}$ je n-tice hodnot získaných přiřazenými proměnnými.

Vlastnost  -  Vzhledem k tomu, je asignace (částečnou nebo úplnou), z CSP , a na omezení na , jako jsou asignace splňuje vazbu v případě, a pouze tehdy, když všechny hodnoty proměnných z omezení patří . ${\ 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} \ podmnožina {\ mathcal {X _ {\ mathcal {A}}}}}$${\ displaystyle {\ mathcal {A}}}$${\ displaystyle C_ {i}}$${\ displaystyle {\ mathcal {V}} _ {{\ mathcal {A}} _ {i}} = \ {v_ {i} \ v {\ mathcal {V}} _ {\ mathcal {A}} {\ mbox {tel que}} x_ {i} \ v {\ mathcal {X}} _ {i} \}}$${\ displaystyle C_ {i}}$${\ displaystyle {\ mathcal {R}} _ {i}}$

Definice  -  Řešením CSP je úplné přiřazení, které splnilo všechna omezení problému.