HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Thursday, May 26, 2005 - 9:52:25 AM
Last modification on : Wednesday, October 20, 2021 - 9:58:16 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

Metrics

Record views

282

Files downloads

142