Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

Algorithmique et Projet : Plus petit
Programmation anceˆtrecommun
Ecolenormalesup´erieure De´partementdinformatique td-algo@di.ens.fr 2011-2012
Leprobl`emeduLowest Common Ancestor (LCA)seoduuenxltseet:´tdanuiesntvauetvdans un arbredonn´e,ilsagitdetrouverquelestlancˆetrecommun`auet`avseiupelt´sulioleqgn´epossibledela racine.Ilexisteunalgorithmequasi-trivialquire´soutlaquestionentempsO(ho)u`hruetlee´nigsuahda delarbre.Onpourraitaussipre´calculerler´esultatpourtouteslespairesdesommets,andepouvoir    2 2 re´pondreentempsconstantr,`measisap´ecaunprneclluOn, et en utilisant un espaceOn. Onsaitdepuis1984[3]quilestpossibleder´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 ikj o`uargmink. . .elavaleurdde´esignkpour laquelle le minimum est atteint. En effet, on peut utiliser RMQeoudrr´esruopLCA. pr´ecalcullbcednuoOaeledetrˆeaquhatceenosiup,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 2nque)itsuelx´euedatropmiaalsnadtn1.Onnote(cesertndse´emeB di`erentexactementduneunit´e.Ond´enite´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´entreuetvsniusleenI.irneul´e´eeEournslatnadtleseuetqcsi `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(ncestgagn´e.),
2Range Minimum Queriesecav´eprlccaenulO(nlogn) Defac¸onpresqueamusante(maiscestunph´enom`ener´ecurrent),undesingre´dientsclefdelasolution optimaleestunalgorithmesous-optimal.Danscettesectiononveutre´soudreleprobl`emeRMQsur un tableauAden.tseneml´´e   j pre´calculriLeed´dtse´rpelaceelucT[i, j] =RMQi, i+ 21 pourtoutes lesO(logn) valeurs A admissibles dej. Ceci peut se faire en tempsO(nlogn) par programmation dynamique.
1