CM1 B

Question 1

Quels sont les 3 éléments qui caractérisent un réseau de contraintes ?

Answer 1

• Ensemble de variables
• Ensemble de domaines des variables (finis, ⊆ {Z})
• Ensemble de contraintes

Question 2

Qu’est-ce qu’une contrainte ?

Answer 2

Une fonction booléenne portant sur des variables

Question 3

Comment satisfaire une contrainte ?

Answer 3

Avec un tuple (un ensemble de valeurs) τ tel que C(τ) = 1

Question 4

Qu’est-ce qu’une instanciation ?

Answer 4

Une affectation de valeurs à une partie des variables

Question 5

Qu’est-ce qu’une instanciation valide ?

Answer 5

Une instanciation dans laquelle chaque valeur affectée à une variable appartient bien au domaine de cette dernière

Question 6

Qu’est-ce qu’une instanciation localement cohérente ?

Answer 6

Une instanciation valide qui ne viole aucune contrainte dont toutes les variables de la portée ont une affectation

Question 7

Qu’est-ce qu’une solution ?

Answer 7

Une instanciation localement cohérente qui a une affectation pour chacune des variables

Question 8

Quelle est la classe de complexité du problème de la résolution de CSP ?

Answer 8

NP-Complet

Question 9

Algorithme de Backtrack (entrée, sortie, algorithme)

Answer 9

• Entrée : problème N = (X, D, C), instanciation I
• Sortie : booléen
• BT(N, I) :
  
  • Si |I| = |X|, renvoyer vrai
  • Choisir x_i une variable non-affectée (!∈ I)
  • Pour v_i ∈ Dom(x_i)
    
    • Si I ∪ {x_i, v_i} est localement cohérente :
      - Si BT(N, I ∪ {x_i, v_i}), renvoyer vrai
  • Renvoyer faux

Question 10

Comment fonctionne l’algorithme du Backtrack ?

Answer 10

Tant que toutes les variables ne sont pas instanciées, l’instanciation est élargie avec une valeur pour une variable :
- Si elle est localement cohérente, on continue
- Sinon, on essaye une autre valeur et s’il n’y en a pas, on revient sur l’affectation précédente

Question 11

Complexité (temporelle et spatiale) du backtrack

Answer 11

Soit n = |X|, m = |C|, d = max_i=1..n(D(X_i)),
- Temporelle : O(m×dⁿ)
- Spatiale : linéaire

Question 12

Défauts de l’algorithme de Backtrack

Answer 12

• Il redécouvre plusieurs fois les mêmes échecs
• Il est limité aux petits problèmes par sa complexité

Question 13

Qu’est-ce qu’un tuple support ?

Answer 13

Un tuple de la contrainte c est support si toutes ses valeurs sont bien dans les domaines des variables concernées et s’il satisfait c

Question 14

Qu’est-ce qu’une valeur viable ?

Answer 14

Une valeur d’un domaine qui est contenue dans au moins un tuple support de chaque contrainte qui porte sur la valeur à laquelle elle est associée

Question 15

Qu’est-ce qu’un domaine arc-cohérent ?

Answer 15

Un domaine dont toutes les valeurs sont viables

Question 16

Comment obtenir la fermeture arc-cohérente d’un domaine ?

Answer 16

En supprimant au fur et à mesure toutes ses valeurs non-viables

Question 17

Quels liens existent entre l’arc-cohénce et la cohénce ?

Answer 17

• Sol(X, D, C) = Sol(X, D_AC, C)
• Cohérent ⇒ Arc-cohérent
• Arc-cohérent !⇒ Cohérent

Question 18

Algorithme AC3 (entrée, sortie, algorithme)

Answer 18

• Entrée : Problème N = (X, D, C)
• Sortie : booléen
• Algorithme :
  
  • Q ← {(x_i, c) | c ∈ C, x_i ∈ portée(c)}
  • Tant que Q != ∅ :
    
    • Supprimer (x_i, c) de Q
    • Si Revise(x_i, c) :
      
      • Si D(x_i) = ∅, renvoyer faux
      • Sinon, Q ← Q ∪ {(x_j, c’) | c’ ∈ C, {x_i, x_j} ⊆ portée(c’), i != j}
  • Renvoyer vrai

Question 19

Algorithme Revise3 (entrée, sortie, algorithme)

Answer 19

• Entrée : Variable x_i, Contrainte c_ij
• Sortie : booléen
• Algorithme :
  
  • Change ← Faux
  • Pour chaque valeur v_i de D(x_i) :
    
    • v_j ← first(D(x_j))
    • Tant que v_j != nil et ¬c_ij (v_i, v_j ) :
      
      • v_j ← next(v_j, D(x_j))
    • Si v_j = nil
      
      • D(x_i) ← D(x_i) \ {x_i}
      • Change ← Vrai
  • Renvoyer Change

Question 20

Algorithme Revise3 (entrée, sortie, algorithme)

Answer 20

• Entrée : Variable x_i, Contrainte c_ij
• Sortie : booléen
• Algorithme :
  
  • Change ← Faux
  • Pour chaque valeur v_i de D(x_i) :
    
    • v_j ← first(D(x_j))
    • Tant que v_j != nil et ¬c_ij (v_i, v_j ) :
      
      • v_j ← next(v_j, D(x_j))
    • Si v_j = nil
      
      • D(x_i) ← D(x_i) \ {x_i}
      • Change ← Vrai
  • Renvoyer Change

Question 21

Quels sont les défauts d’AC3 ?

Answer 21

Il refait des calculs qu’il a déjà faitn il n’est donc pas optimal

Question 22

Qu’est-ce qui change dans l’algorithme d’AC2001 par rapport à celui d’AC3 ?

Answer 22

AC2001 apporte la notion de “last” qui enregistre le dernier tuple support vérifié pour chaque couple (x_i, c), de façon à reprendre à cet endroit là pour tester seulement les couples qui n’ont jamais été testé

Question 23

Algorithme Revise2001 (entrée, sortie, algorithme)

Answer 23

• Entrée : Variable x_i, Contrainte c_ij
• Sortie : booléen
• Algorithme :
  
  • Change ← Faux
  • Pour chaque valeur v_i de D(x_i) telle que Last(x_i, v_i, x_j) !∈ D(x_j) :
    
    • v_j ← next(Last(x_i, v_i, x_j), D(x_j))
    • Tant que v_j != nil et ¬c_ij (v_i, v_j ) :
      
      • v_j ← next(v_j, D(x_j))
    • Si v_j != nil
      
      • Last(x_i, v_i, x_j) !∈ D(x_j) ← v_j
    • Sinon :
      
      • D(x_i) ← D(x_i) - {x_i}
      • Change ← Vrai
  • Renvoyer Change

Question 24

Complexité (temporelle et spatiale) d’AC3

Answer 24

Soit n = |X|, m = |C|, d = max_i=1..n(D(X_i)),
- Temporelle : O(m×d³) pour des contraintes binaires
- Spatiale : O(m)

Question 25

Complexité (temporelle et spatiale) d’AC2001

Answer 25

Soit n = |X|, m = |C|, d = max_i=1..n(D(X_i)),
- Temporelle : O(m×d²) pour des contraintes binaires
- Spatiale : O(m×d)

Question 26

Qu’est-ce qu’un “removal event” ?

Answer 26

Une fonction qui réduit les domaines d’une certaine façon

Question 27

Quels sont les principaux “removal event ?

Answer 27

• remValue qui supprime une valeur
• incMin qui supprime la plus petite valeur
• decMax qui supprime la plus grande valeur
• instantiate qui réduit le domaine à un singleton

Question 28

Quand est-ce qu’un réseau est arc-cohérent ?

Answer 28

Quand pour tout ensemble de variables de taille k-1, pour toute instanciation localement consistante sur cet ensemble, toute variable n’y appartenant pas a au moins une valeur de son domaine qui permet d’étendre l’instanciation sans perdre la cohénrence

Question 29

Comment la 2-cohérence (2C) et l’arc-cohérence (AC) sont elles comparables ?

Answer 29

Pour les réseaux binaires :
- Si le réseau est normalisé, 2C = AC
- Sinon, 2C est plus fort que AC
Pour les réseaux non-binaires :
- Si le réseau est normalisé, 2C est moins fort que AC
- Sinon, 2C et AC sont incomparables

Question 30

Qu’est-ce qu’une réseau fortement k-cohérent ?

Answer 30

Un réseau j-cohérent pour j=1..k

Question 31

Complexité (temporelle et spatiale) du calcul de la k-cohérence forte

Answer 31

Soit n = |X|, m = |C|, d = max_i=1..n(D(X_i)),
- Temporelle : O(n^k+1×d^k+1)
- Spatiale : O(n^k-1×d^k-1)
ou
- Temporelle : O(n^k×d^k)
- Spatiale : O(n^k×d^k)

Question 32

Qu’est-ce qu’une instanciation globalement cohérente ?

Answer 32

Une instanciation qui peut être étendue à une solution

Question 33

Qu’est-ce qu’un réseau globalement cohérent ?

Answer 33

Un réseau dans lequel toute instanciation localement cohérente est globalement cohérente

Question 34

Quel lien peut-on établir entre la cohérence globale et le Backtrack ?

Answer 34

Il n’y a jamais besoin de backtracker dans un réseau globalement cohérent

Question 35

Quel lien peut-on établir entre la cohérence globale et la k-cohérence forte ?

Answer 35

Un réseau est globalement cohérent si et seulement s’il est fortement n-cohérent avec n = |X|