Problème de satisfaction de contraintes

Un problème de satisfaction de contraintes remplace la vision en boîte noire de la recherche - un état initial, une fonction d’actions et un test de but - par une description explicite de ce qui rend un état bon ou mauvais. Les variables portent les choix, les domaines portent les options, et les contraintes enregistrent quelles combinaisons sont permises. Une affectation est cohérente quand elle ne viole aucune contrainte, complète quand chaque variable a une valeur, et c’est une solution quand elle est les deux. Comme la description est standardisée, le solveur n’a besoin de rien de spécifique au problème : il peut inspecter les contraintes elles-mêmes pour décider quoi essayer ensuite et quoi écarter.

Les contraintes binaires induisent un graphe de contraintes, un nœud par variable et une arête par contrainte, et la forme de ce graphe est la carte du problème dont dispose le solveur. Le degré d’une variable, le nombre de contraintes auxquelles elle participe, prédit à quel point l’affecter restreindra tout le reste. L’exemple standard de Russell et Norvig colorie les sept régions de l’Australie avec trois couleurs sous neuf contraintes d’adjacence ; l’Australie-Méridionale est de degré cinq et la Tasmanie, une île, de degré zéro : la couleur de la Tasmanie est donc libre et les dix-huit solutions se répartissent en six coloriages continentaux multipliés par trois.

Deux idées rendent la forme praticable. La première est la commutativité : atteindre une affectation partielle par un ordre d’affectations revient au même que par n’importe quel autre, l’ordre ne porte donc aucune information et un solveur peut fixer une variable par niveau de son arbre. Pour sept variables et trois valeurs, cela transforme 7! × 3⁷ feuilles en 3⁷, un facteur 5 040 gratuit. La seconde est la propagation : avant et pendant la recherche, les valeurs sans partenaire possible peuvent être supprimées d’emblée. La cohérence d’arc, imposée par l’algorithme AC-3, rend cohérente toute paire ordonnée de variables en un temps polynomial en la taille du problème.

La propagation est correcte mais incomplète. Elle ne supprime jamais une valeur susceptible de figurer dans une solution, et pourtant un problème peut franchir la cohérence d’arc sans en avoir aucune, parce que la cohérence d’arc n’inspecte que deux variables à la fois et ne peut pas voir une contradiction qui en exige trois. Ce qui comble l’écart, c’est la recherche avec retour arrière, et ce qui rend cette recherche rapide, c’est l’association de l’inférence avec les heuristiques d’ordonnancement : les valeurs restantes minimales retiennent la variable la plus proche de l’échec, le degré départage les égalités, et la valeur la moins contraignante choisit celle qui laisse le plus de marge aux voisines. L’association compte davantage que chacune des moitiés, puisqu’une heuristique d’ordre des variables qui lit les tailles de domaine ne fait absolument rien tant que rien ne réduit les domaines.

Colorier l’Australie utilise sept variables de domaine {rouge, vert, bleu} et neuf contraintes d’inégalité, une par frontière commune. Lancé sur le problème intact, AC-3 n’effectue aucune révision : chaque région dispose encore de trois couleurs, aucune valeur ne peut donc être supprimée et la propagation n’a rien sur quoi travailler tant qu’une affectation n’a pas créé d’asymétrie.

Posez l’Australie-Occidentale au rouge et le Queensland au vert et la branche est déjà morte, même si une seule méthode s’en aperçoit. La vérification en avant laisse le Territoire du Nord et l’Australie-Méridionale avec la seule valeur bleu et poursuit ; la cohérence d’arc complète propage ce singleton un cran plus loin, constate que les deux régions sont voisines, vide le domaine de l’Australie-Méridionale et signale un échec. Une énumération exhaustive sur les cinq régions restantes confirme qu’il y a zéro complétion.

Mesurer le problème des N reines montre pourquoi les heuristiques sont habituellement mal présentées. À n = 24, le retour arrière simple essaie 411 608 affectations ; ajouter les seules valeurs restantes minimales en essaie exactement autant, parce que rien ne supprime de valeurs et que tous les domaines sont à égalité. La seule vérification en avant ramène le compte à 286 963, et les deux ensemble à 43.