низший подчиненный двух понятий в таксономии

Question

Как найти низший подчиненный из двух понятий эффективным способом?Низший подчиненный двух понятий в таксономии означает наиболее определенного общего предка двух понятий.Например, в следующей картине таксономии, как найти наиболее общего предка смысла 1 и смысла 2?

Кстати, я нашел этот вопрос в опросе Роберто Навильи оЗначение слова.Он не упомянул, как вычислить подчиненного.

Answer 1

Вы можете перейти вверх по иерархии со стороны Sense 1 и отметить все эти узлы как предки Sense 1. Затем поднимитесь на сторону Sense 2 и проверьте каждого предка, чтобы увидеть, отметили ли вы его как предка Sense 1. Первым, кого вы найдете, будет самый низкий верхний или самый частый общий предок.

На вашей картинке это будет корневой узел, независимо от того, с каких чувств вы начинаете.

Answer 2

http://en.wikipedia.org/wiki/Lowest_common_ancestor содержит указатели на более эффективные алгоритмы для наименьшей общей проблемы предков в (обычном) случае, когда у нас есть дерево, поэтому у каждого узла есть один родительский элемент, за исключением корневого узла, у которого нет родительского элемента,Эти алгоритмы могут отвечать на запросы в постоянное время, после линейной предварительной обработки дерева.

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