Une étude des supports résiduels pour la consistance d'arc

Résumé : Pour un algorithme établissant la consistance d'arc (AC), un support résiduel, ou résidu, est un support qui a été trouvé et enregistré lors d'une exécution de la procédure qui détermine si une valeur est supportée par une contrainte. Le point important est qu'un résidu n'offre pas la garantie de représenter un minorant du plus petit support courant de la valeur en question. Dans cet article, nous étudions l'impact théorique d'exploiter des résidus au niveau de l'algorithme élémentaire AC3. Tout d'abord, nous prouvons que AC3r(m) (i.e. AC3 exploitant des résidus) est optimal pour une dureté de contrainte faible ou élevée. Ensuite, nous montrons que MAC2001 présente, par rapport à MAC3r(m), un sur-coût en O(μed) par branche de l'arbre binaire construit par MAC, avec μ représentant le nombre de réfutations de la branche, e le nombre de contraintes et d la taille du plus grand domaine. L'une des conséquences est que, MAC3r(m) admet une complexité temporelle (dans le pire des cas) meilleure que MAC2001 pour une branche impliquant μ réfutations lorsque μ > d2 ou lorsque μ > d et que la dureté de chaque contrainte est soit faible soit élevée. Nos résultats expérimentaux montrent clairement que le fait d'exploiter des résidus permet d'améliorer l'efficacité des algorithmes MAC et SAC embarquant des algorithmes AC à gros grain.
Type de document :
Communication dans un congrès
Journées Francophones de Programmation par Contraintes, 2006, Nîmes - Ecole des Mines d'Alès, 2006
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00085771
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 08:56:06
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:07:51

Fichier

Identifiants

  • HAL Id : inria-00085771, version 1

Collections

Citation

Christophe Lecoutre, Fred Hemery. Une étude des supports résiduels pour la consistance d'arc. Journées Francophones de Programmation par Contraintes, 2006, Nîmes - Ecole des Mines d'Alès, 2006. 〈inria-00085771〉

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

139