Programmation par contraintes
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
Retrouvez l'ancien article sur la PPC en cliquant sur ce lien

Présentation

La programmation par contraintes (PPC, ou Constraint Programming (CP) en anglais) consiste à programmer avec des relations appelées 'contraintes'. Un problème comporte un certain nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de variables, chacune ayant un domaine, et un certain nombre de contraintes. Une contrainte implique une ou plusieurs variables, et restreint les valeurs que peuvent prendre simultanément ces variables. Trouver une solution à un problème de PPC consiste à décrire l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut...) des affectations autorisées de chaque variable (En mathématiques et en logique, une variable est représentée par un symbole. Elle est utilisée pour marquer un rôle dans une formule, un prédicat ou un algorithme. En statistiques, une variable...), de telle sorte que la totalité des contraintes soient satisfaites.

  • Définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.)
  • Historique
  • Tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) ce que vous devez savoir sur la PPC en moins de 5 mn

Programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel, cf. VHDL).) par Contraintes sur les domaines finis

Description du problème de satisfaction de contraintes

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. 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.

Trouver une solution à un problème de PPC consiste à affecter une valeur à chaque variable, de telle sorte que la totalité des contraintes soient satisfaites. Il serait possible d'énumérer toutes les possibilités et vérifier si elles violent ou non les contraintes. Cependant cela serait extrèmement lourd en calcul. La partie la plus importante est appelée "filtrage", elle consiste à déduire à partir des contraintes les valeurs impossibles. Lorsqu'une variable ne possède plus qu'un candidat celle-ci est instanciée. Cependant le filtrage ne permet pas toujours d'instancier toutes les variables. Il faut alors faire des choix arbitraire puis recommencer le filtrage. Si ce choix mène à une contradiction (Une contradiction existe lorsque deux affirmations, idées, ou actions s'excluent mutuellement.), on annule le choix arbitraire par backtracking.

Algorithmes de recherche : en profondeur, en largeur (La largeur d’un objet représente sa dimension perpendiculaire à sa longueur, soit la mesure la plus étroite de sa face. En géométrie plane, la largeur est la plus petite des deux mesures d'un rectangle,...), heuristiques, LDS

Consistances locales

La consistance locale consiste à vérifier que certaines variables ne violent pas les contraintes liées à cette variable. On ignore alors les autres variables et contraintes. Cela permet de filtrer certaines valeurs impossibles, cependant il sera impossible d'avoir un filtrage parfait, puisqu'on ignore alors certaines contraintes.

Consistance de nœud

Elle consiste à ne considérer qu'une seule variable. Cependant les contraintes portent généralement sur au moins deux variables. Cette consistence n'apporte donc que peu d'informations.

Consistance d'arc

Aussi appelée Arc Consistency (AC), il s'agit de la méthode la plus employée. Elle s'applique dans le cas de contraintes binaires (i.e. impliquant deux variables). Une contrainte binaire peut être représentée par un arc reliant les deux variables impliquées, d'où l'emploi du mot arc. Une contrainte satisfait la consistance d'arc si chaque valeur de chaque variable appartient à une solution de la contrainte. On établit la consistance d'arc en supprimant les valeurs qui ne satisfont pas cette propriété.

Par exemple, soient V1 ∈ [1,2,3] et V2 ∈ [1,3] avec la contrainte V1 = V2. On a alors les solutions 1-1 et 3-3. La valeur 2 de V1 n'appartenant pas à une solution, on la supprime du domaine.

Consistance d'hyperarc

Aussi appelée Hyperarc Consistency (HAC), c'est une généralisation (La généralisation est un procédé qui consiste à abstraire un ensemble de concepts ou d'objets en négligeant les détails de façon à ce qu'ils puissent...) de la consistance d'arc pour les contraintes non binaires. Son nom vient du fait que les variables impliquées peuvent être reliées par un hyperarc (nom d'un arc dans un hypergraphe). Elle a aussi été appelée consistance d'arc généralisée. Le principe est le même que pour les contraintes binaires : une contrainte est HAC si et seulement si chaque valeur de chaque variable appartient à une solution de la contrainte. On établit la consistance d'hyperarc en supprimant toutes les valeurs qui ne satisfont pas cette propriété.

Par exemple, la contrainte Alldiff impliquent que les variables sur lesquelles elle est définie prennent des valeurs deux à deux différentes. On sait établir efficacement la consistance d'hyperarc pour cette contrainte.

k-consistance

Elle consiste à considérer k variables, et de tester tous les k-uplets de valeurs possibles afin de tester s'ils ne violent pas les contraintes. Plus k est grand, plus le filtrage sera efficace. Cependant, du fait du grand nombre de combinaisons à tester, cela reste souvent trop lourd. La 3-consistence donne de bons résultats, cependant du fait de la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en...) de son implémentation (Le mot implantation peut avoir plusieurs significations :), elle n'est que très rarement présente dans des solveurs de contraintes.

La 2-consistence est en fait la consistance d'arc. Si un problème contient n variables, alors la n-consistance consisterait à tester l'ensemble des possibilités.

Chemin

Consistance de bornes

Lorsque les domaines des variables sont trop grands (plusieurs milliers d'élements), l'énumération de toutes les possibilités devient alors trop lourd. On ne travaille alors plus que sur les bornes inférieures et supérieures du domaine. Cela fonctionne très bien avec certaines contraintes comme <, > ou =.

Algorithmes de consistance locale

AC1, AC2, AC3, AC4, AC5, AC6, AC7, AC8, AC2001

Exemples

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 (On appelle diagonale d'un polygone tout segment reliant deux sommets non consécutifs (non reliés par un côté). Un polygone à n côtés possède diagonales.) NO-SE)
  • Vi + i ≠ Vj + j (ne pas mettre deux dame sur la même diagonale NE-SO)

send+more=money

Soit l'équation :

 
 send 
 +more 
 ----- 
 money 
 

Le but est d'associer un chiffre (Un chiffre est un symbole utilisé pour représenter les nombres.) à chaque lettre tel que la somme soit vérifie. Les variables sont donc s,e,n,d,m,o,r et y toutes étant des entiers dans [0,9]. On pose la contrainte s \times 1000 + e \times 100 + n \times 10  + d + m \times 1000 + o \times 100 + r \times 10 + e = m \times 10000 + o \times 1000 + n \times 100 + e \times 10 + y.

Sudoku

Le sudoku consiste à remplir une grille ( Un grille-pain est un petit appareil électroménager. Une grille écran est un élément du tube de télévision. Une grille d'arrêt est un élément du tube...) 9x9 avec des chiffres de 1 à 9 tel que chaque chiffre n'apparaisse qu'une seul fois dans chaque ligne, colonne, et sous-boîte de taille 3x3.

Les variables sont donc naturellement des entiers dans [1,9]. On utilise ensuite la contrainte globale AllDifferent qui est bien connue sur chaque ligne, colonne, et sous-boîte.

Autres

reconnaissance de scènes 3D, raisonnement temporel qualitatif

Applications

La PPC se révèle très efficace pour des problèmes d'emploi du temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) et d'affectation (En algorithmique (informatique), une affectation est une opération qui permet d'attribuer une valeur à une variable.), de ce fait elle est principalement utilisée dans le cadre de problèmes de logistique (La logistique est l'activité qui a pour objet de gérer les flux physiques d'une organisation, mettant ainsi à disposition des ressources correspondant...) complexes.

Autres domaines de contraintes

  • termes
  • booléens
  • réels
  • intervalles
  • ensembles
  • chaînes

Solveurs de contraintes

  • Etude théorique
  • Architecture (L’architecture peut se définir comme l’art de bâtir des édifices.) d'un solveur
  • Langages d'expression des propagateurs: indexicaux, CHRs
  • liens vers solveurs libres et commerciaux

Extensions

  • contraintes valuées
  • étude et détection des symétries
  • techniques de décomposition (En biologie, la décomposition est le processus par lequel des corps organisés, qu'ils soient d'origine animale ou végétale dès...) et classes de problèmes "traitables"
  • métaheuristiques
  • transition de phase (En physique, une transition de phase est une transformation du système étudié provoquée par la variation d'un paramètre extérieur particulier (température, champ...)
Page générée en 0.072 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique