HD DBT : Hypertree Décomposition pour la résolution des problèmes de satisfaction de contraintes basée sur un Dual Backtracking - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2010

HD DBT : Hypertree Décomposition pour la résolution des problèmes de satisfaction de contraintes basée sur un Dual Backtracking

Abstract

L'hypertree decomposition généralisée est l'approche la plus générale connue dans la littérature pour identifier des sous classes traitables de problèmes de satisfaction de contraintes (CSPs) n-aires représentés à l'aide d'hypergraphes. Seulement, quoi que sa complexité théorique est bornée par la largeur de la décomposition, la méthode proposée pour la résolution du CSP donné sous forme d'hypertree n'est pas efficace en pratique. Dans ce papier, nous proposons la méthode HD DBT (pour résolution des CSP par un algorithme de type BT sur les tuples guidé par un ordre statique induit par une Hypertree Décomposition) comme une nouvelle approche de résolution des CSPs préalablement décomposés en hypertree généralisée. Nous avons implémenté et expérimenté cette approche. Les résultats de comparaison par rapport à la méthode de résolution des CSPs par hypertree decomposition, connue dans la littérature sont encourageants.
Fichier principal
Vignette du fichier
amroun.pdf (226.83 Ko) Télécharger le fichier
Origin : Explicit agreement for this submission
Loading...

Dates and versions

inria-00519487 , version 1 (20-09-2010)

Identifiers

  • HAL Id : inria-00519487 , version 1

Cite

Kamal Amroun, Zineb Habbas. HD DBT : Hypertree Décomposition pour la résolution des problèmes de satisfaction de contraintes basée sur un Dual Backtracking. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.5-12. ⟨inria-00519487⟩
78 View
89 Download

Share

Gmail Facebook X LinkedIn More