Programação de restrição - Constraint programming

Definição  -  Um problema de satisfação de restrição em domínios finitos (ou CSP) é definido por um trio onde: ${\ displaystyle ({\ mathcal {X}}, {\ mathcal {D}}, {\ mathcal {C}})}$

• ${\ displaystyle {\ mathcal {X}} = \ {x_ {1}, \ dots, x_ {n} \}}$ é o conjunto de variáveis ​​do problema;
• ${\ displaystyle {\ mathcal {D}} = \ {{\ mathcal {D}} _ {1}, \ dots, {\ mathcal {D}} _ {n} \}}$ é o conjunto de domínios das variáveis, ou seja, para tudo o que temos ; ${\ displaystyle k \ in [1; n]}$${\ displaystyle x_ {k} \ in {\ mathcal {D}} _ {k}}$
• ${\ displaystyle {\ mathcal {C}} = \ {C_ {1}, \ dots, C_ {m} \}}$ é um conjunto de restrições. Uma restrição é definida por um conjunto de variáveis ​​e uma relação que define o conjunto de valores permitidos simultaneamente para as variáveis ​​de : ${\ displaystyle C_ {i} = ({\ mathcal {X}} _ {i}, {\ mathcal {R}} _ {i})}$${\ displaystyle {\ mathcal {X}} _ {i} = \ {x_ {i_ {1}}, \ dots, x_ {i_ {k}} \}}$${\ displaystyle {\ mathcal {R}} _ {i} \ subset {\ mathcal {D}} _ {i_ {1}} \ times \ dots \ times {\ mathcal {D}} _ {i_ {k}} }$${\ displaystyle {\ mathcal {X}} _ {i}}$

Definição  -  Uma atribuição (ou modelo) de um CSP é definida pelo casal, onde: ${\ 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}}}$ é um subconjunto de variável;
• ${\ 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}} \}}$ é a tupla dos valores obtidos pelas variáveis ​​atribuídas.

Propriedade  -  Dada uma atribuição (parcial ou total) de um CSP e uma restrição de tal como , a atribuição satisfaz a restrição se e somente se todos os valores das variáveis ​​da restrição pertencerem . ${\ 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} \ in {\ mathcal {V}} _ {\ mathcal {A}} {\ mbox {tel que}} x_ {i} \ in {\ mathcal {X}} _ {i} \}}$${\ displaystyle C_ {i}}$${\ displaystyle {\ mathcal {R}} _ {i}}$

Definição  -  A solução de um CSP é uma atribuição total que satisfaz todas as restrições do problema.