Алгоритм самого низкого общего предка - PullRequest
Новая
       22

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

11 голосов
/ 14 июня 2011

Итак, я искал реализацию алгоритма с наименьшим общим предком.Я посмотрел на множество различных алгоритмов (в основном, варианты решения Траяна или варианты 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
     }

}

Ответы [ 6 ]

16 голосов
/ 14 июня 2011

Как уже упоминалось, ваш алгоритм в настоящее время является квадратичным.Это не может быть проблемой для набора данных размером от 50 до 75 узлов, но в любом случае просто изменить его на линейное время без использования каких-либо наборов или хеш-таблиц, просто записав полный путь к корню для каждого узла, затемспускаясь вниз от корня и ища первый другой узел.Затем непосредственно предшествующий узел (который является общим родителем этих 2 разных узлов) - это 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: Обработать случай, в котором один узелпроисходит от другого, что в противном случае привело бы к попытке pop() пустого стека.Спасибо, черт побери, за то, что указал на это.(Я также понял, что достаточно отследить один oldNode.)

3 голосов
/ 14 июня 2011

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

  1. Переход от первого узла к корню и сбор всех узлов внабор
  2. Перейдите от второго узла к корню и проверьте, существует ли текущий узел в этом наборе.Если это так, то это общий предок.

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

A
|
B
|
C

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

2 голосов
/ 14 июня 2011

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

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

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

1 голос
/ 09 февраля 2012

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

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

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

Пабло

1 голос
/ 14 июня 2011

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

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

0 голосов
/ 07 июля 2012

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

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

...