De FC à MAC : un algorithme paramétrable pour la résolution des CSP - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

De FC à MAC : un algorithme paramétrable pour la résolution des CSP

Assef Chmeiss
Lakhdar Sais

Résumé

Beaucoup d'algorithmes de résolution de Problèmes de Satisfaction de Contraintes ont été proposés ces dernières années. Parmi ces algorithmes nous pouvons mentionner les deux les plus populaires et les plus étudiés : le Forward-Checking (FC) et Maintaining Arc-Consistency (MAC). Dans ce papier, nous étudions ces deux algorithmes et nous réévaluons leurs performances sur des problèmes générés aléatoirement. Précisément, nous montrons expérimentalement que FC est meilleur que MAC sur des CSP difficiles dont le graphe de contraintes est très dense et la dureté des contraintes est faible. En revanche, MAC se montre plus performant que FC sur des problèmes difficiles avec un graphe de contraintes peu dense et une dureté élevée. Ces résultats montrent que le maintien de l'Arc-consistance pendant la recherche peut être une perte de temps. Ensuite, Nous proposons une approche générique qui permet, pendant la recherche, un maintien partiel et paramétrable de la consistance locale.
Fichier principal
Vignette du fichier
22.pdf (305.63 Ko) Télécharger le fichier

Dates et versions

inria-00000063 , version 1 (26-05-2005)

Identifiants

  • HAL Id : inria-00000063 , version 1

Citer

Assef Chmeiss, Lakhdar Sais. De FC à MAC : un algorithme paramétrable pour la résolution des CSP. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, pp.267-276. ⟨inria-00000063⟩
305 Consultations
148 Téléchargements

Partager

Gmail Facebook X LinkedIn More