CM2 B Flashcards
De quelle manière est-il possible d’accélérer une recherche Backtrack ?
- En raisonnant sur les échecs (look-back)
- En propageant les contraintes (look-ahead/forward)
- En ordonnant les variables
- En ordonnant les valeurs des domaines
Quel est le principe du look-back ?
Il s’agit de foncer sur les éches et de réflechir après
Quelles sont les deux façons de raisonner sur les échecs (look-back) ?
- Avoir un meilleur point de retour que celui par défaut : backjumping
- Ne pas refaire les mêmes erreurs : nogood learning
Comment fonctionne le backjumping ?
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
Comment fonctionne le nogood learning ?
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
Quel est le principe du look-ahead/forward ?
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
Quelles sont les deux façons de faire du look-ahead/forward ?
Dans les deux cas il s’agit de propagation de contraintes :
- Forward-Checking (FC)
- Maintaining Arc Consistency (MAC)
Algorihtme du Forward-Checking (entrée, sortie, algorithme)
- Entrée : Réseau N, Instanciation I
- Sortie : Booléen
- FC(N, I) :
- Si |I| = |X|, renvoyer Vrai
- Choisir xi !∈ I
- Pour chaque valeur vi de D(xi) :
- D(xi) ← {vi}
- Supprimer tous les couples (xj, vj) inchohérents avec I ← I ∪ (xi, vi)
- Si aucun domaine n’a été vidé :
- Si FC(N, I ∪ (xi, vi)), renvoyer Vrai
- Restaurer toutes les valeurs supprimées à cause du choix (xi, vi)
- Renvoyer Faux
Comment fonctionne l’algorithme du Forward-Checking ?
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
Algorihtme MAC (entrée, sortie, algorithme)
- 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 xi dont le domaine n’est pas un singleton
- Choisir une valeur vi de D(xi)
- Renvoyer MAC(N+{xi = vi}) ∨ MAC(N+{xi != vi})
Comment fonctionne l’algorithme MAC ?
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
Comment évaluer l’efficacité des algorithmes de résolution ?
L’analyse asymptotique n’est pas adaptée donc on utilise des benchmarks de problèmes binaires aléatoires
Quels sont les paramètres des benchmarks de problèmes binaires aléatoires ?
- le nombre de variables n
- la taille des domaines d
- la proportion de contraintes p1 → |C| = p1 × n(n-1)/2
- l’étanchéité des contraintes p2 → |tuples interdits| = p2 × d2
Conjecture de Cheeseman, Kanesfky et Taylor
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
Qu’est-ce que la transition de phase ?
C’est le moment où, en faisant varier les paramètres, les problèmes passent de tous satisfiables à tous insatisfiables
Quel est l’intérêt de la transition de phase ?
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
Qu’est-ce que les EHPS ?
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
Qu’est-ce que l’existence des EHPS implique ?
Il vaut mieux considérer la médiane que la moyenne pour comparer les algorithmes de résolution
Quelle conclusion sur les algorithmes de résolution a-t-on pu tirer de l’étude de la phase de transition ?
MAC est plus efficace que FC
Pourquoi ordonner les variables pour le backtrack ?
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
Quels critères peuvent être choisis pour ordonner les variables ?
- 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
Pourquoi choisir le degré maximum pour ordonner les variables ?
Pour réduire la profondeur de l’arbre, ce qui est plus efficace sur les réseaux dispersés
Pourquoi choisir le domaine minimum pour ordonner les variables ?
Pour réduir la largeur de l’arbre, ce qui est plus efficace sur les réseaux denses
Pourquoi ordonner les valeurs pour le backtrack ?
Pour choisir d’abord les valeurs les plus prometteuses possibles
Quand est-ce qu’il est possible d’ordonner les valeurs pour le backtrack ?
Quand des experts du domaine concerné peuvent fournir un ordre des valeurs les plus prometteuses
Qu’est-ce que la Singleton Arc-Cohérence ?
C’est l’arc-cohérence calculée pour chaque valeur en y réduisant le domaine de la variable
