Le processus itératif d'application des contraintes dans un réseau de contraintes pour réduire les domaines des variables en éliminant les valeurs qui ne peuvent participer à aucune solution, souvent mis en œuvre via la consistance d'arcs, le contrôle avancé ou des algorithmes de consistance généralisée.

Principe

Utiliser les relations locales de contrainte pour inférer et supprimer les valeurs impossibles, réduisant ainsi les domaines et révélant des affectations forcées ; l'application répétée resserre le problème et réduit le branching combinatoire.

Démonstration

Dans un CSP binaire avec la contrainte X ≠ Y et domaines X = {1,2}, Y = {2,3}, la propagation supprime 2 du domaine de X si Y est fixé à 2, et la consistance d'arcs peut supprimer itérativement des valeurs jusqu'à stabilisation.

Mauvaise application

Une propagation globale trop agressive sans considération du coût peut gaspiller du temps pour peu d'élagage (fort overhead), et une propagation naïve ignorant les dépendances entre contraintes peut provoquer des réductions de domaine incorrectes si elle est mal implémentée.

Conséquence

Une propagation de contraintes correctement appliquée réduit substantiellement la recherche en éliminant tôt des branches infaisables, transformant souvent une recherche inextricable en une recherche praticable lorsqu'elle est combinée à des heuristiques.

Inversion

L'inverse consiste à effectuer la recherche sans aucune propagation (énumération purement exhaustive des affectations), ce qui reste correct mais est typiquement beaucoup moins efficace en raison de l'absence d'élagage précoce.

Limite

S'applique aux problèmes discrets de satisfaction de contraintes et à la recherche combinatoire ; les domaines continus exigent d'autres techniques de propagation (arithmétique d'intervalles, relaxation de contraintes) et certaines contraintes globales nécessitent des propagateurs spécialisés.

Tension sémantique

Tension entre propagation locale (consistance d'arcs) et notions de consistance globale : une consistance plus forte donne un meilleur élagage mais à coût computationnel supérieur ; le compromis dépend du problème.

Synthèse

La propagation de contraintes est l'application disciplinée de déductions locales pour élaguer progressivement les domaines de variables, équilibrant pouvoir d'élagage et coût computationnel afin de rendre la recherche combinatoire viable en pratique.