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

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

6 ответов:

Как уже упоминали другие, Ваш алгоритм в настоящее время квадратичен. Это не может быть проблемой для набора данных размером 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
}

EDIT 27/5/2012: обрабатывает случай, в котором один узел происходит от другого, что в противном случае привело бы к попытке pop() пустой стек. Спасибо проклятому, что указал на это. (Я также понял, что достаточно отслеживать один oldNode.)

15

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

  1. пройдите от первого узла до корня и соберите все узлы в набор
  2. перейдите от второго узла к корню и проверьте, существует ли текущий узел в этом наборе. Если значит, это и есть общий предок.
Кроме того, этот алгоритм предполагает, что узел может быть его собственным предком. В противном случае вам придется немного изменить алгоритм. Рассмотрим этот пример, 
A
|
B
|
C

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

3

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

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

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

2

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

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

1

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

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

Ура,

Пабло

1

У меня есть одно упрощенное решение отсортируйте два элемента, и самый низкий будет слева, а самый высокий-справа. посетите корень деф рекурсия(корень) верните ноль, если корень.пусто? если слева = root вернуть корень elsif операторы слева

Таким образом, это будет проверяться на каждом обходе Проблемы растворяются в o(зарегистрируйте N) времени для средних и худших, и o(зарегистрируйте

0