Une famille de règles d'élimination de variables pour les CSP binaires basées sur BTP
Abstract
L'´ etude des triangles cassés devient de plus en plus ambitieuse, par la résolution desprobì emes de satisfaction de contraintes (CSP) en temps polynomial d'un coté, et par la réduction de l'espace de recherchè a tra-vers l'´ elimination de variables et la fusion de valeurs de l'autre. Pour cela, plusieurs extensions de ce concept ontétéétudiées ontétéontétéétudiées dans le passé récent, tel que les triangles cassés duaux et les triangles légèrement cassés. Ces extensions ontétéontété introduites dans le but de maximiser soit le nombre de valeurs fusionnées et/ou le nombre d'ins-tances traitables capturées. Mais, aucune d'entre elles n'a préservé toutes les caractéristiques de BTP. Ici, nous introduisons une nouvelle version légère de BTP, que nous appelons m-fBTP (pour flexible broken-triangle property). m-fBTP permet la fusion de valeurs, l'´ elimination de variables et définit une plus grande classe polynomiale pour laquelle la cohérence d'arc est une pro-cédure de décision. Une version plus détaillée en langue anglaise a ´ eté publiéè a AAAI'17 [4].
Domains
Computer Science [cs]
Origin : Publisher files allowed on an open archive
Loading...