Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 5. Problemas de Satisfacción de Restricciones (Problema de…
Capítulo 5. Problemas de Satisfacción de Restricciones
Problema de satisfacción de restricciones
Formalmente, un problema de satisfacción de restricciones (o PSR) está definido por un conjunto de variables, X1, X2…, Xn, y un conjunto de restricciones, C1, C2…, Cm.
Cada variable Xi tiene un dominio vacío Di de valores posibles.
Cada restricción Ci implica algún subconjunto de variables y especifica lo aceptable combinaciones de valores para ese subconjunto.
Asignación consistente o legal
Una asignación que no infringe ninguna restricción
Asignación Completa
Es una asignación en la que se menciona cada variable
Solución de un PSR
Es una asignación completa que satisface todas las restricciones.
Ventajas de tratar un problema como PSR
La función sucesor y el test objetivo pueden escribirse de un modo genérico para que se aplique a todo PSR
Podemos desarrollar heurísticas eficaces y genéricas que no requieran ninguna información adicional ni experta del dominio específico.
La estructura del grafo de las restricciones puede usarse para simplificar el proceso de solución,produciendo una reducción exponencial de la complejidad.
Formulación incremental a un PSR como un problema de búsqueda estándar
Estado inicial
Asignación vacía {}, en la que no se asignan todas las variables
Función de sucesor
Un valor se puede asignar a cualquier variable no asignada,
a condición de que no suponga ningún conflicto con variables antes asignadas.
Test objetivo
La asignación actual es completa
Costo del camino
Un coste constante para cada paso.
Tipos de Restricciones
Restricción Unaria
Restringe los valores de una sola variable.
Restricción binaria
Relaciona dos variables
Restricción de orden alto
Implican tres o más variables
Búsqueda con vuelta atrás para PSR
Se utiliza para la búsqueda primero en profundidad
que elige valores para una variable a la vez y vuelve atrás cuando una variable no tiene ningún valor legal para asignarle.
Variable y ordenamiento de valor
Esta idea intuitiva (para elegir la variable con menos valores "legales") se denomina heurística de valor mínimo restante
(MRV)
.
El grado heurístico intenta reducir el factor de bifurcación en opciones futuras seleccionando la variable entre las variables no asignadas que está involucrada en el mayor número de restricciones.
La heurística del valor menos restringido prefiere el valor que excluye las pocas opciones de las variables vecinas en el gráfico de restricción
La heurística trata de dejar la flexibilidad máxima de las asignaciones
de las variables siguientes.
Propagación de Restricciones
La propagación de las implicaciones de una restricción sobre una variable en las otras variables se denomina propagación de restricción.
El arco constante proporciona un método rápido de propagar restricciones. "El arco" se refiere a un arco dirigido en el gráfico de restricción.
Comprobación hacia delante
Cada vez que se asigna una variable X, el proceso de verificación hacia adelante observa cada variable no asignada Y que está relacionada con X por una restricción y elimina cualquier valor del dominio de Y que es inconsistente con el valor elegido para X.
Manejo de Restricciones especiales
Ciertos tipos de restricciones a menudo aparecen en problemas reales y se pueden manejar utilizando algoritmos de propósito especial más eficientes que los métodos de propósito general
Vuelta atrás inteligente: mirando hacia atrás
Cuando hay un conflicto con una variable, puede volver a la variable anterior e intentar con un valor diferente.
Un enfoque más inteligente para ir hacia atrás es regresar al conjunto de variables que causaron la falla, llamado conflicto de conjunto.
El conflicto establecido para la variable X es el conjunto de variables previamente asignadas que están relacionadas con X por las restricciones.
Búsqueda local para problemas de satisfacción de
restricciones
Los algoritmos de búsqueda local demuestran ser muy efectivos para resolver muchos PSR.
Usan una formulación de estado completa
El estado inicial asigna un valor a cada variable
La función sucesora generalmente funciona cambiando el valor de una variable a la vez.
la búsqueda local es que se puede usar en una configuración en línea cuando el problema cambia.
Estructura de los problemas
La complejidad de resolver un PSR está fuertemente relacionada con la estructura de su gráfico de restricción.
Los problemas estructurados por árbol se pueden resolver en tiempo lineal.
Algoritmos aproximados eficientes
El acondicionamiento de corte
Puede reducir un PSR general a un árbol estructurado y es muy eficiente si se puede encontrar un corte pequeño.
Descomposición en árbol
Un conjunto de subproblemas relacionados
Cada subproblema se resuelve independientemente, y las soluciones que resultan son entonces combinadas
Debe satisfacer tres exigencias
Cada variable en el problema original aparece en al menos uno de los subproblemas.
Si dos variables están relacionadas por una restricción en el problema original, deben aparecer juntas (junto con la restricción) en al menos uno de los subproblemas.
Si una variable aparece en dos subproblemas en el árbol, debe aparecer en cada subproblema a lo largo del camino que une a esos subproblemas.