5. Problemas de satisfacción de restricciones

5. Problemas de satisfacción de restricciones

1. 5.1 PSR

   • Está definido por un conjunto de variables X1,X2,...,Xn y un conjunto de restricciones C1,,C2,...,Cn.
     • Variables: tienen un dominio no vacío Di de valores posibles.
     • Restricciónes: cada una implica un subconjunto de variables y las combinaciones aceptables de valores para ese subconjunto.
   • Un estado del problema está definido por una asignación de valores a unas o todas las variables, {Xi = vi , Xj = vj ...}
     • Consistente: no viola ninguna restricción.
       • Completa: asignación en la que se menciona cada variable. solución de un PSR es una asignación completa que satisface todas las restricciones.
   • Se le puede dar una formulación incremental.
   • La categoría más conocida de PSRs en dominios continuos son los problemas de programación lineal

2. 5.2 Búsqueda con vuelta atrás para PSR

   • Un problema es conmutativo si el orden de aplicación de cualquier conjunto de acciones no tiene ningún efecto sobre el resultado.
   • Variable y ordenamiento de valor
     • Escoger la variable con menos valores "legales" se llama heurística de mínimos valores restantes (MVR). También llamada heurística «variable más restringida» o «primero en fallar»,
   • Comprobación hacia delante
     • Siempre que se asigne una variable X, el proceso de comproba-ción hacia delante mira cada variable no asignada Y que esté relacionada con Xpor una restricción y suprime del dominio de Ycualquier valor que sea inconsistente con el valor elegido para X.
   • Propagación de restricciones
     • Es el término general para la propagación de las implicaciones de una restricción sobre una variable en las otras variables
     • Arco consistente
   • Vuelta atrás inteligente: mirando hacia atrás
     • Política muy simple para saber qué hacer cuando falla una rama de búsqueda: hacia atrás hasta la variable anterior e intentar un valor diferente para ella.
     • Conjunto conflicto: ir hacia atrás hasta el conjunto de variables que causaron el fracaso.
   • 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.

3. 5.3 Búsqueda local para problemas de satisfacción de restricciones

   • Eficaces para muchos PSR.
   • Formulación de estados completa.
   • Puede usarse en un ajuste online cuando el problema cambia

4. 5.4 La estructura de los problemas

   • Aproximaciones( estructura del problema representada en grafo de restricciones para encontrar soluciones de forma rápida) son muy generales y aplicables a otros problemas
   • Mayoría de los casos los subproblemas de un PSR están relacionado
     • El caso más simple es cuando el grafo de restricciones forma un árbol: cualquiera dos variables están relacionadas por, a lo sumo, un camino.

Bilder und Dateien der Mindmap