Begrænsningsprogrammering - Constraint programming

Definition  -  Et begrænset tilfredshedsproblem på begrænsede domæner (eller CSP) defineres af en triplet, hvor: ${\ displaystyle ({\ mathcal {X}}, {\ mathcal {D}}, {\ mathcal {C}})}$

• ${\ displaystyle {\ mathcal {X}} = \ {x_ {1}, \ prikker, x_ {n} \}}$ er sæt af variabler for problemet;
• ${\ displaystyle {\ mathcal {D}} = \ {{\ mathcal {D}} _ {1}, \ dots, {\ mathcal {D}} _ {n} \}}$ er sæt af domæner af variablerne, dvs. for alt, hvad vi har ; ${\ displaystyle k \ i [1; n]}$${\ displaystyle x_ {k} \ i {\ mathcal {D}} _ {k}}$
• ${\ displaystyle {\ mathcal {C}} = \ {C_ {1}, \ prikker, C_ {m} \}}$ er et sæt begrænsninger. En begrænsning defineres af et sæt variabler og en relation, der definerer det sæt værdier, der tillades samtidigt for variablerne i : ${\ displaystyle C_ {i} = ({\ mathcal {X}} _ {i}, {\ mathcal {R}} _ {i})}$${\ displaystyle {\ mathcal {X}} _ {i} = \ {x_ {i_ {1}}, \ prikker, x_ {i_ {k}} \}}$${\ displaystyle {\ mathcal {R}} _ {i} \ subset {\ mathcal {D}} _ {i_ {1}} \ times \ dots \ times {\ mathcal {D}} _ {i_ {k}} }$${\ displaystyle {\ mathcal {X}} _ {i}}$

Definition  -  En opgave (eller model) af en CSP defineres af parret, hvor: ${\ 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}}}} \ subset {\ mathcal {X}}}$ er en delmængde af variabel;
• ${\ 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}} \}}$ er tuplen for de værdier, der er taget af de tildelte variabler.

Ejendom  -  Givet en tildeling (delvis eller total) af en CSP og en begrænsning af f.eks. , Tildeler tildelingen begrænsningen, hvis og kun hvis alle værdierne for begrænsningens variabler hører til . ${\ 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} \ subset {\ mathcal {X _ {\ mathcal {A}}}}}$${\ displaystyle {\ mathcal {A}}}$${\ displaystyle C_ {i}}$${\ displaystyle {\ mathcal {V}} _ {{\ mathcal {A}} _ {i}} = \ {v_ {i} \ i {\ mathcal {V}} _ {\ mathcal {A}} {\ mbox {tel que}} x_ {i} \ i {\ mathcal {X}} _ {i} \}}$${\ displaystyle C_ {i}}$${\ displaystyle {\ mathcal {R}} _ {i}}$

Definition  -  En løsning af en CSP er en total opgave, der opfylder alle problemets begrænsninger.