REPOSITORY Doc's

Calcul des hypertrees décompositions pondérées

Show simple item record

dc.contributor.author Abbache, Farid
dc.contributor.author Dahmani, Abdennassar ; promoteur
dc.date.accessioned 2018-04-04T14:43:45Z
dc.date.available 2018-04-04T14:43:45Z
dc.date.issued 2010
dc.identifier.uri http://univ-bejaia.dz/dspace/123456789/9551
dc.description Option : Réseaux et Systèmes Distribués en_US
dc.description.abstract Les problèmes de satisfaction de contraintes (CSP) permettent de modéliser et de résoudre beaucoup de problèmes du monde réel. Cependant, ils sont connus pour être des problèmes NP complets. Leur complexité théorique est exponentielle en la taille du problème. Cependant, il est bien connu que les CSP ayant une structure acyclique en déterminant des sous classes parmi ces CSP cycliques traitables de manière polynomiale. Les techniques de décompositions structurelles permettent de déterminer des sous classes traitables en temps polynomial. Ces méthodes regroupent des variables ou des contraintes en des clusters de telle sorte que le CSP obtenu ait une structure d’arbre. Parmi ces méthode, la méthode la plus générale est la méthode dite « hypertree decomposition » où la qualité de la décomposition est basé uniquement sur la largeur de la décomposition hors qu’il y a d’autre paramètre qui peuvent guider à une meilleur décomposition, chose qui a permet à introduire une nouvelle méthode appelé « weighted hypertree decomposition ». Cependant, l’algorithme présenté pour le calcul de cette méthode présente une complexité exponentielle. Pour cela, nous proposant un nouvel algorithme « Tabu Search for Weighted Hypertree Décomposition » basé sur une méthode méta heuristique (recherche taboue). Cet algorithme est testé et évalué sur des différents problèmes connus dans la littérature et l’industrie en_US
dc.language.iso fr en_US
dc.publisher université Abderahmane Mira en_US
dc.subject CSP : Weighted hypertree decomposition : Méta-heuristiques en_US
dc.title Calcul des hypertrees décompositions pondérées en_US
dc.type Thesis en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account