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

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

Решение

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

Источник

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

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

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

A
|
B
|
C

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

Источник

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

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

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

Источник

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

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

Источник

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

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

Ура,

Pablo

Источник

У меня есть одно упрощенное решение, сортирующее два элемента, и нижний должен быть левым, а самый верхний правым посещением. 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

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

Источник
Другие вопросы по тегам