(LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale
➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạmNội dung chi tiết: (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale
(LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale
IflInstitut do la Francophonie pour rinformatiquoInstitut de la Francophoniepour rinformatiqueUniversité catholique de LouvainAppariement multivoque d (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale de graphes par la recherche localeMémoire de fin d’etudesRealise par :NGUYEN Thi Hong HiepSous la direction de :Prof. Yves DevilleDepartement d’lngenierie InformatiqueUniversité catholique de LouvainLouvain - ỉa - Neuve, le Ỉ5 Novembre 2009RemerciementsJe tiens à remercier particuliẻrement mon promo (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale teur, Yves Deville, qui ma dirigé mon travail de stage de tin d’etude. Sa direction scientifique. ses judicieux conseils. ses pertinents commentates e(LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale
t ses encouragements m’ont aide à aller jusqu’au bout de ce travail.Je remercie aussi Pham Quang Dung pour ses propositions et son aide avec lesquels IflInstitut do la Francophonie pour rinformatiquoInstitut de la Francophoniepour rinformatiqueUniversité catholique de LouvainAppariement multivoque d (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale ils scientifiques sans lesquelles ce travail n’aurait pas pu aboutir.Je tiens à remercier les membres du groupe Be-cool (Belgian Constraint Group) du Departement d'Ingenierie Informatique pom leur accueil. leur soutien et leur bonne humeur.Ma reconnaissance s’adresse aussi aux professeurs de riFI (I (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale nstitut de la Francophonie pour rinformatique) qui m’ont donné des connaissances et des guides utiles pour mon mémoire et qui m’ont aide à suivre la f(LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale
ormation de master à L IFIEn fin, j’exprime ma gratitude à ma famille pour leur soutien, leurs encouragements et leur aide qui m’a pennis de réaliser IflInstitut do la Francophonie pour rinformatiquoInstitut de la Francophoniepour rinformatiqueUniversité catholique de LouvainAppariement multivoque d (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale e de similarile cnlrc des objcls jouc un role clc. I.orsquc les objels sonl prcscnlcs sous forme de graphes. ce problème se transforme en mesure de similarite entre des graphes. En fait, ã cause de la difference ail niveau de modélisation des objets, chaque sommet dim graphe correspond peut-être à p (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale lusieurs sommets de rautre graphe et inversement. Le matching multivoque de graphic pent résoudre cc problcmc cn pcrmellanl de mcltre en correspondanc(LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale
c un somnict d'un graphe avcc plusieurs sommets de I’aulre. En ulilisant line mesure de similarité pour formuler ce problème en problẽme d’optimisatioIflInstitut do la Francophonie pour rinformatiquoInstitut de la Francophoniepour rinformatiqueUniversité catholique de LouvainAppariement multivoque d (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale rme en line recherche d’un appariement maximisant la fonction objectif.Malheureusement, lappanement multivoque de graphes est un problème NP-complet impossible d’etre résolu par un algorithme polynomial. Done, la recherche locale est line approche alternative inléressanie car permettant d’obtenir li (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale ne solution approchée en temps polynomial. Elie ne garantit pas loujours le résullal globalement optimal mais donne des solutions acceptable*. En expl(LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale
oranl respace de recherche de Voisin cn voisin. les algorithmes de recherche locale permettent d’ameliorer petit-ã-petit la qualité de solution et dirIflInstitut do la Francophonie pour rinformatiquoInstitut de la Francophoniepour rinformatiqueUniversité catholique de LouvainAppariement multivoque d (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale abouc el la recherche laboue reactive oil la function object!f esl de maximiscr la similarilc cnlrc les graphes. Ccs trois algorilhmcs sonl implcmcnlccs en COMET - un environnement développẽ pour la recherche locale et pour la programmation par contraintes. Dans la section résultats. nous comparons (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale la qualite de ces trois algoritlimes. Nous évaluons aussi lefficacite de la recherche locale pour le problcme d’appariement multivoquc de graphes en m(LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale
ontrant la qualilé de la mcillcurc solution trouvée et le temps d'execution.iiNguyen Thi Hong Hiep Appariement multivoque de graphesAbstractThe similaIflInstitut do la Francophonie pour rinformatiquoInstitut de la Francophoniepour rinformatiqueUniversité catholique de LouvainAppariement multivoque d (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale phs, this problem turns into a similarity measurement between the graphs. In fact, each node of a graph may correspond to many nodes of the other graph. This can only be modeled by multivalent graph matching allowing to matching a node of a graph with several nodes of the other graph. By using the s (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale imilarity measure [1] as the objective function of an optimization problem, the original problem changes from finding the best match between two graph(LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale
s to the search of a matching maximizing the objective function.Unfortunately, multivalent graph matching is a NP-hard problem and cannot be solved byIflInstitut do la Francophonie pour rinformatiquoInstitut de la Francophoniepour rinformatiqueUniversité catholique de LouvainAppariement multivoque d (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale s find the globally optimal result, but gives acceptable solutions. By exploring the search space from neighbor to neighbor. the local search algorithms can progressively improve the quality of the solution and leads the search to the global optimum.In this report, we present three local search algo (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale rithms: greedy, tabu and reactive tabu search implemented in Comet - a programming environment developed for local search and constraints programming.(LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale
In the result section, we will compare the quality of these three algorithms one to another. We evaluate also the efficiency of the local search for IflInstitut do la Francophonie pour rinformatiquoInstitut de la Francophoniepour rinformatiqueUniversité catholique de LouvainAppariement multivoque d (LUẬN văn THẠC sĩ) appariement multivoque de graphes par la recherche locale n Thi Hong HiepIflInstitut do la Francophonie pour rinformatiquoInstitut de la Francophoniepour rinformatiqueUniversité catholique de LouvainAppariement multivoque dGọi ngay
Chat zalo
Facebook