Posts

CPS 2

Image
...CPS Planeación     Estado inicial     acciones posibles     Objetivo     (Esto es búsqueda en grafos)     Representar en estados     Muchos estados posibles     Muchas acciones     Crece el número de estados exponencialmente         ¿Como hacer para no revisar todas las variables que no son relevantes?         STRIPS         La idea es factorizar los estados en variables relevantes.         Representamos condiciones compactamente.         Variables booleanas.                 Cada variable se convertir+a en muchas variables, una por cada tiempo.         Una variable por cada propiedad en cada tiempo.                 *Dado el estado inicial, llegar al estado final.       ...
Post a Comment
Read more

Backtracking

Backtracking Pintar territorios en un mapa - (1(prioridad uno))El que tiene menos opciones para colorear - (2)Tomar el nodo que tiene más conexiones     - Pintas los que ya están definidos     * Elegir el valor que ponga menos restricciones Comprobación hacia adelante tablita hacer backtracking en la tabla Infiriendo restricciones Forzando restricciones *Un ciclo de corte es un conjunto de nodos que si los quitas, se deshacen los ciclos Criptoaritmética Mínimo conflicto
Post a Comment
Read more

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         Progr...
2 comments
Read more