Je regardais this question puis je lisais environ Tarjan's least common ancestors algorithm. Je n'ai jamais rencontré d'applications d'algorithmes LCA auparavant.Quelles sont les applications pratiques des algorithmes d'ancêtres communs les plus bas?
Où ces algorithmes LCA sont-ils couramment utilisés?
Je ne sais pas où il est utilisé, mais j'ai quelques idées où il pourrait être utilisé:
infographie: souvent des paysages 3D se divisent en cubes qui forment une structure arborescente. Si vous avez un objet qui est contenu dans deux cubes, un algorithme LCA vous donne le plus petit cube plus grand.
de Gén afin de trouver les relations entre les espèces et leur ancêtre commun le plus
algorithmes de fusion des systèmes de contrôle de version
merci! contrôle de version -> fusion à trois voies: http://en.wikipedia.org/wiki/Merge_(revision_control)#Three-way_merge – Lazer
Il est également utile pour certains types de traitement de chaîne lors de la recherche de mots racines pour différents suffixes. –
Dans compilateurs, la LCA de deux blocs de base est un placez vous pouvez mettre un calcul afin qu'il soit disponible pour les deux. Cela peut être utile pour éliminer les sous-expressions courantes ou insérer un nœud phi pour la conversion SSA. Ces algorithmes sont bien évolués et très optimisés, donc le LCA lui-même peut être difficile à voir, par exemple, SSA et PRE
merci @Doug Currie – Lazer
Je viens d'écrire un billet de blog sur la façon dont j'ai dû mettre en œuvre mon propre algorithme pour ce problème (étendu pour un ensemble de noeuds avec une longueur arbitraire) pour un arbre de taxonomie dans le contexte de la métagénomique:
vôtre,
Pablo
Spatial arbres de structure de données dans le calcul scientifique, arbres de suffixe pour les chaînes dans la biologie computationnelle, etc. Oublié les détails, désolé, mais c'est certainement utile. – polygenelubricants