Stavo dando un'occhiata a this question e poi leggendo su Tarjan's least common ancestors algorithm. Non ho mai incontrato alcuna applicazione di algoritmi LCA prima.Quali sono le applicazioni pratiche degli algoritmi degli antenati più comuni?
Dove sono comunemente utilizzati tali algoritmi LCA?
Non so dove viene utilizzato, ma ho un paio di idee in cui potrebbe abituarsi:
computer grafica: spesso scenari 3D vengono suddivisi in cubetti che formano una struttura ad albero. Se si dispone di un oggetto contenuto in due di questi cubi, un algoritmo LCA fornisce il cubo più piccolo contenente il più piccolo.
analisi della gens al fine di trovare le relazioni tra le specie ed il loro più basso antenato comune
algoritmi di unione dei sistemi di controllo versione
grazie! controllo versione -> unione a tre vie: http://en.wikipedia.org/wiki/Merge_(revision_control)#Three-way_merge – Lazer
È utile anche per alcuni tipi di elaborazione di stringhe quando si cercano le parole radice per diversi suffissi. –
Nel compilatori, la LCA di due blocchi di base è un posto puoi mettere un calcolo così è disponibile per entrambi. Ciò potrebbe essere utile per eliminare le sottoespressioni comuni o per inserire un nodo-phi per la conversione SSA. Questi algoritmi sono ben evoluti ed altamente ottimizzata, però, in modo che il LCA stessa può essere difficile da vedere, ad esempio, SSA e PRE
grazie a @Doug Currie – Lazer
ho appena scritto un post sul blog su come dovevo realizzare il mio proprio algoritmo per questo problema (esteso a un insieme di nodi con una lunghezza arbitraria) per un albero tassonomia nel contesto metagenomics:
Salute,
Pablo
Spatial alberi della struttura dei dati nel calcolo scientifico, alberi del suffisso per le stringhe nella biologia computazionale, ecc. Ho dimenticato i dettagli, mi dispiace, ma è sicuramente utile. – polygenelubricants