Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadata

https://hal.inria.fr/inria-00000063
Contributor : Christine Solnon <>
Submitted on : Thursday, May 26, 2005 - 9:52:25 AM
Last modification on : Thursday, January 11, 2018 - 6:19:28 AM
Long-term archiving on: : Thursday, April 1, 2010 - 9:32:41 PM

Files

Identifiers

  • HAL Id : inria-00000063, version 1

Collections

Citation

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⟩

Share