¿Qué es el valor de menor restricción?

En problemas de satisfacción de restricciones, la heurística se puede utilizar para mejorar el rendimiento de un solucionador de bactracking. Tres heurísticas comúnmente dadas para los solucionadores de retroceso simples son:

• Valores restantes mínimos (cuántos valores siguen siendo válidos para esta variable)
• Grado heurístico (cuántas otras variables se ven afectadas por esta variable)
• Valor de restricción mínima (qué valor dejará la mayoría de los otros valores para otras variables)

Los dos primeros son bastante obvios y fáciles de implementar. Primero elija la variable que tenga el menor valor restante en su dominio, y si hay vínculos, elija la que afecte a la mayoría de las otras variables. De esta manera, si un paso principal en el solucionador eligió una mala asignación, es probable que lo descubra antes y, por lo tanto, ahorre tiempo si elige la variable con el menor valor restante que afecta la mayoría de las otras cosas.

Esos son simples, claramente definidos y fáciles de implementar.

El valor de menor restricción no está claramente definido, en ningún lugar que haya buscado. Inteligencia artificial: un enfoque moderno (Russel y Norvig) simplemente dice:

Prefiere el valor que descarta la menor cantidad de opciones para las variables vecinas en el gráfico de restricción.

La búsqueda del "valor de menor restricción" solo arrojó muchas presentaciones de diapositivas universitarias basadas en este libro de texto, sin más información sobre cómo se haría esto algorítmicamente.

El único ejemplo dado para esta heurística es un caso en el que una opción de valor elimina todas las opciones para una variable vecina, y la otra no. El problema con este ejemplo es que se trata de un caso trivial, que se eliminaría de inmediato cuando se verificara la asignación potencial para verificar la coherencia con las restricciones del problema. Entonces, en todos los ejemplos que pude encontrar, la heurística de valor de menor restricción en realidad no benefició el rendimiento del solucionador de ninguna manera, excepto por un pequeño efecto negativo al agregar una verificación redundante.

Lo único que se me ocurre sería probar las posibles asignaciones de las variables vecinas para cada asignación, y contar el número de posibles asignaciones de los vecinos que existen para cada posible asignación de esta variable, luego ordenar los valores para esta variable basado en el número de asignaciones de vecinos disponibles si se elige ese valor. Sin embargo, no veo cómo esto ofrecería una mejora con respecto a un orden aleatorio, ya que esto requiere probar numerosas combinaciones de variables y ordenarlas según los resultados del recuento.

¿Alguien puede dar una descripción más útil del valor de menor restricción y explicar cómo esa versión del menor valor de restricción realmente produciría una mejora?

ver este enlace:

https://people.cs.pitt.edu/~wiebe/courses/CS2710/lectures/constraintSat.example.txt

Primero selecciona la variable "O" y luego prueba "O" con todos sus valores legales "i" para ver el número de reducciones en los vecinos "N" de "O". Agrega todos ellos. y elige una "i" que causa menos reducciones:

   sums = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
   For i from 0 to 9:  
     plug "o=i" into the constraint formulas
     For each neighbor "N" of "o" in the constraint graph:
       sums[i] += the number of values remaining for "N"

Elige "i" para que:

sums[i] = MAX{sums[i] | for all "i" that is a member of "O",s valid values}

¡Espero que esto pueda ayudarte a encontrar tu respuesta!

Creo que lo principal aquí es que estas heurísticas se aplican según la tarea para la que se escribe el solucionador. Y si existe la posibilidad de que si el valor seleccionado de una variable no deja un solo valor en el dominio de otra variable (digamos que tenemos un problema muy limitado con solo una solución), entonces la solución se detendrá . Y una búsqueda aleatoria puede ir por el camino correcto que conduce a una decisión y la equivocada. Y si sale mal, tendrá que hacer un seguimiento hacia atrás (ver saltos hacia atrás dirigidos por conflictos), y lleva tiempo de cálculo. Pero es más probable que el algoritmo que utiliza la heurística LCV siga un camino más correcto y no se requieren retornos. Pero si hay un problema poco restringido, creo que será muy parecido a la búsqueda aleatoria.