Problemas de satisfacción de restricciones

Problemas de satisfacción de restricciones

1. Búsqueda con vuelta atrás para PSR

   • Elige valores para una variable a la vez y vuelve atras cuando una variable no tiene ningun valor legal para asignarle
   • Variable y ordenamiento
     • Heuristica de minimos restantes
       • Escoge una variable que tiene la mayor probabilidad de fracaso
   • Vuelta atras inteligente
     • Metodo salto atras
     • Conjunto conflicto
   • Propagacion de restricciones
     • Propagacion de las implicaciones de una restriccion sobre una variable
     • arco consistente
   • Comprobacion hacia adelante
     • Cuando se asigna una variable X, el proceso se fija en cada variable no asignada Y

2. Estructura de los problemas

   • Subproblemas independientes
     • Descomposicion en arbol
       • Resolver cada subproblema independientemente y combinar las soluciones
   • Cualquier solucion para una variable y para la otra variable produce una solucion para el mapa entero

3. Busqueda local

   • Cambia el valor de una variable a la vez
     • Seleccionar el valor que cause el numero minimo de conflictos con otras variables
       • Heuristica de minimos conflictos
   • Formulacion de estados completa
     • Se le asigna a cada variable un valor inicial

4. Problemas de satisfaccion de restricciones

   • Asignacion de valores a una o todas las variables
     • Asignacion consistente
       • No viola ninguna restriccion
     • Asignacion completa
       • Se menciona cada variable
       • Satisface todas las restricciones
   • Dominio finito
   • Formulacion incremental
     • Estado inicia
     • Funcion sucesor
     • Costo del camino
     • Test objetivo
   • Heuristicas de proposito general
   • Grafo de restricciones
   • Conjunto de restricciones
     • Implica un subconjunto de variables y especifica las combinaciones aceptables de valores para ese subconjunto
   • Conjunto de variables
     • Dominio de valores posibles