Problemas de satisfacción de restricciones

Búsqueda con vuelta atrás para PSR
1. Elige valores para una variable a la vez y vuelve atras cuando una variable no tiene ningun valor legal para asignarle
2. Variable y ordenamiento
  1. Heuristica de minimos restantes
    1. Escoge una variable que tiene la mayor probabilidad de fracaso
3. Vuelta atras inteligente
  1. Metodo salto atras
  2. Conjunto conflicto
4. Propagacion de restricciones
  1. Propagacion de las implicaciones de una restriccion sobre una variable
  2. arco consistente
5. Comprobacion hacia adelante
  1. Cuando se asigna una variable X, el proceso se fija en cada variable no asignada Y
Estructura de los problemas
1. Subproblemas independientes
  1. Descomposicion en arbol
    1. Resolver cada subproblema independientemente y combinar las soluciones
2. Cualquier solucion para una variable y para la otra variable produce una solucion para el mapa entero
Busqueda local
1. Cambia el valor de una variable a la vez
  1. Seleccionar el valor que cause el numero minimo de conflictos con otras variables
    1. Heuristica de minimos conflictos
2. Formulacion de estados completa
  1. Se le asigna a cada variable un valor inicial
Problemas de satisfaccion de restricciones
1. Asignacion de valores a una o todas las variables
  1. Asignacion consistente
    1. No viola ninguna restriccion
  2. Asignacion completa
    1. Se menciona cada variable
    2. Satisface todas las restricciones
2. Dominio finito
3. Formulacion incremental
  1. Estado inicia
  2. Funcion sucesor
  3. Costo del camino
  4. Test objetivo
4. Heuristicas de proposito general
5. Grafo de restricciones
6. Conjunto de restricciones
  1. Implica un subconjunto de variables y especifica las combinaciones aceptables de valores para ese subconjunto
7. Conjunto de variables
  1. Dominio de valores posibles

Next up

Problemas de satisfacción de restricciones

Description

Resource summary

Similar

	Created by Jack Fenix over 6 years ago