Алгоритм наименьшего общего предка

Итак, я изучал реализацию алгоритма с наименьшим общим предком. Я рассмотрел множество различных алгоритмов (в основном вариации решения Trajan или вариации RMQ).

Я использую небиновое дерево. Мое дерево часто будет меняться между запросами, и поэтому предварительная обработка не обязательно будет стоить. Дерево не должно содержать более 50-75 узлов. Мне интересно, нужно ли мне использовать их алгоритмы или просто придерживаться своих собственных.

Мой алгоритм

myLCA(node1, node2) {
    parentNode := [ ]
    while (node1!=NULL) {
         parentNode.push(node1)
         node1 := node1.parent
    }
     while (node2!=NULL) {
         for i in parentNode.size {
             if (parentNode(i) == node2) {
                 return node2; 
             }
         }
         node2 := node2.parent
     }

}

Ответ 1

Как уже упоминалось, ваш алгоритм в настоящее время квадратичен. Это может быть не проблемой для набора данных размером не менее 50-75 узлов, но в любом случае просто изменить его на линейное время без использования каких-либо наборов или хеш-таблиц, просто записав полный путь к корню для каждого node, затем отступая от корня и ищет первые разные node. Немедленно предшествующий node (который является общим родителем этих двух разных узлов) является LCA:

linearLCA(node1, node2) {
    parentNode1 := [ ]
    while (node1!=NULL) {
         parentNode1.push(node1)
         node1 := node1.parent
    }
    parentNode2 := [ ]
    while (node2!=NULL) {
         parentNode2.push(node2)
         node2 := node2.parent
    }
    while (node1 == node2 && !isEmpty(parentNode1) && !isEmpty(parentNode2)) {
        oldNode := node1
        node1 := parentNode1.pop()
        node2 := parentNode2.pop()
    }
    if (node1 == node2) return node1    // One node is descended from the other
    else return oldNode                 // Neither is descended from the other
}

РЕДАКТИРОВАТЬ 27/5/2012: Обрабатывать случай, когда один node происходит от другого, что в противном случае приведет к попытке pop() пустого стека. Спасибо, что процитировал это. (Я также понял, что достаточно отслеживать один oldNode.)

Ответ 2

Для небольшого дерева я бы не стал заниматься чем-то более сложным. Ваше решение выглядит хорошо, хотя временная сложность возведена в квадрат с точки зрения высоты дерева. Если вы можете легко реализовать Set (большинство языков имеют встроенный), тогда алгоритм может быть изменен,

Перейдите от первого node до корня и соберите все узлы в наборе
Перейдите со второго node до корня и проверьте, существует ли текущий node в этом наборе. Если это так, то это общий предок.

Кроме того, этот алгоритм предполагает, что node может быть его собственным предком. В противном случае вам придется слегка настроить алгоритм. Рассмотрим этот пример,

A
|
B
|
C

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

Ответ 3

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

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

Я думаю, что не стоит оптимизировать немного кода, если вы не увидите значительных результатов (некоторые люди очень сильно чувствуют, что преждевременная оптимизация корень всех злых)

Ответ 4

Ваш алгоритм квадратичен, но его можно легко сделать линейным.

Просто используйте хеш-таблицу (т.е. установить) для parentNode вместо списка. Таким образом, проверка node в parentNode будет O(1) вместо O(n).

Ответ 5

Я только что написал сообщение в блоге о том, как мне пришлось реализовать свой собственный алгоритм для этой проблемы, но расширился до набора узлов с произвольной длиной. Вы можете найти его здесь (с пошаговым графическим объяснением того, как он работает)

http://bio4j.com/blog/2012/02/finding-the-lowest-common-ancestor-of-a-set-of-ncbi-taxonomy-nodes-with-bio4j/

Приветствия,

Пабло

Ответ 6

У меня есть одно упрощенное решение сортировать два элемента, а самый низкий - левый и самый высокий - правые посещать корень def recurse (корень) return nil if root.empty? если оставить <= корень && right >= root вернуть корень elsif left <= корень && right <= root рекурсия (root.left) еще рекурсия (root.right) конец

Таким образом, это будет проверяться на каждом обходе Проблема решена в O (log n) времени для среднего и худшего и O (log