Название алгоритма восстановления дерева по наименьшему общему предку?

Question

Я хотел бы написать инструмент, который работает с некоторыми древовидными данными. (На самом деле он будет работать с древовидным подмножеством GAG-версии DAG, но для этого вопроса это не важно). В частности, я хочу алгоритм, который восстанавливает подмножество дерева, состоящее из всех "точек соединения" данного входного набора.

В частности, я думаю, что хочу

• У нас есть какой-то тип H которая имеет функцию "самого низкого общего предка", lca в теме. Это дает H древовидная структура.

• Алгоритм занимает некоторое подмножество S из H в качестве ввода.

• На выходе должно быть многоходовое дерево t с узлами, помеченными значениями H,

• t должен удовлетворять свойствам

  • Все s в S пометить некоторый узел t

  • Листья t могут быть помечены только элементами S

  • Любой элемент h за H метки не более одного узла t

  • Если h1 этикетки n1 а также h2 этикетки n2 затем lca(h1, h2) обозначает самого низкого общего предка n1 а также n2 в t,

Мой вопрос: "Это известная проблема с известными алгоритмами?". Я подозреваю, что это так. Это похоже на топологический вид. У меня есть идея для алгоритма, основанного на сортировке слиянием, но если известные алгоритмы уже существуют, нет никаких причин, чтобы придумать свой собственный.

Answer 1

Я не знаю, как вы это называете, но я сначала сравнил бы все пары элементов, чтобы построить частичный порядок для дерева, затем выполнил топологическую сортировку, а затем построил дерево из этого. (Смысл сортировки в том, что теперь вы знаете, что первый элемент - это корень, а каждый элемент в свою очередь будет листом.)

Субъект напомнил мне алгоритмы кладистики, http://bio.slu.edu/mayden/systematics/bsc420520lect12.html. Однако это и проще, и сложнее. Проще, потому что при осмотре легко определить, какие формы близки к другой. Сложнее, потому что проблема в том, что вы не знаете LCA. Таким образом, это может быть интересным побочным треком, но, вероятно, не очень полезно.