Hybridation de prouveurs CSP et apprentissage
Résumé
À ce jour, l'algorithme MGAC-$dom/wdeg$, qui maintient l'Arc Consistance Généralisée pendant la recherche d'une solution, est considéré comme étant l'approche générique la plus efficace pour résoudre des Problèmes de Satisfaction de Contraintes (CSP) difficiles et de grande taille. Dans cet article, nous proposons une approche hybride capable de combiner des recherches systématiques et locales indépendantes tout en transférant des informations utiles d'un algorithme à l'autre. Nous proposons différentes interactions, et en particulier l'apprentissage de nogoods, la pondération de contraintes ainsi que des affectations gloutonnes. Sur un grand nombre d'instances de CSP structurés, les résultats expérimentaux montrent que notre approche donne des résultats intéressants en comparaison avec MGAC-$dom/wdeg$.
Domaines
Langage de programmation [cs.PL]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...