Я смотрел this question, а затем читал о Tarjan's least common ancestors algorithm. Раньше я никогда не сталкивался с любыми применениями алгоритмов LCA.Каковы практические применения алгоритмов с наименьшим общим предком?
Где такие алгоритмы LCA обычно используются?
Не знаю, где он используется, но у меня есть пара идей, где она может привыкнуть:
компьютерной графики: часто 3D пейзажи получают расколоть на кубики, которые образуют структуру дерева. Если у вас есть объект, который содержится в двух таких кубах, алгоритм LCA дает вам самый маленький содержащий более крупный куб.
анализ рода, чтобы найти взаимосвязь между видами и их наименьшего общего предка
слияния алгоритмы систем контроля версий
спасибо! контроль версий -> трехстороннее слияние: http://en.wikipedia.org/wiki/Merge_(revision_control)#Three-way_merge – Lazer
Он также полезен для некоторых видов обработки строк при поиске корневых слов для разных суффиксов. –
В компиляторах LCA из двух основных блоков является вы можете поместить вычисление, чтобы оно было доступно для обоих. Это может быть полезно для устранения общих подвыражений или вставки phi-узла для преобразования SSA. Эти алгоритмы хорошо развиты и сильно оптимизированы, поэтому сама LCA может быть труднодоступной, например, SSA и PRE
спасибо @Doug Currie – Lazer
Я только что написал сообщение в блоге о том, как мне пришлось реализовать свой собственный алгоритм для этой проблемы (расширенный к набору узлов с произвольной длиной) для таксономии дерева в контексте метагеномика:
Чирза,
Пабло
Spatial деревья структуры данных в научных вычислениях, деревья суффикса для строк в вычислительной биологии и т. д. Забыл подробности, извините, но это определенно полезно. – polygenelubricants