Qu'est-ce que la valeur la moins contraignante?

Dans les problèmes de satisfaction de contraintes, l'heuristique peut être utilisée pour améliorer les performances d'un solveur de bactracking. Trois heuristiques communément données pour les solveurs de retour arrière simples sont:

• Valeurs minimales restantes (combien de valeurs sont encore valides pour cette variable)
• Degré heuristique (combien d'autres variables sont affectées par cette variable)
• Valeur la moins contraignante (quelle valeur laissera le plus de valeurs pour les autres variables)

Les deux premiers sont assez évidents et simples à mettre en œuvre. Choisissez d'abord la variable qui a le moins de valeurs dans son domaine, et s'il y a des liens, choisissez celle qui affecte le plus de variables. De cette façon, si une étape parent du solveur a sélectionné une mauvaise affectation, vous êtes susceptible de le découvrir plus tôt et ainsi de gagner du temps si vous choisissez la variable avec le moins de valeurs restantes qui affecte le plus d'autres choses.

Celles-ci sont simples, clairement définies et faciles à mettre en œuvre.

La valeur la moins contraignante n'est pas clairement définie, partout où j'ai regardé. L'intelligence artificielle: une approche moderne (Russel & Norvig) dit simplement:

Il préfère la valeur qui exclut le moins de choix pour les variables voisines dans le graphe de contraintes.

La recherche de «valeur la moins contraignante» n'a révélé que de nombreux diaporamas universitaires basés sur ce manuel, sans plus d'informations sur la façon dont cela serait fait de manière algorithmique.

Le seul exemple donné pour cette heuristique est un cas où un choix de valeur élimine tous les choix pour une variable voisine, et pas l'autre. Le problème avec cet exemple est qu'il s'agit d'un cas trivial, qui serait éliminé immédiatement lorsque l'affectation potentielle est vérifiée pour la cohérence avec les contraintes du problème. Donc, dans tous les exemples que j'ai pu trouver, l'heuristique de valeur la moins contraignante n'a en fait pas profité aux performances du solveur, à l'exception d'un petit effet négatif de l'ajout d'une vérification redondante.

La seule autre chose à laquelle je peux penser serait de tester les affectations possibles des variables voisines pour chaque affectation, et de compter le nombre d'affectations possibles des voisins qui existent pour chaque affectation possible de cette variable, puis de classer les valeurs de cette variable basé sur le nombre d'affectations de voisins disponibles si cette valeur est choisie. Cependant, je ne vois pas comment cela offrirait une amélioration par rapport à un ordre aléatoire, car cela nécessite à la fois de tester de nombreuses combinaisons de variables et un tri basé sur les résultats du comptage.

Quelqu'un peut-il donner une description plus utile de la valeur la moins contraignante et expliquer comment cette version de la valeur la moins contraignante entraînerait réellement une amélioration?

voir ce lien:

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

Il sélectionne d'abord la variable "O" puis teste "O" avec toutes ses valeurs légales "i" pour voir le nombre de réductions sur les voisins de "O" "N". Il les ajoute tous. et sélectionne un "i" qui entraîne moins de réductions:

   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"

Il prend "i" pour que:

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

J'espère que cela peut vous aider à trouver votre réponse!

Je pense que l'essentiel ici est que ces heuristiques sont appliquées en fonction de la tâche pour laquelle le solveur est écrit. Et s'il y a une possibilité que si la valeur sélectionnée d'une variable ne laisse pas une seule valeur dans le domaine d'une autre variable (disons que nous avons un problème fortement contraint avec une seule solution), alors la solution s'arrêtera . Et une recherche aléatoire peut aller dans le bon chemin menant à une décision et à la mauvaise. Et si cela se passe mal, vous devrez faire un retour en arrière (voir le saut en arrière dirigé par le conflit), et cela prend du temps de calcul. Mais l'algorithme utilisant l'heuristique LCV est plus susceptible de suivre un chemin plus correct et aucun retour n'est requis. Mais s'il y a un problème sous-contraint, je pense que ce sera un peu comme une recherche aléatoire.