Strengthening Neighbourhood Substitutability
Résumé
Domain reduction is an essential tool for solving the constraint satisfaction problem (CSP). In the binary CSP, neighbourhood substitution consists in eliminating a value if there exists another value which can be substituted for it in each constraint. We show that the notion of neighbourhood substitution can be strengthened in two distinct ways without increasing time complexity. We also show the theoretical result that, unlike neighbourhood substitution, finding an optimal sequence of these new operations is NP-hard.
La réduction de domaines est un outil essentiel dans la résoluion de problèmes de satisfaction de contraintes (CSP). Pour les CSP binaires, la substitution de voisinage constisteàéliminer une valeur s'il existe une autre valeur qui peut la remplacer dans chaque contrainte. Nous démontrons qu'il est possible de rendre plus forte la notion de substitution de voi-sinage de deux façons distinctes sans augmenter la complexité temporelle. Nous démontrons que contrai-rementà ce qui se passe pour la substitution de voisinage, trouver la séquence optimale de ces nouvelles opérations est NP-difficile.
Domaines
Intelligence artificielle [cs.AI]| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...