Programmation par contraintes
Présentation
La programmation par contraintes (PPC, ou CSP en anglais : Constraint Satisfaction Problem) fournit un cadre et des méthodes pour la résolution de problèmes définis sur des domaines finis (intervalles de nombres entiers, intervalles d'ensembles, par exemple).
Un problème comporte un certain nombre de variables, chacune ayant un domaine fini, et un certain nombre de contraintes.
Une contrainte implique une ou plusieurs variables, en définissant les combinaisons autorisées et celles qui sont interdites.
Trouver une solution à un problème de PPC consiste à affecter une valeur à chaque variable, de telle sorte que la totalité des contraintes soient satisfaites.
Lorsqu'une contrainte implique deux variables, on parle de contrainte binaire. Lorsqu'elle implique un nombre non fixé de variables, on parle de contrainte globale.
Exemple de problème : les N-Dames
Le problème des N-Dames consiste à placer N dames sur un échiquier NxN sans que l'une d'elles puisse en manger une autre (avec les règles des échecs : une dame peut « manger » toute pièce située sur sa ligne, sur sa colonne ou sur l'une de ses deux diagonales). Pour plus de détails sur ce problème, voir le Problème des huit dames.
Le problème peut être représenté avec N variables (Vi ∈ [1..N], i=1 .. N), représentant la position en colonne de la dame de la ligne i. En effet, comme deux dames ne peuvent pas être sur la même ligne, et qu'il y a autant de dames que de lignes, il y a exactement une et une seule dame par ligne.
Les contraintes imposées sur les variables Vi sont :
pour tout i ≠ j :
- Vi ≠ Vj (ne pas mettre deux dames sur la même colonne).
- Vi - i ≠ Vj - j (ne pas mettre deux dames sur la même diagonale NO-SE)
- Vi + i ≠ Vj + j (ne pas mettre deux dame sur la même diagonale NE-SO)
Méthodes de résolution
Le problème étant défini sur un produit d'ensembles de cardinal fini, il peut se résoudre par une énumération complète des valeurs des variables.
En pratique, on construit un arbre de recherche, dont les nœuds correspondent à une variable, et chaque branche à une réduction du domaine de la variable (cette réduction pouvant être une instanciation, c’est-à-dire la réduction du domaine à un singleton).
A chaque énumération (une feuille terminale de l'arbre de recherche), une vérification du respect de chaque contrainte doit être réalisé.
Au total, si chaque variable a un domaine de cardinal supérieur ou égal à C, alors l'énumération comporte au moins Cn étapes.
Cette méthode fait une utilisation trop pauvre des contraintes, ce qui conduit à explorer un trop grand nombre de combinaisons. Dans l'exemple des N-reines décrit ci-dessus, on s'aperçoit en effet que si à un nœud de l'arbre, une variable Vi a été instanciée à une valeur x, il est inutile d'explorer toute sous-branche où une variable Vj, j ≠ i serait instanciée à la même valeur x.
On peut ainsi limiter la taille de l'espace des recherche en faisant un usage efficace des capacités de déduction des contraintes : on appelle cette méthode la propagation de contraintes. Dans cette méthode, on peut voir le problème de PPC comme un réseau de variables qui communiquent entre elles par le seul intermédiaire des contraintes :
- lorsque le domaine d'une variable est réduit, on « réveille » les contraintes qui impliquent cette contrainte.
- lorsqu'une contrainte est réveillée, on examine s'il est possible de faire des déductions sur le domaine des autres variables de la contrainte.
Les domaines et les contraintes étant en nombres finis, ce processus converge toujours vers, soit une contradiction (une variable a un domaine vide, ce qui signifie que le problème n'a pas de solution), soit vers un point fixe (toutes les déductions possibles ayant été faites, il n'y a plus lieu de réduire plus avant les domaines des variables).
A l'issue de ce processus, trois cas de figure se présentent :
- Si une contradiction a été identifiée, il faut remonter d'un niveau dans l'arbre de recherche (backtracking).
- Si le domaine de chaque variable est un singleton, c'est qu'une solution a été trouvée. On peut alors s'arrêter si l'on cherche une solution, ou continuer le parcours de l'arbre d'énumération si l'on cherche toutes les solutions.
- Si le domaine d'une variable comporte plusieurs valeurs, il faut poursuivre l'énumération par une descente dans l'arbre de recherche.