Problèmes de satisfaction de contraintes

Un problème de satisfaction de contraintes décrit un ensemble de choix et les règles qui les relient. Son état est une représentation factorisée : tu peux examiner chaque variable et sa valeur, puis réutiliser des méthodes générales de réduction des domaines et de recherche.

Variables, domaines et contraintes

Une variable désigne quelque chose à choisir. Son domaine énumère ses valeurs autorisées. Une contrainte précise les combinaisons qui peuvent se présenter ensemble. Pour les ateliers A et B, chaque valeur est un créneau de $\{1,2,3\}$. La règle « A précède B » a pour portée $\{A,B\}$ et pour relation $\{(1,2),(1,3),(2,3)\}$. L'écriture $A<B$ exprime la même relation de façon concise.

La portée indique les variables concernées ; la relation donne les tuples de valeurs autorisés. Confondre les deux conduit à un modèle dans lequel « rouge » devient une variable. Dans la coloration de carte, les régions sont les variables et les couleurs sont les valeurs.

Qu'est-ce qu'une solution ?

Une affectation donne des valeurs aux variables. Trois critères décrivent son état :

• Elle est partielle si certaines variables n'ont pas de valeur.
• Elle est complète si chaque variable a une valeur.
• Elle est cohérente si elle ne viole aucune contrainte entre les variables affectées.

Une solution doit être complète et cohérente. Avec $A=2$ seule, l'affectation est cohérente mais partielle. La compléter avec $B=1$ la rend complète et incohérente. Choisir $B=3$ donne une solution à cet exemple à deux variables. Une affectation partielle cohérente peut néanmoins être impossible à compléter : les variables non affectées peuvent manquer de choix compatibles.

Lire un graphe de contraintes

Pour un problème de satisfaction de contraintes binaire, trace un nœud par variable et une arête pour chaque paire soumise à une contrainte. Dans une carte simplifiée de l'Australie, les variables sont WA, NT, SA, Q, NSW, V et T, chacune de domaine {rouge, vert, bleu}. Les paires voisines sont WA-NT, WA-SA, NT-SA, NT-Q, SA-Q, SA-NSW, SA-V, Q-NSW et NSW-V. Chaque arête exige des couleurs différentes.

Une solution est WA rouge, NT vert, SA bleu, Q rouge, NSW vert, V rouge et T rouge. Vérifie chaque arête, y compris SA-V. T n'a aucune arête : sa couleur est donc indépendante de celle du continent. Il y a 6 colorations du continent et 3 choix pour T, soit 18 solutions. Une contrainte concernant plusieurs variables nécessite une représentation par hypergraphe ; un nœud supplémentaire pour la contrainte peut être relié à chaque variable de sa portée.

Domaines et taille de la recherche

Un domaine discret fini est une liste fixe, comme trois couleurs. Un domaine discret infini pourrait contenir tous les horaires de début entiers positifs ou nuls. Un domaine continu pourrait contenir des horaires à valeurs réelles. Ces deux derniers types nécessitent des représentations et des méthodes adaptées ; la programmation linéaire traite les contraintes linéaires continues.

Pour $n$ variables ayant chacune $d$ valeurs, il y a $d^n$ affectations complètes. La carte possède $3^7=2187$ affectations candidates avant que les contraintes n'en éliminent. Les problèmes de satisfaction de contraintes finis comprennent des problèmes NP-complets : on ne connaît donc pas de méthode générale de résolution en temps polynomial. Leur structure interne permet néanmoins de réduire la recherche : le solveur peut éliminer un choix sans énumérer toutes les affectations complètes qui le contiennent. Seules les valeurs finales déterminent si la réponse est valide ; le chemin suivi pour les trouver est sans importance.

Les contraintes se distinguent par le nombre de variables qu'elles relient et selon qu'elles expriment des exigences ou des préférences. Reconnaître cette structure t'aide à écrire un modèle fidèle et à choisir des méthodes de propagation utiles.

Classer selon la portée

Une contrainte unaire restreint une variable. Si l'atelier E ne peut pas utiliser le créneau 1, applique $E\mathrm{\ne }1$ en réduisant son domaine de $\{1,2,3\}$ à $\{2,3\}$ avant la recherche. Une contrainte binaire relie deux variables, comme $A<B$ ou $A\mathrm{\ne }D$. Un problème de satisfaction de contraintes binaire ne contient que des contraintes unaires et binaires.

Une contrainte d'arité supérieure concerne au moins trois variables. Si les durées des tâches X, Y et Z doivent remplir 10 heures, écris $X+Y+Z=10$. Chaque durée appartenant à $\{1,2,3,4,5\}$, le tuple $(2,3,4)$ ne convient pas, tandis que $(2,3,5)$ convient. Pour vérifier une règle d'arité supérieure, les valeurs doivent convenir ensemble.

Conserver les contraintes globales utiles

Une contrainte globale donne un nom à une règle portant sur un groupe de variables de taille variable. $\mathrm{Alldiff}(X_1,\dots ,X_k)$ exige des valeurs différentes pour chaque paire. Son ensemble de solutions est égal à celui défini par les $k(k-1)\mathrm{/}2$ inégalités prises deux à deux. Pour neuf cases de Sudoku, cela représente 36 contraintes binaires.

La forme globale permet aussi au solveur de raisonner sur le groupe. Trois variables limitées à deux valeurs distinctes ne peuvent pas toutes être différentes, même si chaque paire séparément admet une affectation compatible. Des ensembles de solutions identiques ne garantissent pas une réduction des domaines aussi forte.

Une règle de capacité peut aussi être globale. Ici, $\mathrm{Atmost}(10,P_1,P_2,P_3)$ signifie $P_1+P_2+P_3\le 10$ : le nombre total de personnes affectées aux trois tâches ne peut pas dépasser dix. Les arguments représentent des quantités additionnées ; cette règle autorise donc, par exemple, $(3,4,3)$.

Convertir une contrainte finie en forme binaire

Introduis une variable auxiliaire U dont les valeurs sont les triplets autorisés pour $X+Y+Z=10$. Une valeur possible est $(2,3,5)$. Ajoute trois contraintes binaires : la première composante de U est égale à X, la deuxième à Y et la troisième à Z. Choisir cette valeur pour U exige donc $X=2$, $Y=3$ et $Z=5$.

Chaque triplet valide d'origine correspond à une valeur de U et chaque affectation cohérente comprenant U produit un triplet valide d'origine. Cette construction permet aux méthodes binaires de traiter une contrainte finie d'arité supérieure. Elle a pour coût un domaine de tuples potentiellement grand : c'est pourquoi les solveurs conservent souvent la règle globale ou d'arité supérieure d'origine.

Exigences et préférences

Avec des contraintes souples, la tâche devient un problème d'optimisation sous contraintes : satisfaire toutes les règles dures et minimiser le coût total des préférences. La séparation et évaluation et la recherche locale peuvent servir à l'optimisation.

Teste le modèle avec une affectation que tu sais valide et une autre que tu sais invalide. Une inégalité inventée entre des ateliers sans lien élimine des emplois du temps légitimes ; l'oubli d'une contrainte liée à un formateur commun autorise des emplois du temps impossibles. Les préférences demandent aussi de l'attention : transformer « après-midi préférable » en « après-midi obligatoire » peut éliminer tous les emplois du temps réalisables.

Un modèle doit décrire les décisions assez directement pour que les règles soient faciles à exprimer. Commence par déterminer ce qu'il faut choisir, puis attribue des domaines et traduis chaque exigence à l'aide des variables qu'elle concerne réellement.

Construire un emploi du temps d'ateliers

Cinq ateliers d'un créneau chacun se partagent trois créneaux : 1 le matin, 2 au milieu de la journée et 3 l'après-midi. Soit A l'atelier Bases de Python, B Python avancé, C Statistiques, D Bases de données et E Éthique. Chaque atelier est une variable de domaine initial $\{1,2,3\}$.

Les participants communs imposent $A\mathrm{\ne }C$, $A\mathrm{\ne }D$, $C\mathrm{\ne }D$, $B\mathrm{\ne }C$, $C\mathrm{\ne }E$ et $D\mathrm{\ne }E$. L'atelier de base doit précéder l'atelier avancé, donc $A<B$. Le formateur en éthique arrive au milieu de la journée, donc $E\mathrm{\ne }1$. Cela donne sept arêtes binaires et une règle unaire ; C a quatre voisins.

L'affectation $A=2,B=3,C=1,D=3,E=2$ satisfait toutes les règles : chaque paire d'ateliers ayant des participants communs occupe des créneaux différents, l'atelier de base précède l'atelier avancé et l'atelier Éthique n'est pas au créneau 1. C'est la seule affectation valide parmi les $3^5=243$ candidates. Les ateliers B et D peuvent tous deux utiliser le créneau 3, car aucune règle ne leur impose d'être différents.

Choisir plutôt une variable par créneau ferait de chaque valeur un sous-ensemble d'ateliers, avec jusqu'à $2^5=32$ sous-ensembles possibles par créneau. Les règles devraient alors examiner ces ensembles et garantir que chaque atelier a lieu une fois. Choisir les ateliers comme variables permet de garder des contraintes plus simples.

Exprimer les horaires des tâches et les ressources partagées

Dans l'ordonnancement d'atelier, utilise une variable d'heure de début pour chaque tâche. Préparer prend 20 minutes, Analyser 40 et Rédiger le rapport 30. Les heures de début sont des nombres entiers de minutes positifs ou nuls. L'ordre et l'échéance de 120 minutes donnent

Les débuts au plus tôt sont 0, 20 et 60. En remontant depuis l'échéance, on obtient les débuts au plus tard 30, 50 et 90. Les intervalles sont donc $S_P\in [0;30]$, $S_A\in [20;50]$ et $S_R\in [60;90]$.

Deux tâches qui partagent une machine nécessitent une contrainte disjonctive : $S_X+d_X\le S_Y$ ou $S_Y+d_Y\le S_X$. L'une ou l'autre peut venir en premier, mais elles ne peuvent pas se chevaucher. Une simple contrainte de précédence imposerait un ordre particulier et supprimerait l'autre possibilité.

Modéliser les affectations et les énigmes

Pour trois rapports affectés à trois relecteurs, fais de chaque rapport une variable dont les valeurs sont les relecteurs. Utilise Alldiff si chaque relecteur traite un rapport. Un conflit d'intérêts retire un relecteur du domaine du rapport concerné.

Pour le problème des n reines, soit $Q_i$ la ligne de la reine dans la colonne $i$. Une reine par colonne est intégrée au modèle. Pour chaque paire, impose $Q_i\mathrm{\ne }{Q}_j$ et $\mathrm{\mid }{Q}_i-Q_j\mathrm{\mid }\mathrm{\ne }\mathrm{\mid }i-j\mathrm{\mid }$ afin d'éviter les attaques sur les lignes et les diagonales. Pour huit reines, cela réduit l'espace des possibilités : au lieu de choisir 8 cases parmi 64, soit $4426165368$ placements, on obtient $8^8=16777216$ affectations. Il y a 92 solutions.

Pour le Sudoku, les 81 variables correspondant aux cases ont pour domaine les valeurs de 1 à 9. Les chiffres donnés imposent des contraintes unaires, et les 9 lignes, 9 colonnes et 9 régions imposent chacune une contrainte Alldiff.

Choisis les unités de temps les plus grossières qui permettent encore de représenter chaque début autorisé. Des séances commençant à chaque heure nécessitent des choix à l'heure près ; des domaines à la minute près augmenteraient le travail sans ajouter d'emploi du temps utile. Termine en séparant les préférences des règles dures et en vérifiant un petit cas dont tu connais la réponse.

Le retour arrière construit une affectation partielle par recherche en profondeur d'abord. Il choisit une variable, essaie une valeur et continue jusqu'à trouver une solution ou devoir annuler un choix. La recherche conserve les choix antérieurs utiles lorsqu'un choix ultérieur échoue.

Créer des branches sur les valeurs, une variable à la fois

Affecter A puis B produit la même affectation finale qu'affecter B puis A. Cette commutativité permet à un solveur de contraintes de choisir une variable à chaque niveau et de créer des branches sur ses valeurs. Autoriser tous les ordres de variables produirait $n!d^n$ feuilles pour seulement $d^n$ affectations complètes distinctes. Pour cinq variables ayant trois valeurs, cela représente 29 160 feuilles au lieu de 243.

La variable suivante peut dépendre des domaines courants. Ce qui compte est de choisir une seule variable suivante à un nœud ; la recherche n'a pas besoin de branches distinctes pour tous les ordres d'affectation possibles.

Suivre les étapes récursives

1. Si l'affectation est complète et cohérente, la renvoyer.
2. Choisir une variable non affectée.
3. Essayer chaque valeur du domaine qui est cohérente avec l'affectation courante.
4. Effectuer un appel récursif après avoir ajouté une valeur. Si l'appel échoue, supprimer cette affectation et essayer la valeur suivante.
5. Si aucune valeur ne convient, renvoyer un échec à l'appelant.

Le retour arrière simple teste une contrainte dès que toutes les variables de sa portée ont une valeur. Avec $A=1$ et B non affectée, $A<B$ ne dispose d'aucun couple complet à rejeter. Essayer ensuite $B=1$ échoue immédiatement. Attendre que toutes les variables soient affectées retarderait ce rejet facile.

Suivre une impasse

Utilise les règles des ateliers : $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Prends les variables dans l'ordre A, B, C, D, E et essaie les valeurs 1, 2, 3.

• Affecte $A=1$. Rejette $B=1$ et choisis $B=2$.
• Rejette $C=1$ à cause de A et $C=2$ à cause de B ; choisis $C=3$.
• Rejette $D=1$ à cause de A ; choisis $D=2$.
• E n'a aucune valeur autorisée : 1 est interdite, 2 est incompatible avec D et 3 avec C.

L'échec pour E rend le contrôle à D. Sa valeur suivante, 3, est incompatible avec C. C n'a pas de valeur suivante, le contrôle revient donc à B. Essayer $B=3$ conduit finalement à une autre impasse avec $A=1$. La recherche essaie alors $A=2$ et atteint $A=2,B=3,C=1,D=3,E=2$. Dans cet ordre, le retour arrière simple teste 32 valeurs candidates au total, y compris celles qui sont rejetées.

Ce que garantit la méthode

La vérification des contraintes et le stockage du modèle ont aussi un coût. La mémoire linéaire décrite concerne le chemin de recherche, tandis que la propagation peut aussi stocker les domaines et des informations de restauration.

Le retour arrière chronologique revient au choix le plus récent. Des variantes plus rapides améliorent quatre décisions distinctes : la variable suivante, l'ordre de ses valeurs, les conséquences déduites après un choix et le choix antérieur à reprendre après un échec. Ces améliorations réduisent le travail en pratique sans changer ce qui constitue une solution.

Un bon ordre peut révéler un échec près du sommet d'un arbre de recherche ou préserver des choix utiles pour la suite. L'ordonnancement des variables et celui des valeurs ont des objectifs différents : la direction qui semble la meilleure diffère donc entre les deux.

Choisir la variable la plus contrainte

L'heuristique du minimum de valeurs restantes sélectionne la variable non affectée qui possède actuellement le moins de valeurs autorisées. Elle est aussi appelée heuristique de la variable la plus contrainte ou du premier échec. Un domaine presque épuisé risque de révéler bientôt une contradiction. Si un domaine est vide, la branche échoue immédiatement.

Compte les valeurs courantes après réduction des domaines, et non les tailles initiales des domaines. Sans domaines stockés, un solveur doit déterminer quelles valeurs d'origine restent cohérentes avec l'affectation avant d'appliquer l'heuristique.

L'heuristique du degré départage les variables à égalité en choisissant celle qui a le plus de contraintes avec d'autres variables non affectées. Un tel choix influence davantage de décisions restantes. Les voisins déjà affectés ne comptent pas dans ce degré restant. Au départ sur la carte de l'Australie, les domaines de trois couleurs sont à égalité et les cinq voisins de SA lui donnent le degré le plus élevé.

Garder des possibilités lors du choix d'une valeur

L'heuristique de la valeur la moins contraignante essaie la valeur qui supprime le moins de valeurs des domaines voisins non affectés. Évaluer les valeurs candidates ajoute des calculs, mais peut éviter une branche infructueuse coûteuse.

Avec WA rouge et NT vert, SA ne peut être que bleue, tandis que Q peut être rouge ou bleue. Choisir Q bleu viderait le domaine de SA. Choisir Q rouge supprime rouge du domaine de NSW tout en conservant bleu pour SA. L'heuristique essaie donc Q rouge.

Chaque variable doit finir par recevoir une valeur, ce qui rend utile le test précoce d'une variable fragile. Une seule valeur est nécessaire pour compléter une première solution, ce qui favorise une valeur qui laisse de la place aux autres décisions.

Combiner l'ordonnancement et la vérification anticipée

Dans l'emploi du temps des ateliers, applique d'abord $E\mathrm{\ne }1$. E a deux valeurs ; A, B, C et D en ont chacune trois. L'heuristique du minimum de valeurs restantes choisit E. Essaie $E=2$ : la vérification anticipée supprime 2 des domaines de C et D.

C et D sont maintenant à égalité avec les domaines $\{1,3\}$. C a trois voisins non affectés, A, B et D ; D en a deux, A et C. L'heuristique du degré sélectionne C. Choisis $C=1$, ce qui laisse $D_D=\{3\}$ et $D_A=D_B=\{2,3\}$. L'heuristique du minimum de valeurs restantes choisit $D=3$, ce qui impose $A=2$ ; la règle de précédence donne alors $B=3$. Cinq affectations permettent de trouver la solution sans retour arrière. Avec un ordre fixe des variables, la vérification anticipée nécessite 12 affectations et atteint deux impasses.

L'ordonnancement préserve la complétude, car il change la séquence des choix sans écarter de branches autorisées. La recherche reste exponentielle dans le pire des cas. Lorsqu'on énumère toutes les solutions ou qu'on prouve l'absence de solution, toutes les valeurs pertinentes doivent finir par être explorées : l'avantage de la valeur la moins contraignante pour obtenir un succès précoce est donc réduit. Son principal intérêt est de trouver plus tôt une première solution.

Une impasse a souvent une cause plus limitée que l'ensemble de l'affectation courante. Le retour arrière non chronologique utilise cette cause pour décider où revenir, et l'apprentissage de contraintes mémorise un échec afin de ne pas avoir à le redécouvrir.

Trouver les choix qui ont causé l'échec

Sur la carte de l'Australie, prends l'ordre d'affectation Q, NSW, V, T, SA. Soit Q rouge, NSW vert, V bleu et T rouge. SA touche Q, NSW et V : les trois couleurs sont donc interdites. Son ensemble de conflit est $\{Q,NSW,V\}$ : ce sont les variables antérieures dont les choix excluent ses valeurs.

Le retour arrière chronologique essaierait de modifier T. La Tasmanie n'a aucune arête avec SA : changer sa couleur ne peut donc rétablir aucune possibilité pour SA. Le retour arrière non chronologique revient à V, le membre le plus récemment affecté de l'ensemble de conflit, et saute T.

Un ensemble de conflit contient des variables ; un nogood enregistre des affectations particulières. Cette distinction compte : une autre couleur pour V peut corriger l'échec, même si V reste voisine de SA.

Transmettre un conflit à travers les échecs antérieurs

Le retour arrière non chronologique simple utilise l'ensemble de conflit direct de l'échec courant. Le retour arrière non chronologique dirigé par les conflits transmet l'information à travers plusieurs niveaux en échec. Lorsqu'une variable X en échec revient à Y, Y absorbe l'ensemble de conflit de X après en avoir retiré Y. Si Y épuise ensuite toutes ses valeurs, son ensemble combiné indique une cause située plus loin dans les affectations antérieures.

Par exemple, utilise l'ordre WA, NSW, T, NT, Q, V, SA et commence avec WA rouge, NSW rouge, T rouge. WA et NSW ne sont pas voisines : cette affectation partielle est donc cohérente. Leurs choix retirent rouge des domaines de NT, Q et SA. Ces trois régions forment un triangle qui ne peut pas être colorié avec seulement du vert et du bleu.

Aucun choix pour T ne change ce triangle. Les informations de conflit peuvent remonter à travers les tentatives infructueuses et désigner WA et NSW comme la cause sous-jacente. La recherche revient à NSW, la plus récente de ces deux décisions, au lieu de passer du temps à recolorier T.

Apprendre la combinaison ayant échoué

Un solveur peut enregistrer $\{WA=\text{rouge},NSW=\text{rouge}\}$ comme nogood. Chaque fois que les deux choix se reproduisent, la même contradiction sur le triangle s'ensuit : la branche peut donc être rejetée immédiatement. Il serait incorrect d'interdire WA rouge à elle seule : WA peut être rouge dans des solutions valides où NSW a une autre couleur.

L'apprentissage ajoute une contrainte ou une combinaison interdite en cache. La condition apprise doit découler des contraintes d'origine ; un échec dû uniquement à l'atteinte d'une limite de temps ne fournit pas une telle justification logique. Un nogood utile conserve suffisamment d'affectations pour expliquer l'impossibilité sans inclure de choix sans rapport.

Combiner anticipation et retour sur les échecs

La vérification anticipée et la cohérence d'arc suppriment les valeurs sans support avant qu'un échec ne se produise en profondeur. Le retour arrière non chronologique analyse un échec après qu'il s'est produit. Le retour arrière non chronologique direct et simple n'ajoute aucune réduction à ce que détecte déjà la vérification anticipée, mais les méthodes dirigées par les conflits peuvent combiner les explications d'échecs plus profonds. L'apprentissage conserve ces explications pour les branches ultérieures.

La vérification anticipée examine ce qu'une nouvelle affectation élimine immédiatement pour ses voisins non affectés. Elle supprime les valeurs incompatibles avant que la recherche n'atteigne ces variables, ce qui rend certaines impasses visibles plusieurs niveaux plus tôt.

Réduire les domaines après une affectation

Après avoir choisi $X=x$, examine chaque variable Y non affectée qui partage une contrainte avec X. Supprime de $D_Y$ toute valeur incompatible avec ce choix. Un domaine vide signifie que la branche courante ne peut pas être complétée : reviens donc immédiatement en arrière.

Pour $X\mathrm{\ne }Y$, affecter $X=2$ supprime 2 du domaine de Y. Pour $X<Y$, affecter $X=2$ supprime toute valeur de Y inférieure ou égale à 2. C'est la relation elle-même qui détermine les valeurs supprimées ; la vérification anticipée ne se limite pas à supprimer les valeurs égales.

La réduction des domaines modifie ceux de la branche courante. Tiens une liste de restauration, souvent appelée pile de restauration, de chaque suppression causée par le choix. Lorsque ce choix est annulé, rétablis les valeurs qu'il a supprimées tout en conservant les restrictions dues aux choix antérieurs. Une autre implémentation consiste à copier les domaines à chaque niveau.

Suivre les domaines des ateliers

Utilise les créneaux 1 à 3 et les règles $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Applique la règle unaire pour obtenir $D_E=\{2,3\}$, puis utilise l'ordre fixe A, B, C, D, E.

1. $A=1$ laisse à B, C et D le domaine $\{2,3\}$.
2. $B=2$ laisse à C le domaine $\{3\}$.
3. $C=3$ laisse à D et E le domaine $\{2\}$ pour chacune.
4. $D=2$ supprime 2 du domaine de E, qui devient vide. Reviens en arrière.

Après restauration des domaines, essayer $B=3$ impose à C la valeur 2. D et E ne peuvent alors valoir que 3 ; affecter D vide donc à nouveau le domaine de E. La recherche doit modifier A. Avec $A=2$, elle peut atteindre $B=3,C=1,D=3,E=2$. Ce parcours essaie 12 valeurs, contre 32 valeurs candidates testées par le retour arrière simple dans le même ordre.

Reconnaître la limite d'une vérification à un pas

Après l'étape 3, D et E ont toutes deux 2 comme seule valeur et doivent être différentes. La vérification anticipée n'a toujours pas vérifié cette contrainte : ni D ni E ne vient d'être affectée. Elle ne détecte l'échec que lorsque D reçoit sa valeur.

C'est la limite principale de la vérification anticipée. Elle teste la variable affectée par rapport à ses voisins non affectés, sans propager plus loin la réduction du domaine d'un voisin. La cohérence d'arc peut suivre ces conséquences entre variables non affectées.

Utiliser les domaines maintenus à jour

L'heuristique du minimum de valeurs restantes peut maintenant sélectionner directement le plus petit domaine restant. Un domaine réduit à une seule valeur devient souvent le choix suivant ; un domaine vide signale un échec sans ajouter d'affectation. Maintenir les domaines à jour aide à la fois l'inférence et l'ordonnancement.

Pour au plus $n-1$ voisins et au plus $d$ valeurs par voisin, une passe de vérification anticipée utilise environ $O(nd)$ vérifications binaires, en supposant que le test de la relation prend un temps constant. Elle ne supprime que des valeurs incompatibles avec l'affectation courante : le retour arrière reste donc complet. Oublier de restaurer une valeur supprimée peut faire perdre une solution valide dans une branche ultérieure ; réduire le domaine d'une variable sans rapport peut avoir le même effet.

Une valeur a besoin d'une valeur compatible dans chaque domaine voisin. La cohérence d'arc rend cette exigence de support explicite et suit les effets des changements de domaine dans tout un problème de satisfaction de contraintes binaire.

Le support a une direction

La cohérence de nœud supprime d'abord les valeurs interdites par les règles unaires. Pour une contrainte binaire, l'arc orienté $X\to Y$ est cohérent lorsque chaque valeur de X possède au moins une valeur compatible dans Y. Cette valeur de Y est un support. Réviser l'arc consiste à supprimer les valeurs sans support à son origine, X.

Pour $A<B$ avec les deux domaines $\{1,2,3\}$, réviser $A\to B$ supprime 3 du domaine de A. Réviser $B\to A$ supprime 1 du domaine de B. Les domaines obtenus sont $D_A=\{1,2\}$ et $D_B=\{2,3\}$. Une valeur conservée peut utiliser un support différent pour chaque voisin ; ces supports ne forment pas nécessairement une solution commune.

Exécuter AC-3

AC-3 utilise une file d'arcs orientés :

1. Placer initialement tous les arcs dans la file.
2. Retirer $X\to Y$ et réviser le domaine de X à l'aide de celui de Y.
3. Si le domaine de X devient vide, s'arrêter avec un échec.
4. Si le domaine de X est réduit, ajouter $Z\to X$ pour chaque autre voisin Z de X, à l'exception de Y.
5. Continuer jusqu'à ce que la file soit vide.

Une suppression dans le domaine de X peut retirer un support à Z : la file doit donc contenir des arcs dirigés vers le domaine modifié. L'arc provenant de Y n'a pas besoin d'être immédiatement vérifié à nouveau : les valeurs supprimées de X ne servaient de support à aucune valeur de Y, puisqu'aucune n'était compatible avec Y au départ. Les domaines non vides obtenus à la fin sont indépendants de l'ordre de traitement ; des ordres différents peuvent conduire à un échec sur des domaines vides différents.

Propager une décision concernant les ateliers

Pour les règles des ateliers $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$, l'application initiale d'AC-3 supprime 3 du domaine de A et 1 de celui de B. Elle laisse à C et D le domaine $\{1,2,3\}$ et à E le domaine $\{2,3\}$.

Décide maintenant $C=1$. L'arc $A\to C$ supprime 1 du domaine de A, ce qui laisse $A=2$. Réviser B par rapport à A impose $B=3$. D diffère de C et de A, donc $D=3$. E diffère de D et ne peut pas valoir 1, donc $E=2$. Les réductions de domaines se sont propagées au-delà des voisins immédiats de la décision initiale.

Le maintien de la cohérence d'arc applique cette inférence après chaque décision de recherche. En partant de domaines cohérents d'arc, la restriction à $X=x$ nécessite une file contenant les arcs entrants provenant de ses voisins non affectés. Les valeurs supprimées des domaines doivent être restaurées lorsque la recherche annule la branche.

Interpréter le résultat et le coût

Un triangle dont les domaines sont {rouge, bleu} et dont les trois arêtes imposent des inégalités reste cohérent d'arc, mais n'a pas de solution. Chaque arête possède des supports séparément, mais les trois choix ne peuvent pas fonctionner ensemble.

Avec $c$ contraintes binaires et des domaines de taille maximale $d$, AC-3 prend un temps de $O(c{d}^3)$ : une révision d'arc vérifie jusqu'à $d^2$ couples, et chaque arc peut nécessiter jusqu'à $d$ révisions à mesure que son extrémité perd des valeurs. Le maintien de la cohérence d'arc coûte davantage par nœud de recherche que la vérification anticipée, souvent en échange d'un arbre de recherche beaucoup plus petit.

Des supports considérés séparément par paires peuvent masquer une contradiction au sein d'un groupe. Des cohérences plus fortes et des propagations spécialisées pour les contraintes globales examinent des combinaisons que la cohérence d'arc manque, tandis que les bornes numériques peuvent représenter de grands domaines par des intervalles utiles.

Étendre des affectations à une autre variable

La cohérence de chemin examine des triplets. Toute affectation cohérente à deux variables doit pouvoir être étendue à une troisième de manière cohérente avec les deux. Dans un triangle colorié en rouge ou en bleu, X rouge et Y bleu ne laissent aucune valeur pour Z. La cohérence de chemin supprime cette paire autorisée et finit par révéler l'absence de solution. Elle peut supprimer des tuples de relations et fait donc plus que supprimer des valeurs individuelles de domaines.

La k-cohérence exige que toute affectation cohérente à n'importe quelles $k-1$ variables puisse être étendue à n'importe quelle variable supplémentaire. Pour les problèmes binaires, la 1-cohérence correspond à la cohérence de nœud, la 2-cohérence à la cohérence d'arc et la 3-cohérence à la cohérence de chemin. La k-cohérence forte comprend tous les niveaux de 1 à k. Avec la n-cohérence forte sur n variables et des domaines non vides, toute affectation partielle cohérente peut être étendue jusqu'à devenir une solution, sans retour arrière. Établir cette propriété a un coût exponentiel en temps et en mémoire dans le pire des cas.

Dénombrer les valeurs dans Alldiff

Alldiff exige des valeurs distinctes pour toutes les variables de sa portée. Si un groupe de m variables ne dispose que de n valeurs possibles distinctes et que $m>n$, aucune affectation ne peut satisfaire la contrainte.

Pour trois cases de domaine $\{4,7\}$, les inégalités prises deux à deux sont cohérentes d'arc : chaque 4 a pour support 7 chez chaque voisin, et chaque 7 a pour support 4. Le dénombrement global échoue néanmoins, car trois valeurs différentes sont nécessaires et il n'en existe que deux.

Si deux cases ont toutes deux le domaine $\{4,7\}$, elles doivent prendre les valeurs 4 et 7. Ces valeurs peuvent être supprimées de toutes les autres cases de la ligne. Ce raisonnement par paire nue utilise un sous-ensemble de toute la portée d'Alldiff. Un propagateur global simple peut aussi traiter à plusieurs reprises les variables à une seule valeur, supprimer leurs valeurs ailleurs et vérifier s'il reste trop peu de valeurs distinctes. Des propagateurs plus puissants reconnaissent aussi les sous-ensembles contraints.

Resserrer les bornes numériques

La propagation des bornes stocke un domaine à l'aide de son minimum et de son maximum. La cohérence de bornes exige que chaque extrémité puisse être étendue en une affectation qui satisfait chaque contrainte concernée ; elle ne vérifie pas chaque valeur intérieure.

Pour deux bus transportant 100 personnes, soit $B_1\in [0;50]$ et $B_2\in [0;70]$, avec $B_1+B_2=100$. Le second bus transporte au plus 70 personnes, ce qui impose $B_1\ge 30$. Le premier en transporte au plus 50, ce qui impose $B_2\ge 50$. Les intervalles resserrés sont $[30;50]$ et $[50;70]$.

Pour Préparer, Analyser et Rédiger le rapport, qui prennent respectivement 20, 40 et 30 minutes dans cet ordre, une échéance de 120 minutes donne les débuts au plus tard 30, 50 et 90. Des débuts positifs ou nuls donnent les débuts au plus tôt 0, 20 et 60. La propagation vers l'avant et vers l'arrière donne ces intervalles avant qu'un horaire de début soit choisi.

Choisir une puissance d'inférence utile

Chaque case de Sudoku a 20 cases distinctes liées à elle : 8 dans sa ligne, 8 dans sa colonne et 4 autres dans sa région. Pour les 81 cases, cela donne $81\times 20\mathrm{/}2=810$ paires distinctes de cases devant être différentes. Les contraintes globales conservent les mêmes solutions que ces paires, mais peuvent révéler plus tôt les paires nues et les manques de valeurs. Une inférence plus forte coûte davantage par passe ; les solveurs pratiques mettent ce coût en balance avec la recherche économisée, souvent en combinant la cohérence d'arc avec une propagation spécialisée des contraintes globales et des bornes.

La recherche locale part d'une valeur pour chaque variable, même lorsque certaines contraintes ne sont pas respectées. L'heuristique des conflits minimaux répare cette affectation complète en donnant à une variable en conflit une valeur qui cause aussi peu de conflits que possible.

Choisir une réparation

1. Construire une affectation complète, aléatoirement ou de manière gloutonne.
2. Si aucune contrainte n'est violée, renvoyer la solution.
3. Choisir au hasard une variable intervenant dans une contrainte violée.
4. Évaluer chacune des valeurs de son domaine par rapport aux autres variables, qui restent fixes.
5. Choisir une valeur causant le moins de conflits, en départageant aléatoirement les ex æquo, et répéter jusqu'à réussir ou atteindre une limite d'étapes.

Une variable en conflit intervient dans au moins une contrainte violée. Ce n'est pas nécessairement la variable qui participe au plus grand nombre de violations. Le choix aléatoire parmi les variables en conflit et les valeurs ex æquo aide à éviter la répétition d'une séquence rigide.

Réparer un échiquier de 4 reines

Utilise une reine par colonne, avec les variables de ligne $Q_1,Q_2,Q_3,Q_4$. Une paire est en conflit si ses lignes sont égales ou si leur différence est égale à la différence de ses colonnes. Commence par $(2,4,2,3)$. Les colonnes 1 et 3 partagent la ligne 2 ; les reines des colonnes 3 et 4 s'attaquent en diagonale. Les variables en conflit sont Q1, Q3 et Q4.

Choisis Q3 et évalue les lignes tandis que Q1, Q2 et Q4 restent fixes :

La ligne 1 donne $(2,4,1,3)$, une solution. Si Q1 avait été choisie à la place, ses nombres de conflits pour les lignes 1 à 4 seraient 0, 1, 2 et 2. La déplacer à la ligne 1 donne $(1,4,2,3)$, où subsiste le conflit en diagonale entre Q3 et Q4. Une réparation localement optimale peut donc nécessiter d'autres réparations.

Compte les contraintes concernant la variable sélectionnée. Compter toutes les violations sur chaque échiquier obtenu donne le même ordre, car les contraintes sans rapport ajoutent une constante pour chaque valeur candidate. Cela demande simplement plus de travail. Utilise une définition cohérente des conflits lorsque tu compares les valeurs candidates.

Réparer un emploi du temps existant

Lorsqu'un formateur devient indisponible, l'emploi du temps courant est déjà une affectation complète. L'heuristique des conflits minimaux peut partir de là et déplacer des séances jusqu'à ce que les contraintes nouvelles et existantes soient respectées. Un petit changement nécessite souvent peu de réparations, même si un déplacement peut créer de nouveaux conflits ailleurs. S'il importe de conserver le plan initial, associe un coût explicite à la modification d'une affectation ; minimiser les violations ne minimise pas à lui seul les changements.

Des expériences avec une bonne affectation initiale ont nécessité relativement peu d'étapes de réparation, même pour un million de reines. Sur des échiquiers plus grands, chaque étape reste plus coûteuse. L'heuristique des conflits minimaux a aussi servi à la planification de Hubble : le temps nécessaire pour planifier une semaine d'observations aurait été réduit d'environ trois semaines à environ 10 minutes.

Interpréter le comportement de la recherche

Dans de nombreuses familles de problèmes de satisfaction de contraintes aléatoires, les problèmes passent de majoritairement solubles à majoritairement insolubles lorsque le rapport entre contraintes et variables augmente. Près de cette transition, déterminer comment les choix interagissent est souvent le plus difficile. Les problèmes peu contraints peuvent avoir de nombreuses solutions faciles à atteindre. Les problèmes très contraints et sans solution peuvent être rapidement rejetés par des solveurs complets fondés sur la propagation.

Atteindre la limite d'étapes de l'heuristique des conflits minimaux signifie qu'aucune solution n'a été trouvée lors de cette exécution. Le problème peut néanmoins être soluble. La force pratique de la méthode vient de réparations efficaces, notamment des déplacements entre valeurs de même score, bien que les solutions ne représentent qu'une infime partie de toutes les affectations possibles.

La recherche par réparation peut cesser de progresser alors que des conflits subsistent. Pour continuer, le solveur a besoin d'un moyen de traverser des états de même score ou de changer les déplacements qui paraissent utiles. Le résultat recherché compte aussi : une réparation réalisable rapide et une preuve d'absence de solution demandent des méthodes différentes.

Traverser un plateau

Un minimum local comporte des violations, mais aucun déplacement modifiant une seule variable ne réduit leur nombre. Un plateau est une région connexe d'affectations ayant le même score. Les déplacements qui ne font que réduire le score peuvent y rester bloqués ; un déplacement latéral change l'état sans réduire le score.

Pour le problème des 4 reines, $(1,4,2,3)$ comporte un conflit entre Q3 et Q4. Les autres reines restant fixes, les nombres de conflits de Q3 pour les lignes 1 à 4 sont 1, 1, 3 et 2 ; ceux de Q4 sont 2, 2, 1 et 2. Aucune des deux variables ne permet un déplacement qui améliore le score.

Déplacer Q3 à la ligne 1 donne $(1,4,1,3)$, toujours avec un conflit, cette fois entre Q1 et Q3 qui partagent une ligne. Dans ce nouvel état, les nombres de conflits de Q1 sont 1, 0, 3 et 1. Déplacer Q1 à la ligne 2 produit $(2,4,1,3)$ et élimine le conflit. Le déplacement latéral a changé les déplacements améliorants disponibles.

Poursuivre la recherche

Une liste tabou est une mémoire de courte durée. Elle décourage le retour immédiat à un état que l'on vient de quitter. Un redémarrage explore une autre région, tandis que le recuit peut traverser une région comportant davantage de conflits au cours de la même exécution.

Avec la pondération des contraintes, donne d'abord à chaque contrainte un poids de 1 et calcule le score d'un état comme la somme des poids de ses contraintes violées. Choisis une modification qui réduit ce score pondéré, puis augmente les poids des contraintes qui restent violées. Les échecs répétés deviennent plus coûteux, ce qui remodèle le paysage de recherche. Un score pondéré nul signifie toujours que chaque contrainte dure de poids positif est satisfaite.

Choisir le résultat dont tu as besoin

La recherche locale est incomplète : elle peut manquer une solution existante et une exécution finie infructueuse ne permet pas de conclure à l'absence de solution. Le retour arrière sur domaines finis avec propagation est complet : il finit par trouver une solution ou par épuiser toutes les façons de compléter l'affectation.

Utilise la recherche locale lorsqu'un grand problème peu contraint nécessite une affectation réalisable ou une réparation rapide. Le retour arrière avec l'heuristique du minimum de valeurs restantes et le maintien de la cohérence d'arc est un choix solide pour les énigmes fortement contraintes et chaque fois que la tâche exige de déterminer s'il n'y a pas de solution. Le temps d'exécution dépend néanmoins de l'instance ; ces choix de méthode reposent sur leurs garanties.

L'emploi du temps des ateliers possède l'unique solution $A=2,B=3,C=1,D=3,E=2$. Ajouter $C\mathrm{\ne }1$ l'élimine. L'heuristique des conflits minimaux peut essayer des réparations jusqu'à sa limite, mais seule une recherche complète qui épuise les cas restants établit que l'organisateur doit modifier une exigence, par exemple en ajoutant un créneau.

Un graphe de contraintes peut révéler des problèmes plus petits à l'intérieur d'un grand problème. Les composantes indépendantes peuvent être résolues séparément, et les composantes sans cycle admettent un algorithme particulièrement efficace, avec un parcours ascendant de réduction des domaines et un parcours descendant d'affectation.

Séparer les composantes non reliées

Une composante connexe est indépendante lorsqu'aucune contrainte ne relie ses variables à une autre composante. Résous chaque composante, puis combine une solution de chacune. Si une composante n'a pas de solution, le problème de satisfaction de contraintes complet n'en a pas non plus. Sur la carte de l'Australie, la Tasmanie est indépendante du continent.

Avec n variables réparties en groupes indépendants de taille c, trouver une affectation complète demande un travail de l'ordre de $O((n\mathrm{/}c)d^c)$ au lieu de $O(d^n)$. Pour 60 variables binaires réparties en trois groupes de 20, les recherches exhaustives séparées examinent au plus $3\times 2^{20}=3145728$ affectations au lieu d'environ $\mathrm{1,15}\times {10}^{18}$. Énumérer toutes les solutions combinées exigerait encore de lister les combinaisons ; l'économie décrite concerne la résolution des problèmes associés aux composantes.

Ordonner un arbre depuis sa racine

Un problème de satisfaction de contraintes binaire est arborescent lorsque son graphe de contraintes ne comporte aucun cycle. Un arbre connexe possède un chemin entre chaque paire de variables ; une forêt contient des arbres séparés. Applique d'abord les restrictions unaires. Choisis une racine quelconque et ordonne les variables de sorte que chaque parent apparaisse avant ses enfants.

La cohérence d'arc directionnelle dans cet ordre exige que chaque variable antérieure ait un support chez chaque voisin ultérieur. Dans un arbre, ces voisins ultérieurs sont ses enfants. Le support va du parent vers l'enfant, même si l'algorithme traite les enfants avant les parents.

Réduire les domaines en remontant, affecter en descendant

1. Parcourir l'ordre à l'envers, sauf la racine. Pour chaque enfant, réviser l'arc de son parent vers cet enfant. Supprimer les valeurs sans support du domaine du parent.
2. Si un domaine devient vide, signaler qu'il n'y a pas de solution.
3. Parcourir l'ordre dans le sens direct. Choisir une valeur restante quelconque pour la racine, puis donner à chaque enfant une valeur compatible avec celle de son parent affecté.

Les descendants de l'enfant ont déjà été traités lorsque son parent est révisé. Une valeur restante du parent possède donc un support chez chaque enfant, et chaque valeur d'enfant possède déjà un support plus bas. Les différentes branches issues des enfants n'ont aucune arête qui les relie : ces supports peuvent donc être choisis indépendamment. C'est pourquoi le parcours descendant ne nécessite aucun retour arrière.

Suivre l'arbre des ateliers

Fixe $C=1$ dans l'emploi du temps des ateliers et supprime 1 des domaines des autres ateliers. Le graphe restant est le chemin B-A-D-E, avec les domaines $\{2,3\}$ et les contraintes $A<B,A\mathrm{\ne }D,D\mathrm{\ne }E$.

Choisis A comme racine et l'ordre A, B, D, E. Le parcours ascendant révise $D\to E$, puis $A\to D$, sans changement. Enfin, $A\to B$ supprime 3 du domaine de A, car B n'a pas de valeur supérieure. L'affectation en descendant donne $A=2,B=3,D=3,E=2$. Rétablir $C=1$ donne l'emploi du temps complet.

Pour n variables dont les domaines ont une taille maximale d, le parcours ascendant révise $n-1$ arcs à un coût pouvant atteindre $O(d^2)$ chacun, soit un temps de $O(n{d}^2)$. Cette garantie dépend de l'absence de cycle. Un cycle peut relier des branches distinctes issues d'enfants et invalider l'indépendance qui rendait ces choix locaux fiables.

Un graphe comportant quelques cycles peut néanmoins être assez proche d'un arbre pour être résolu efficacement. Le conditionnement par ensemble coupe-cycles affecte d'abord certaines variables ; la décomposition arborescente regroupe les variables en parties qui se chevauchent. Les deux méthodes donnent à la coordination restante une structure arborescente.

Conditionner sur un ensemble coupe-cycles

Un ensemble coupe-cycles est un ensemble de variables dont la suppression laisse un arbre ou une forêt. Vérifie chaque cycle restant, et pas seulement le plus visible. Pour la carte de l'Australie, supprimer SA laisse le chemin WA-NT-Q-NSW-V ainsi que T isolée. Pour le graphe des ateliers, supprimer C laisse B-A-D-E.

Pour chaque affectation de l'ensemble coupe-cycles qui satisfait ses contraintes internes :

1. Supprimer les valeurs incompatibles des domaines restants.
2. Résoudre chaque arbre restant par réduction des domaines en remontant et affectation en descendant.
3. Si tous aboutissent, combiner leurs affectations avec les valeurs de l'ensemble coupe-cycles. Sinon, essayer une autre affectation de cet ensemble.

Dans le problème des ateliers, $C=1$ laisse un arbre qui possède une solution. Avec $C=2$, A et B doivent appartenir à $\{1,3\}$ et $A<B$ impose $A=1,B=3$. D doit être différente à la fois de A et de C, ce qui donne $D=3$. E ne peut pas valoir 1 et doit être différente de C et de D : il ne lui reste aucune valeur. Avec $C=3$, A et B doivent valoir 1 et 2 ; D doit alors valoir 2, ce qui ne laisse à nouveau aucune valeur pour E.

Pour un ensemble coupe-cycles de taille c, il y a au plus $d^c$ affectations, chacune suivie d'un problème arborescent de coût $O((n-c)d^2)$. Le total est $O(d^c(n-c)d^2)$. La méthode est utile si c est petit ; son coût reste exponentiel en c. Trouver un ensemble coupe-cycles minimal est NP-difficile, mais un ensemble valide non minimal donne tout de même une procédure correcte.

Relier des sacs qui se chevauchent

Une décomposition arborescente dispose en arbre des ensembles de variables appelés sacs. Elle doit respecter trois conditions :

• Chaque variable apparaît dans un sac.
• La portée de chaque contrainte tient dans au moins un sac.
• Les sacs contenant une même variable forment une partie connexe de l'arbre de sacs.

La troisième règle est la propriété d'intersection courante. Si X apparaît aux deux extrémités d'un chemin de sacs, elle doit apparaître tout au long de ce chemin. Sinon, des sacs éloignés pourraient choisir des valeurs incohérentes de X sans vérification de leur accord entre les deux.

Les affectations localement valides de chaque sac deviennent les valeurs d'une méga-variable. Les sacs voisins doivent s'accorder sur les variables partagées. L'arbre obtenu coordonne les solutions locales. Pour un triangle X-Y-Z-X auquel s'ajoute l'arête Z-W, les sacs $\{X,Y,Z\}$ et $\{Z,W\}$ couvrent toutes les arêtes et s'accordent sur Z.

La largeur arborescente de la décomposition est la taille de son plus grand sac moins 1. Celle d'un graphe est le minimum sur toutes ses décompositions valides. Pour une largeur w, la borne usuelle d'un problème de satisfaction de contraintes est $O(n{d}^{w+1})$. Une largeur bornée par une constante limite l'exposant.

Supprimer la symétrie de valeurs

Lorsque les noms des couleurs n'ont pas de signification particulière, permuter rouge, vert et bleu conserve la validité. Les six solutions du continent australien sont six renommages d'un même motif. Fixer l'ordre NT avant SA avant WA dans l'ordre des couleurs rouge, vert, bleu conserve un représentant. Une telle contrainte de bris de symétrie n'est valide que si le renommage préserve les règles d'origine. Une règle exigeant qu'une région particulière soit rouge donne à cette couleur un rôle particulier et modifie les permutations qui restent des symétries.