Intégration partielle de la consistance de chemin dans la résolution des CSP

National audienceDe nombreuses propriétés de consistance locale ont été exploitées dans la résolution des problèmes de satisfaction de contraintes (CSP). L'objectif est de réduire l'espace de recherche et par conséquent améliorer les méthodes de résolution. La consistance d'arc a été la forme de consistance locale la plus étudiée. Il a été montré que le maintien de la consistance d'arc durant la recherche est très utile pour la résolution des CSP. L'utilisation de formes plus fortes de consistance locale (comme la consistance de chemin) est encore limitée car elles nécessitent la gestion de structures de données complexes. Dans ce papier, nous proposons une technique permettant l'exploitation, dans la phase de prétraitement, d'une forme partielle de consistance d'arc et de chemin. Cette consistance est basée sur la notion d'intervalles de supports. Nous montrons aussi que, grâce à cette forme de consistance, il est possible de réduire l'espace de recherche pendant la résolution