Programmation par contraintes - 2ème CM

Table des matières

Différences entre réseaux
Extensions des CSP
- Traitement des intervalles de valeurs
Les CSP dynamiques
Représentation des règles
- Réseau de contraintes et prise en compte du temps (séquencement)
Exercice - Classico DS apparemment
Génération d'un graphe

On définit la notion d'Hyper-contraintes.

Une contrainte C sur les variables x1, ..., xn de domaines D1, ..., Dn est dite hyper-consistante d'arc par rapport à i ∈ {1, ..., n} si et seulement si :

∀ a ∈ Di
∃ b₁ ∈ D₁, ... ∃ b_i-1 ∈ D_i-1, ..., ∃ b_n ∈ D_n

tel que C(b₁, ..., b_i-1, ...., b_n)

C est dite hyper-consistante d'arc si et seulement si elle est hyper-consistance d'arc par rapport à tout X_i ∈ {1, ..., n}

Au lieu d'hyper-consistance d'arc on parle également de consistance d'arc généralisé (GAC).

Différences entre réseaux

Réseau de contrainte complet : un réseau de contraintes est dit complet si chacune de ses variables est connectée à toutes les autres variables (il y a une contrainte entre chaque paire de variables).

Tous les réseaux de contraintes ne sont pas complets et il est important dans ces cas de mesurer la densité du réseau.

Densité : la densité d'un réseau est le ratio entre le nombre total de ses arcs et le nombre d'arcs du réseau comportants les mêmes variables mais étant complet.

Difficulté d'un problème - Tightness : la difficulté d'un problème de satisfaction de contraintes avec les variables X₁, ..., X_n est le ratio entre le nombre de solutions et le cardinal du produit cartésien : D₁ × D₂ × ... × D_n

Exemple :

Le problème des N reines est complet (densité = 1/1 = 1)
Le problème des 4 reines possède 2 solutions
Sa difficulté vaut 2 / (4 × 4 × 4 × 4) = 1/128 = 0,0078125
Le problème des 8 reines possède 92 solutions
Sa difficulté vaut 92/ (8 × 8 × 8 × 8 × 8 × 8 × 8 × 8) = 92/16777216 = 0,00000549

Il est important de faire la distinction entre la difficulté d'un problème et la difficulté à résoudre le problème.

On peut avoir :

Des problèmes difficiles mais facile à résoudre
ou des problèmes faciles mais difficiles à résoudre

La difficulté à résoudre un problème de satisfaction de contraintes dépend à la fois de la densité du graphe et de sa difficulté.

Pour tester les algorithmes de résolution de CSP il est habituel d'utiliser des générateurs de problèmes aléatoires. Les paramètres de ces générateurs sont non seulement le nombre d'arcs mais également la densité du graphe et la difficulté des contraintes.

Les études dans ce domaine de la génération de CSP montrent que les CSP présentent souvent une phrase de transition qui sépare les problèmes qui sont trivialement satisfaits de ceux qui sont trivialement insatisfaits.

Extensions des CSP

Les CSP traitent des classes de problèmes (booléens, réels, domaines finis, etc.)
comment traiter judicieusement l'ajout / le retrait de contraintes : les CSP dynamiques

Traitement des intervalles de valeurs

Problème de domaines finis :

Les valeurs sont traitées de manière individuelle notamment lors des filtrages
Ils ne permettent pas de manipuler les imprécisions

C - B = [80, 100] - [50, 90] = [80 - 90, 100 - 50] = [10, 50]
A ← A ∩ C - B = [30, 70] ∩ [10, 50] = [30, 50]

                                      +---------------+
{30, 31, ..., 70} = [30, 70]    A --- |               |
                                      |  Additionneur |
{50, 51, ..., 90} = [50, 90]    B --- |   C = A + B   |
                                      |               | --- C {1, 2, ..., 100}
                                      +---------------+

A = [a₁, a₂]
B = [b₁, b₂]

A + B = [a₁, a₂] + [b₁, b₂]
      = [a₁ + b₁, a₂ + b₂]

A - B = [a₁, a₂] - [b₁, b₂]
      = [a₁, a₂] + [-b₂, -b₁]
      = [a₁ - b₂, a₂ - b₁]

A * B = [a₁, a₂] * [b₁, b₂]

L'arithmétique peut être étendu aux fonctions classiques :

√ x, sin(x), cos(x), etc.

En travaillant sur les intervalles sur lesquels les fonctions sont monotones dans ce cas on peut être amené à traiter des ensembles d'intervalles.

Problème 1 : multiplication des intervalles
Problème 2 : on perd des propriétés de l'arithmétique classique

A chaque relation est associé un ensemble de règles de maintient de la cohérence, ces règles vérifient les 4 propriétés suivantes:

Contractantes : après application des règles de maintenance, l'intervalle de chaque variable est inclus ou égal à l'interval précédent.
Correcte : après application des règles de maintenance, tout valeur d'une instanciation satisfaisant la contrainte.
Monotone : l'inclusion des intervalles est préservée par l'application des règles.
Idempotente : une seule application des règles de maintenance suffit à calculer les nouveaux intervalles des variables. Une autre application ne modifie plus ces intervalles.

Conséquences : la mise en forme d'une expression va influencer la qualité du filtrage !

Exemple : on considère le polynôme : P(X) = X⁴ - 10X³ + 35X² - 50X + 24 avec X = [0, 4].

On a P(0) = 24, P(1) = 0, P(2) = 0, P(3) = 0, P(4) = 0.

Evaluation directe :

P([0, 4]) = [0, 4]⁴ - 10 × [0, 4] ³ + 35 × [0, 4]² - 50 × [0, 4] + 24
= [0, 256] - 10 × [0, 64] + 35 × [0, 16] - 50 × [0, 4] + 24
= [-816, 840]

Schéma de Hörner :

P(X) = X⁴ - 10X³ + 35X² - 50X + 24
= 24 + X(-50 + X(35 + X(-10 + X)))

P([0, 4]) = [-256, 384]

Expansion des racines :

P(X) = X⁴ - 10X³ + 35X² - 50X + 24
= (X - 1) × (X - 2) × (X - 3) × (X - 4)

P([0, 4]) = [-24, 72]

Les CSP dynamiques

Problématique :

Il n'est pas rare qu'un CSP qui représente le modèle d'un problème doive être modifier pour différentes raisons :

Corriger des contraintes
Ajouter des contraintes oubliées
Ajouter des contraintes redondantes pour améliorer la propagation locale
Retirer des contraintes
Modifier des domaines
etc.

Si le CSP n'a pas de solution, l'utilisateur peut-il se satisfaire d'une réponse telle que "no solution" ? Ne peut-on pas détermine des contraintes à relaxer pour que le CSP ait des solutions ?

Objectif

Proposer des moyens d'ajouter, retirer ou modifier un CSP sans remettre en cause tout le travail effectué.

Définition : Un CSP dynamique P (noté CnCSP) est une suite de CSP (statiques) P₀, ... P_i, P_i+1, ... tels que chaque Pi diffère de Pi+1 par l'ajout ou le retrait d'une contrainte

On note Pi = (C, dom, C(i)) représente l'ensemble des contraintes présentes dans le CSP Pi. Au départ, on a : P0 = (X, dom, {})

Remarque 1 : lors de l'ajout d'une contrainte à un CSP, l'ensemble des solutions est au plus conservé : généralement il est réduit. On parle de restriction.

Conséquence : si on désigne par Φ(Pi) le CSP obtenu après l'application d'un filtrage Φ sur le CSP Pi, les CSP Φ(Pi) et Pi ont les mêmes solutions. De même, les CSP Φ(Pi+1) et Pi+1 ont les mêmes solutions (puisque le filtrage préserve les solutions). Si C(i+1) = C(i) ∪ {α} on a sol(Pi+1) ⊆ sol(Pi).

Remarque 2 : Si C(i+1) = C(i) ∪ {α} alors : Φ(Pi+1) = Φ(Pi ∪ {α}) = Φ(Φ(Pi) ∪ {α})

Conséquence : lors de l'ajout d'une contrainte à un CSP il est inutile de "refaire tout le travail de filtrage". On peut partir du filtrage réalisé juste avant l'ajout. Ceci se fait très facilement.

Par contre pour le retrait d'une contrainte α, il faut restituer aux différents domaines des variables toutes les valeurs qui avaient été supprimées lors de l’ajout de α.

Représentation des règles

X1	X2	X3
V	V	V
V	F	V
F	V	V
F	F	F

R1 : si (X3 = faux) alors (X1 = faux, X2 = faux)
R2 : si (X1 = vrai) alors (X3 = vrai)
R3 : si (X2 = vrai) alors (X3 = vrai)
R4 : si (X3 = vrai) et (X2 = faux) alors (X1 = vrai)
R5 : si (X3 = vrai) et (X1 = faux) alors (X2 = vrai)
R5 : si (X1 = faux) et (X2 = vrai) alors (X3 = vrai)

Réseau de contraintes et prise en compte du temps (séquencement)

Problème il y a des relations :

Entre les valeurs et les variables
Entre les dépendances temporelles et ces valeurs

Exercice - Classico DS apparemment

Le but ici est d'évaluer le circuit. On donne les valeurs d'entrée et celles de sortie. Il faut dans un premier temps vérifier que les valeurs de sortie sont les mêmes que celles données en utilisant les valeurs d'entrée.

Si ce n'est pas le cas, il faut proposer une modification à réaliser au niveau du circuit pour que l'on obtienne les mêmes valeurs de sortie que celles données.

Différence entre NOR et NEGOR :

NEGOR = Negation puis le OR
NOR = OR et négation du résultat

Entrée
IN 1	1
IN 2	0
IN 3	1
IN 4	1
IN 5	1
IN 6	0
IN 7	1
IN 8	0

Sortie	Valeur
OUT 1	1
OUT 2	1
OUT 3	0

Ici on voit que OUT2 n'a pas la valeur qui a été donné. On peut donc proposer une modification pour que sa valeur soit correcte comme transformer le XOR2 (ou exclusif) en OR classique.

Génération d'un graphe

On rappelle qu'un CSP est définit par :

CSP = (X, D, C)

Lors de la génération d'un graphe, les paramètres variables suivant sont à prendre en compte :

Nombre de variables
Taille des domaines
Nombre de contraintes
Dureté des contraintes (nombre de couples de valeurs autorisés)

M2