Ich schaute mir this question an und las dann über Tarjan's least common ancestors algorithm. Ich habe nie zuvor Anwendungen von LCA-Algorithmen gefunden.Was sind die praktischen Anwendungen der kleinsten gemeinsamen Vorfahren-Algorithmen?
Wo werden solche LCA-Algorithmen häufig verwendet?
Sie wissen nicht, wo sie verwendet wird, aber ich habe ein paar Ideen, wo es gewöhnen könnten:
Computergrafik: oft bekommen 3D-Szenerien in Würfel aufgeteilt, die eine Baumstruktur bilden. Wenn Sie ein Objekt haben, das in zwei solcher Würfel enthalten ist, gibt Ihnen ein LCA-Algorithmus den kleinsten größeren Würfel.
Analyse von gen um
die Beziehungen zwischen den Arten und ihren kleinsten gemeinsamen Vorfahren zu findenMerge-Algorithmen von Versionskontrollsystemen
danke! Versionskontrolle -> Three Way Merge: http://en.wikipedia.org/wiki/Merge_(revision_control)#Three-way_merge – Lazer
Es ist auch nützlich für bestimmte Arten der String-Verarbeitung bei der Suche nach Stammwörtern für verschiedene Suffixe. –
In Compiler, die LCA von zwei Basisblöcken ist ein Stellen Sie eine Berechnung ein, damit sie für beide verfügbar ist. Dies kann nützlich sein, um häufige Teilausdrücke zu eliminieren oder um phi-node für die SSA-Konvertierung einzufügen. Diese Algorithmen sind gut entwickelt und hoch optimierten, obwohl, so die LCA selbst schwierig sein kann, um zu sehen, zum Beispiel SSA und PRE
danke @Doug Currie – Lazer
ich gerade eine Blog-Post über schrieben, wie ich hatte meinen eigenen Algorithmus für dieses Problem zu implementieren (extended zu einem Satz von Knoten mit einer beliebigen Länge) für einen Taxonomie Baum im Rahmen der Metagenomics:
Prost,
Pablo
Spatial Datenstrukturbäume im Scientific Computing, Suffixbäume für Strings in der Computerbiologie, etc. Die Details vergessen, sorry, aber es ist definitiv nützlich. – polygenelubricants