CPS

CPS

CPSs: INGREDIENTES


Conjuntos que representan las variables

Una asignación completa es un subconjunto del producto (un vector)

    Genera un espacio vectorial

Asignaciones permitidas: cuando tenemos condiciones que limitan a las asignaciones

El problema se resuelve cuando encuentras una asignación que cumple con todas las condiciones



SUDOKU

    Variable X i,j
    D i,j = {1,2,3,4,5,6,7,8,9}
   
   
Ejemplos

    SAT es un CSP.
   
   

GRAPH COLORING

    Una variable por cada vértice
    La variable te dice qué color es ese vértice
    Las condiciones son que para cada arista los colores no pueden ser iguales
   
   
   
   
Consistencia de aristas
    Idea: tratar de hacer los D i's lo más chico posibles.
   
    Gráficas bipartitas
   
    Programar: aristas por procesar
   
   
    Programar este de acá y de allá
    Criptoaritmética TWO + TWO = FOUR
   
    1.- Dominio reducido
    2.- Procesamiento de aristas