Saltar a contenido

Clase 2: Introducción a CSP

Características de la CSP

Como es un problema de satisfacción de restricciones

  • Conjunto de variables
  • Cada una de estas variable tiene un Dominio finito
  • Estas variables están sujetas de restricciones

Ejemplo

SEND + MORE

MONEY

Escribir:

1000S+E100+N10+D+M1000+O100+R10+E = M10000+O1000+N100+E10+Y

Incluyendo variables de acarreo C1,..C4 cuyo dominio es binario

D + E = 10*C1+Y

C1 + N + R = 10*C2 + E

C2 + E + O = 10*C3 + N

C3 + S + M = 10*C4 + O

C4 = M

Otra forma programación entera

Creamos un conjunto de variables adicional para verificar que una variable mayor que la otra, por ejemplo \(z_{S,E}\) si S es mayor que E, toma el valor 0 y si es E es mayor que S entonces toma el valor de 1, se garantiza que S es diferente que E

image.png