Une famille de règles d'élimination de variables pour les CSP binaires basées sur BTP - Aix-Marseille Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Une famille de règles d'élimination de variables pour les CSP binaires basées sur BTP

Résumé

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].
Fichier principal
Vignette du fichier
JFPC-2017-ElMouelhi-1.pdf (278.13 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01785215 , version 1 (07-05-2018)

Identifiants

  • HAL Id : hal-01785215 , version 1

Citer

Achref El Mouelhi. Une famille de règles d'élimination de variables pour les CSP binaires basées sur BTP. Treizièmes Francophones de Programmation par Contraintes, JFPC 2017, Jun 2017, Montreuil-sur-Mer, France. ⟨hal-01785215⟩
64 Consultations
37 Téléchargements

Partager

Gmail Facebook X LinkedIn More