Cohérence d'arc virtuelle dynamique
Résumé
Virtual Arc Consistency (VAC) is a recent local consistency for processing Cost Function Networks (or Weighted Constraint Networks) that exploits a simple but powerful connection with classical Constraint Networks. It has allowed to close hard frequency assignment benchmarks and is capable of directly solving networks of submodular functions. The algorithm enforcing VAC is an iterative algorithm that solves a sequence of classical Constraint Networks. In this work, we show that Dynamic Arc Consistency algorithms can be suitably injected in the virtual arc consistency iterative algorithm, providing noticeable speedups.
La cohérence d'arc virtuelle (VAC) est une cohérence récente pour les réseaux de fonctions de coût (ou réseaux de contraintes pondérées). VAC exploite une relation simple mais puissante avec les réseaux de contraintes classiques. VAC a permis de clore des problèmes d'af-fectation de fréquences difficiles, et est capable de ré-soudre directement les réseaux de fonctions de coût sous-modulaires. L'algorithme pourétablir VAC est un algo-rithme itératif qui résout une séquence de réseaux de contraintes classiques. Dans cet article, nous montrons que les techniques utilisées dans les algorithmes de cohé-rence d'arc dynamique peuventêtre injectées dans l'al-gorithme itératif de cohérence d'arc virtuelle. Cette intégration donne une accélération importante.
Domaines
Intelligence artificielle [cs.AI]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...