Algorithmique et Programmation Projet Plus petit ancetre commun

Publié par

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


Publié le : mardi 19 juin 2012
Lecture(s) : 82
Source : di.ens.fr
Nombre de pages : 3
Voir plus Voir moins
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
Partie “en-ligne”Une fois qu’on a ce tableauT, on peut s’en servir pour calculerRMQen temps A k k constant. Notons 2la plus grande puissance de deux telle quei+ 21joi,nnti´erdPa. k k l’intervalle [i;j[esllreavixtndsueraelertpcouvemnetnit`]eerseti;i+ 21] et [j2 +1;j]. Il s’ensuit que : (      k kk T i,i+ 21 ifA Ti, i+ 21< AT i,i+ 21 RMQ(i, j) =  A k T j12 +, jotherwise
3Range Minimum QueriesenO(n)par le truc des quatre Russes Poursed´ebarrasserdufacteurlogarithmique,ilsutdenutiliserlalgorithmesous-optimalquesur des tableaux de tailleO(n/logn). On peut obtenir cela en utilisant une technique classique qui s’ap-pellelame´thodedesquatrerusses.Cettetechnique,dabordappliqu´ee`alamultiplicationdematrices bool´eennes,ae´te´invente´eparArlazarov,Dinic,KronrodetFaradzeven1970[1](ilsave`reenfaitquun seuldecesauteursestrusse,maislenomestrest´e).Lide´ege´ne´raleestlasuivante[2]: logn ond´ecoupeletableauxAen blocs de taille(on va supposer que le logarithme est pair, pour se 2 0 0 simplierlavie).Ond´enitalorsuntableauAtel queA[i] contient le mimium duidceem-`loebA. 0 0 Delameˆmemani`ere,ond´enitB[icediinllensdamoc]tnate´emiimum-lbcoe`emmeni`oluA[i] estatteint.Onpeutalorsappliquerlepre´calculdelalgorithmeRMQde la section 2 au tableau 0 Aen tempsO(n). Onpre´calculeetonstocketouteslesvaleurspossiblesdeRMQ(i, j) quandietjsont dans le A meˆmebloc(cf.ci-dessous). Ilrestea`d´eterminercommentcalculerRMQen temps constant. Pour cela, on observe que sii A etjneenraitappnocblmeˆeumsapantsrola,RMQ(i, j) est l’indice du minimum des trois valeurs A suivantes : 1.Leminimumdelintervallequise´tenddeiaal`clloubndetancenotn 2.Leminimumdelintervalleform´edetouslesblocscomprisentreceluideiet celui dej 3.Leminimumdelintervallequise´tenddude´butdubloccontenantj`aj.eˆmmeul-i 0 Ladeuxie`mevaleurestfournieparlalgorithmedelasection2appliqu´eautableauA, tandis que lapremi`ereetlatroisie`mesontd´ej`atoutespreˆtesparcequellesont´et´epr´ecalcule´es. Ilrestea`d´eterminercommentpr´ecalculertouteslesvaleurspossiblesdeRMQemel`a´tnieiredruˆmnu A bloc en tempsO(n). Pour cela, on observe que si on prend un bloc quelconque, et qu’on ajoute une constante`achacundesese´l´ements,onvamodierlavaleurabsolueduminimumdubloc,maispassa positiondanslebloc.Tantquonnesinte´ressequ`alapositionduminimumdanslebloc,onpeutdoncse restreindre`adesblocsmronse´silaerimltpe´lmeree´t-`acesedon-dir,O.ire´oruaztnevtaquelnyO(n) logn blocsnormalise´sdi´erentsdetaille,puisquechaquecasenedi`eredelapre´ce´dentequeduneunit´e. 2 Onpeutdonc,pourchaqueblocnormalis´epossible,pr´ecalculerasseznaı¨vementlensembledesr´eponses `alint´erieurdubloc,etlepre´traitementdelensembledesblocsnormalis´esestpossibleentempseten 2 espaceOnlogn. Undernierd´etail:d´eterminerlaformenormalis´eedunblocdemandeaprioriuntempsO(logn), doncnepeutpasˆetrefaiten-ligne.Ilfautdoncpr´ecalculera`lavancepourchaqueblocquelleestsa formenormalise´e.
4Travaildemand´e Programmezlalgorithmeavecpr´ecalculenO(n)tsenurin-curousdnC.Vd´eevezirst´dcenoe3ceit turededonn´eepourstockerlarbre,puiscre´erdeuxfonctions:PrecalculetLCA. Votre programme doitprendreenargumentlenomdunchierquide´criraunarbre.Leformatdecechierestsimple: ()onuesdue,ld´igesunne(((())))gnoleden,4rueud´esigneunpeig(()()()()())recaennunieigesd´ avec 5 fils, et((()())(()()))ds.Onvast`a7noeueuelnseopuopesqrneigarlesd´ocerelpmberbianisud sontnum´erot´esa`partirdeze´rodanslordreduparcourspre´xe.Votreprogrammedevraeectuerle pr´ecalculpuisacherREADYsurlasortiederreur.Apartirdecemoment-l`a,votreprogrammedevra liresurlentr´eestandardunepairededeuxentiers,ete´criresurlasortiestandardlenum´eroduplus petitanceˆtrecommunauxdeuxsommetsenquestion. Par exemple, si l’arbre est((()()())((())(()()))),laraqerolseuˆet7 9reuq´ralnopeesdrovooitp 5e.´etren.prLa´eocreduitdosraˆrtereolsruqunelignevideest
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.