Algorithmique et Programmation Projet Plus petit ancetre commun

Description

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

Sujets

• Arbre binaire
• multiplication

Informations

• Publié par: pefav
• Nombre de lectures: 88
• Langue: Français

Extrait

Algorithmique et Projet : Plus petit

Programmation anceˆtrecommun

Ecolenormalesup´erieure De´partementd’informatique [e-mail] 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,afindepouvoir    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`uargmin k . . .elavaleurdde´esignkpour laquelle le minimum est atteint. En effet, on peut utiliser RMQeoudrr´esruopLCA. pr´ecalcullbcednuoO’aeledetrˆeaquhatceffenosiup,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 diff`erentexactementd’uneunit´e.Ond´efinite´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   LCA T (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.

1