CM2 B

Question 1

De quelle manière est-il possible d’accélérer une recherche Backtrack ?

Answer 1

• En raisonnant sur les échecs (look-back)
• En propageant les contraintes (look-ahead/forward)
• En ordonnant les variables
• En ordonnant les valeurs des domaines

Question 2

Quel est le principe du look-back ?

Answer 2

Il s’agit de foncer sur les éches et de réflechir après

Question 3

Quelles sont les deux façons de raisonner sur les échecs (look-back) ?

Answer 3

• Avoir un meilleur point de retour que celui par défaut : backjumping
• Ne pas refaire les mêmes erreurs : nogood learning

Question 4

Comment fonctionne le backjumping ?

Answer 4

Lors du backtrack, lorsqu’un domaine est vidé, on remonte à la plus basse variable responsable de l’échec plutôt que de toujours remonter juste au niveau précédent

Question 5

Comment fonctionne le nogood learning ?

Answer 5

Lors du backtrack, lorsqu’un domaine est vidé, on garde en mémoire la raison de l’échec en l’ajoutant aux contraintes pour ne pas retomber sur le même échec une deuxième fois

Question 6

Quel est le principe du look-ahead/forward ?

Answer 6

Il s’agit de réfléchir d’abord ou ne pas descendre, c’est à dire d’enlever des branches qui conduisent à un échec avant de les explorer

Question 7

Quelles sont les deux façons de faire du look-ahead/forward ?

Answer 7

Dans les deux cas il s’agit de propagation de contraintes :
- Forward-Checking (FC)
- Maintaining Arc Consistency (MAC)

Question 8

Algorihtme du Forward-Checking (entrée, sortie, algorithme)

Answer 8

• Entrée : Réseau N, Instanciation I
• Sortie : Booléen
• FC(N, I) :
  
  • Si |I| = |X|, renvoyer Vrai
  • Choisir x_i !∈ I
  • Pour chaque valeur v_i de D(x_i) :
    
    • D(x_i) ← {v_i}
    • Supprimer tous les couples (x_j, v_j) inchohérents avec I ← I ∪ (x_i, v_i)
    • Si aucun domaine n’a été vidé :
      
      • Si FC(N, I ∪ (x_i, v_i)), renvoyer Vrai
    • Restaurer toutes les valeurs supprimées à cause du choix (x_i, v_i)
  • Renvoyer Faux

Question 9

Comment fonctionne l’algorithme du Forward-Checking ?

Answer 9

On construit une instanciation au fur et à mesure en prenant une variable non-instanciée et en construisant une branche pour chaque valeur de son domaine dans laquelle on supprime les valeurs incompatibles de tous les autres domaines, puis on coupe la branche si on obtient un domaine vide

Question 10

Algorihtme MAC (entrée, sortie, algorithme)

Answer 10

• Entrée : Réseau N
• Sortie : Booléen
• MAC(N) :
  
  • N = AC(N)
  • Si un domaine est vide, renvoyer Faux
  • Si tous les domaines sont réduits à des singletons et si c’est une solution, renvoyer Vrai
  • Choisir une variable x_i dont le domaine n’est pas un singleton
  • Choisir une valeur v_i de D(x_i)
  • Renvoyer MAC(N+{x_i = v_i}) ∨ MAC(N+{x_i != v_i})

Question 11

Comment fonctionne l’algorithme MAC ?

Answer 11

On commence par calculer l’arc-cohérence, et si cela ne donne pas déjà une réponse, on prend une variable qui a plusieurs valeurs possibles et on branche sur l’une e ces valeurs avec = ou != puis on recommence

Question 12

Comment évaluer l’efficacité des algorithmes de résolution ?

Answer 12

L’analyse asymptotique n’est pas adaptée donc on utilise des benchmarks de problèmes binaires aléatoires

Question 13

Quels sont les paramètres des benchmarks de problèmes binaires aléatoires ?

Answer 13

• le nombre de variables n
• la taille des domaines d
• la proportion de contraintes p₁ → |C| = p₁ × n(n-1)/2
• l’étanchéité des contraintes p₂ → |tuples interdits| = p₂ × d²

Question 14

Conjecture de Cheeseman, Kanesfky et Taylor

Answer 14

Pour évaluer une méthoe de résolution :
- Prendre un problème NPC et identifier les k paramètres qui le caractérisent
- Fixer k-1 paramètres et varier le k-ième
- Pour chaque valeur du paramètre k, générer 100 instances

Question 15

Qu’est-ce que la transition de phase ?

Answer 15

C’est le moment où, en faisant varier les paramètres, les problèmes passent de tous satisfiables à tous insatisfiables

Question 16

Quel est l’intérêt de la transition de phase ?

Answer 16

C’est là que se trouvent tous les problèmes vraiment difficiles à résoudre et sur lesquels on voudrait comparer les algorithmes de résolution

Question 17

Qu’est-ce que les EHPS ?

Answer 17

Les Exceptionnaly Hard Problems sont des problèmes censés être faciles à résoure mais sur lesquels un des algorithmes peut rester bloqué à cause d’une erreur dans l’abre

Question 18

Qu’est-ce que l’existence des EHPS implique ?

Answer 18

Il vaut mieux considérer la médiane que la moyenne pour comparer les algorithmes de résolution

Question 19

Quelle conclusion sur les algorithmes de résolution a-t-on pu tirer de l’étude de la phase de transition ?

Answer 19

MAC est plus efficace que FC

Question 20

Pourquoi ordonner les variables pour le backtrack ?

Answer 20

Pour traiter les variables les “plus dures” en priorité afin de détecter les échecs le plus tôt possible et de réduire la profondeur de l’arbre

Question 21

Quels critères peuvent être choisis pour ordonner les variables ?

Answer 21

• Le degré maximum (statique)
• Le domaine minimum (dynamique)
• Le ratio minimum dom/deg
• Le ration minimum dom/(w×deg) avec w le nombre d’échecs

Question 22

Pourquoi choisir le degré maximum pour ordonner les variables ?

Answer 22

Pour réduire la profondeur de l’arbre, ce qui est plus efficace sur les réseaux dispersés

Question 23

Pourquoi choisir le domaine minimum pour ordonner les variables ?

Answer 23

Pour réduir la largeur de l’arbre, ce qui est plus efficace sur les réseaux denses

Question 24

Pourquoi ordonner les valeurs pour le backtrack ?

Answer 24

Pour choisir d’abord les valeurs les plus prometteuses possibles

Question 25

Quand est-ce qu’il est possible d’ordonner les valeurs pour le backtrack ?

Answer 25

Quand des experts du domaine concerné peuvent fournir un ordre des valeurs les plus prometteuses

Question 26

Qu’est-ce que la Singleton Arc-Cohérence ?

Answer 26

C’est l’arc-cohérence calculée pour chaque valeur en y réduisant le domaine de la variable