Une approche gloutonne pour établir la singleton consistance d'arc - 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

Une approche gloutonne pour établir la singleton consistance d'arc

Résumé

Dans cet article, nous proposons une nouvelle approche pour établir la singleton consistance d'arc (SAC) d'un réseau de contraintes. Tandis que le principe des algorithmes SAC existants consiste à réaliser un parcours en largeur d'abord jusqu'à une profondeur égale à 1, le principe des deux algorithmes que nous introduisons consiste à réaliser plusieurs exécutions d'une recherche gloutonne (telle que la consistance d'arc soit maintenue à chaque étape). Il s'agit d'une illustration originale d'inférence (i.e. établir la singleton consistance d'arc) par la recherche. Utiliser une approche gloutonne permet de bénéficier de l'incrémentalité de la consistance d'arc, d'apprendre des informations pertinentes à partir des conflits et de, potentiellement, trouver des solutions pendant le processus d'inférence. De plus, les complexités temporelle et spatiale sont tout à fait compétitives.
Fichier principal
Vignette du fichier
8.pdf (158.88 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00000049 , version 1 (24-05-2005)

Identifiants

  • HAL Id : inria-00000049 , version 1

Citer

Stephane Cardon, Christophe Lecoutre. Une approche gloutonne pour établir la singleton consistance d'arc. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, pp.99-108. ⟨inria-00000049⟩
69 Consultations
101 Téléchargements

Partager

Gmail Facebook X LinkedIn More