Algorithmique et Programmation Projet Plus petit ancetre commun

pages

Français

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

pages

Français

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

Français

Algorithmique et Programmation Projet : Plus petit ancetre commun Ecole normale superieure Departement d'informatique 2011-2012 Le probleme du Lowest Common Ancestor (LCA) est le suivant : etant deux noeuds u et v dans un arbre donne, il s'agit de trouver quel est l'ancetre commun a u et a v qui est le plus eloigne possible de la racine. Il existe un algorithme quasi-trivial qui resout la question en temps O (h) ou h designe la hauteur de l'arbre. On pourrait aussi precalculer le resultat pour toutes les paires de sommets, afin de pouvoir repondre en temps constant, mais apres un precalcul en O ( n2 ) , et en utilisant un espace O ( n2 ) . On sait depuis 1984 [3] qu'il est possible de resoudre le probleme en temps constant, si on a pu faire au prealable un precalcul lineaire en la taille de l'arbre. Le but de ce projet est de programmer un algorithme exhibant ces performances. 1 Correspondance avec Range Minimum Queries Le probleme Lowest Common Ancestor est etroitement lie a un autre probleme, Range Minimum Queries. Dans cet autre probleme, on a un tableau A contenant n entiers, et il s'agit de calculer RMQA(i, j) = arg min i≤k≤j A[k] ou arg mink .

bloc quelconque

zero dans l'ordre du parcours prefixe

minimum de l'intervalle

probleme du lowest common

arbre

probleme rmq

arbre binaire

bloc

Voir

Publié par

pefav

Langue

Français

Arbre binaire multiplication

Algorithmique et Projet : Plus petit

Programmation anceˆtrecommun

Ecolenormalesup´erieure De´partementd’informatique td-algo@di.ens.fr 2011-2012

Leprobl`emeduLowest Common Ancestor (LCA)seoduuenxltseet:´tdanuiesntvauetvdans un arbredonn´e,ils’agitdetrouverquelestl’ancˆetrecommun`auet`avseiupelt´sulioleqgn´epossibledela racine.Ilexisteunalgorithmequasi-trivialquire´soutlaquestionentempsO(ho)u`hruetlee´nigsuahda del’arbre.Onpourraitaussipre´calculerler´esultatpourtouteslespairesdesommets,aﬁndepouvoir    2 2 re´pondreentempsconstantr,`measisap´ecaunprneclluOn, et en utilisant un espaceOn. Onsaitdepuis1984[3]qu’ilestpossibleder´esoudreleprobl`emeentempsconstant,sionapufaire aupr´ealableunpr´ecalculeriae´nilen la taille de l’arbre. Le but de ce projet est de programmer un algorithme exhibant ces performances.

1 CorrespondanceavecRange Minimum Queries Leproble`meLowest Common Ancestorutreprobl`eme,metiltne`e´ianuat´esroetRange Minimum Queries. Danscetautreproble`me,onauntableauAcontenantnentiers, et il s’agit de calculer RMQ(i, jmin) = argA[k] A i≤k≤j o`uargmink. . .elavaleurdde´esignkpour laquelle le minimum est atteint. En eﬀet, on peut utiliser RMQeoudrr´esruopLCA. pr´ecalcullbcednuoO’aeledetrˆeaquhatceﬀenosiup,erbreunuapcruosruE´leriendugrapher´etlustna en partant de la racine (en d’autres termes, on fait un parcours en profondeur de l’arbre, mais on ignorepaslessommetsd´eja`vus).Onstockeleistn´rdenaeudrenco-`emenoA[i], et on stocke sa hauteur dansB[icemmoC.]ioesnufe´seevaresttreteeearˆhaquisfomoenanntt,sedndnecetnaenut la taille deAetBest 2n−que)itsuelx´euedatropmiaalsnadtn1.Onnote(cesertndse´emeB diﬀ`erentexactementd’uneunit´e.Ond´eﬁnite´galementlapremie`reoccurrencedeidansA: C[i] = arg min{k:A[k] =i} Ge´n´ererlestroistableauxA,BetCse.eemernetntiafialclsnietpmernee´iaillelataarbrdel’ ´ Partie “en-ligne”peiaeredosmmtesnttaEun´enndouetv, il est clair (et on admettra) que leur plus petitancˆetrecommunestvisite´entreuetvsniusle’enI.irneul´e´eeEournslatnadtleseuetqc’si `sivde´tieme`ueon-i,alorsC[u]≤`≤C[v], et clairementB[`] est minimal dans l’intervalle. On a donc :h i   LCAT(u, v) =ARMQC[u], C[v] B

Si on est capable de calculerRMQen tempsOr´ecalculen1(a)rpe`uspnO(nc’estgagn´e.),

2Range Minimum Queriesecav´eprlccaenulO(nlogn) Defac¸onpresqueamusante(maisc’estunph´enom`ener´ecurrent),undesingre´dientsclefdelasolution optimaleestunalgorithmesous-optimal.Danscettesectiononveutre´soudreleprobl`emeRMQsur un tableauAden.tseneml´´e   j pre´calculr’iLeed´dtse´rpelaceelucT[i, j] =RMQi, i+ 2−1 pourtoutes lesO(logn) valeurs A admissibles dej. Ceci peut se faire en tempsO(nlogn) par programmation dynamique.

Voir