Please enable JavaScript.
Coggle requires JavaScript to display documents.
Problemas de Satisfacción de Restricciones (Búsqueda con vuelta atrás para…
Problemas de Satisfacción de Restricciones
Problema de Satisfacción de Restricciones (PSR)
Definición formal
Conjunto finito variables
X1, X2, X3, ..., Xn
Cada variable
Conjunto no vacío D
Conjunto finito de restricciones
C1, C2, C3, ..., Cn
Cada restricción
Subconjunto de variables
Estado
Asignaciones
{Xi = vi, ..., Xj = vj}
Asignación
Consistente
Cumple restricciones
Completa
Menciona cada variable
Solución
Asignación completa
En grafos
Nodos = variables
Arcos = restricciones
Formulación
Función de sucesor
Asignar valor a una variable
Test objetivo
Asignación completa
Estado inicial
Ninguna variable asignada
Costo del camino
Constante
Búsqueda con vuelta atrás para PSR
Similar a búsqueda primero en profundidad
Variable y ordenamiento de valor
Selecciona siguiente variable
Orden en la lista de variables
Búsqueda eficiente
Heurística de mínimos valores restantes
Escoger variable con menos valores
Propagación de la información
A través de restricciones
Comprobación hacia adelante
Asigna variable X
Observa variables Y no asignadas
Relacionadas con X
Por restricción
Suprime valores inconsistentes
Propagación de restricciones
Arco consistente
Método de propagación de restriccionestext
Dirigido
En el grafo de restricciones
Para todo x
Existe un 'y' consistente con x
Aplicarse repetidamente
Problemas
Quitar inconsistencias pueden surgir otras
Vuelta atras inteligente
Dirigirse a variable anterior
Conjunto conflicto
Incosistencia
Problemas para cumplir restricciones
Búsqueda local para PSR
Formulación de estados completa
Estado inicial
Asigna valor a variables
Función sucesor
Cambia valores de variables
Heurística
Seleccionar valor con menos conflictos
Independiente del tamaño del problema
Estructura de problemas
Dividir en subproblemas
Componentes conectados
Subproblemas del PSR
Eficiencia
Quitar nodos
Nodos que sufren colisiones
Acondicionamiento del corte
Probabilidades
Descomposición de árbol
Problema original
Cada variable aparece en los subproblemas
Variables relacionadas por restricción
Deben estar juntas en un subproblema
Variable aparece en dos subproblemas
Estar presente en subproblemas relacionados