A legkisebb közös ős
A gráfelmélet , a legkisebb közös őse két csomópont egy fa a legalacsonyabb a fában ( azaz a legmélyebb), amelynek két csomópontot leszármazottai. Az angol kifejezés a legalacsonyabb közös ős (LCA) . Az első közös ős és a legközelebbi közös ős kifejezéseket is használják.
Különböző algoritmusokat találtak ki a legkisebb közös ős gyors megtalálásához.
Meghatározás
Ha egy fát kapunk, két csomópont közös ősei azok a csúcsok, amelyek ennek a két csomópontnak az ősei; más szóval, azok a csomópontok, amelyeknek ez a két csomópont van utódaikban. A legkisebb közös ős (PPAC) ezen a két csomóponton a legmélyebb közös ős, vagyis a legtávolabbi a gyökértől.
A legkisebb közös ősök fogalmát egy irányított aciklusos gráfban (DAG) is meghatározhatjuk.
Algoritmusok
Egyszerű meghatározás és algoritmus
A legtöbb algoritmust, amelyet a fák PPAC-jának megtalálásához vizsgáltak, csomópontpárok lekérdezéseinek megválaszolására hozták létre. Ezek az algoritmusok tehát két fázisból állnak: egy előfeldolgozásból és egy algoritmusból, amely válaszol a kérésekre ( lekérdezésekre ).
Egyszerű algoritmus egy olyan táblázat létrehozása, amely tartalmazza az összes PPAC-t, majd ebből a táblából merít minden kérést. Ez az algoritmus egy időbonyolultsága az O (Nl) (ahol n a méret a fa) az preproccesing (ha dinamikus programozási használunk ), és a kérelmek feldolgozása folyamatos időben.
Gyors algoritmusok
Számos optimális algoritmust javasoltak a PPAC probléma megoldására. Ezek az algoritmusok nagyságrend szerint optimálisak, mivel lineárisan összetettek az előfeldolgozás és az állandó lekérdezési idő szempontjából.
Egyes algoritmusok megfelelő adatstruktúrákat használnak a fa ösvényre bontására, míg mások a fa euleri járásán és a tartomány minimális lekérdezésének (in) kiszámításán alapulnak (néha minimális intervallumnak is nevezik őket ).
Változatok
Algoritmusokat találtak ki általánosabb esetekre, például DAG-okra és dinamikusabb modellekre, csomópontok hozzáadásával és eltávolításával.
Alkalmazások
A legkisebb közös ős olyan objektum, amelyet különösen a szöveges algoritmusokban és a bioinformatikában használnak, ahol sok objektumot fákkal lehet ábrázolni. Ennek egyik kiemelkedő példája a manipuláció utótagot fák , amelyek gyorsan megoldani a problémákat, mint megtalálni a leghosszabb közös karaktersorozat .
Történelmi
A probléma megtalálni a cMYP definiálta először Aho, Hopcroft és Ullman 1973-ban az első optimális algoritmus miatt Harel és Tarján , amelyet aztán egyszerűsíteni Tarján és Gabow az uniós Find szerkezetét. , Majd tovább egyszerűsíthető 1988 1993-ban Berkman és Vishkin egy teljesen más elvű, 2000-ben leegyszerűsített algoritmust tett közzé.
Megjegyzések és hivatkozások
-
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest és Clifford Stein , Bevezetés az algoritmikába , Dunod ,2002[ a kiadás részlete ], "21.3. Tarjan halasztott algoritmusa az első közös ős számára ”, p. 508 .
-
Michael A. Bender és Martin Farach-Colton , „Az LCA-probléma áttekintve” , Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN) , vol. 1776, Springer-Verlag,2000( DOI 10.1007 / 10719839_9 , online olvasás ) , p. 88-94.
-
Charles Bouillaguet, Claire Mathieu, „ Projekt: legközelebbi közös ős ” , az ENS IT részlegén ,2014.
-
Michael A. Bender , Farach-Colton , Giridhar Pemmasani , Steven Skiena és Pavel Sumazin , „A fák legalacsonyabb közös ősei és irányított aciklikus grafikonok ”, Journal of Algorithms , vol. 57, n o 2
2005, P. 75–94 ( online olvasás ).
-
Richard Cole és Ramesh Hariharan, "Dinamikus LCA lekérdezések a fákról" , {A tizedik éves ACM-SIAM szimpózium diszkrét algoritmusok anyagai} című cikkben ,
1999, P. 235–244
-
Johannes Fischer és Volker Heun , „Az RMQ-probléma elméleti és gyakorlati fejlesztései, az LCA-ra és az LCE-re vonatkozó alkalmazásokkal” , a Kombinatorikus mintaillesztés 17. éves szimpóziumának folyóirata , vol. 4009, Springer-Verlag,
2006( DOI 10.1007 / 11780441_5 ) , p. 36-48
-
(in) Dan Gusfield , algoritmusok Strings, fák és sorozatok: Computer Science and Computational Biology , Cambridge / New York / Melbourne, Cambridge University Press ,
1999, 534 p. ( ISBN 0-521-58519-8 , online olvasás )
-
Alfred Aho , John Hopcroft és Jeffrey Ullman : „A legalacsonyabb közös ősök megtalálásáról a fák között” , Proc. 5. ACM Symp. Számítástechnika (STOC) ,
1973( DOI 10.1145 / 800125.804056 ) , p. 253-265.
-
Dov Harel és Robert E. Tarjan , „ Gyors algoritmusok a legközelebbi közös ősök megtalálásához ”, SIAM Journal on Computing , vol. 13, n o 2
1984, P. 338-355 ( DOI 10.1137 / 0213024 ).
-
Harold N. Gabow és Robert Endre, Tarján , „A lineáris idejű algoritmust egy speciális esete a diszjunkt halmaz unió” , a Proceedings of the tizenötödik éves ACM Symposium on Theory számítástechnikai ,
1983, P. 246-251.
-
Lásd Tarjan off-line legalacsonyabb közös ősök algoritmusát (in) .
-
Baruch Schieber és Uzi Vishkin , „ A legkisebb közös ősök megtalálásáról: egyszerűsítés és párhuzamosság ”, SIAM Journal on Computing , vol. 17, n o 6,
1988, P. 1253-1262 ( DOI 10.1137 / 0217079 )
-
Omer Berkman és Uzi Vishkin , „ Rekurzív csillag-fa párhuzamos adatszerkezet ”, SIAM Journal on Computing , vol. 22, n o 2
1993, P. 221–242 ( DOI 10.1137 / 0222017 )