Comprendre Cohérence d’arc
Un problème de contraintes est un ensemble de variables, un domaine pour chacune, et des contraintes restreignant les combinaisons. La recherche affecte des valeurs et les vérifie. La propagation fait autre chose : elle regarde les domaines et retire les valeurs qui ne peuvent participer à aucune solution, ce qui rétrécit le problème lui-même au lieu de l’explorer.
Un arc de X vers Y est cohérent quand chaque valeur restante de X possède au moins une valeur de Y satisfaisant la contrainte entre eux. Le rendre cohérent, c’est supprimer les valeurs non soutenues de X. La subtilité est que cela peut casser des arcs déjà cohérents, car une valeur d’une troisième variable Z pouvait s’appuyer sur une valeur de X désormais disparue. L’algorithme standard, AC-3, gère cela par une file : dès qu’un domaine rétrécit, tous les arcs pointant vers cette variable y reviennent.
Le gain est une conclusion qu’aucune vérification locale n’atteint. Si un domaine se vide, aucune solution n’existe sous ce point de la recherche, et la branche peut être abandonnée aussitôt. C’est pourquoi la propagation s’entrelace avec la recherche au lieu d’être exécutée une fois au début, et pourquoi la combinaison bat chacune des deux.
Ce qu’elle ne peut pas faire, c’est trancher le problème. La cohérence d’arc ne regarde que des paires, si bien qu’une contradiction n’émergeant que de trois variables ou plus lui survit. Un problème arc-cohérent peut rester insoluble, et des notions plus fortes et plus coûteuses - cohérence de chemin, k-cohérence - existent précisément pour voir plus loin à un prix plus élevé.
Comment calculer
D_i \leftarrow \{\, x \in D_i \;:\; \exists\, y \in D_j \text{ with } (x, y) \text{ allowed} \,\}
où
- D_i
- le domaine restant de la variable X_i
- (x, y) \text{ allowed}
- le couple satisfait la contrainte entre X_i et X_j
Exemple : Cohérence d’arc
Coloriez les sept régions de l’Australie avec trois couleurs de sorte que les voisines diffèrent, et fixez l’Australie-Occidentale au rouge et le Queensland au vert. Rien n’est violé : les deux ne sont pas adjacentes, et une vérification de contrainte ne trouve rien à redire.
La propagation voit plus loin. Le Territoire du Nord borde les deux : il perd le rouge et le vert et ne garde que le bleu ; l’Australie-Méridionale borde les deux également et ne garde que le bleu. Mais le Territoire du Nord et l’Australie-Méridionale se touchent, donc l’arc entre eux retire le bleu de l’Australie-Méridionale et vide son domaine. Il n’y a aucune solution sous ce point.
La force brute sur les 3^7 = 2 187 affectations le confirme : cette affectation partielle a exactement zéro complétion, sur les 18 que compte le problème. La vérification en avant, qui n’élague que les voisines d’une variable au moment où on l’affecte, laisse les deux domaines à une seule valeur, ne voit rien d’anormal et continue de chercher.
Questions fréquentes
La cohérence d’arc vaut-elle son coût ?
Le plus souvent oui, entrelacée avec la recherche. Elle est quadratique en le nombre d’arcs et la taille des domaines, ce qui est bon marché face à l’exponentielle qu’elle élague, et l’exemple ci-dessus est le cas courant : une impasse détectée avant d’en avoir exploré quoi que ce soit.
Si elle ne tranche pas le problème, à quoi sert-elle ?
Elle convertit une recherche sur les affectations en une recherche bien plus petite. Chaque valeur supprimée est un sous-arbre jamais visité, et un domaine vide est une preuve d’échec obtenue sans en visiter aucun.
En résumé
La cohérence d’arc supprime les valeurs qu’aucun voisin ne peut soutenir, en remettant les arcs en file à mesure que les domaines rétrécissent. Elle ne tranche pas un problème, mais elle peut prouver une branche sans espoir avant qu’une seule affectation en dessous n’ait été essayée, et c’est pourquoi elle s’exécute dans la recherche et non avant elle.