Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Эта статья о низших общих предках в теории графов и информатике. Чтобы узнать об общем предке набора видов в эволюционных деревьях, см. Самого последнего общего предка . Чтобы узнать об общем предке всех форм жизни, см. Последний универсальный общий предок .
В этом дереве наименьший общий предок узлов x и y отмечен темно-зеленым. Остальные общие предки показаны светло-зеленым цветом.

В теории графов и информатике , то самые низкий общий предок ( LCA ) из двух узлов V и W в дереве или ориентированный ациклический граф (DAG) Т является самым низким (то есть самым глубоким) узлом , который имеет как V и W , как потомки, где мы определите, что каждый узел является потомком самого себя (так, если v имеет прямое соединение с w , w является самым низким общим предком).

LCA v и w в T - это общий предок v и w , расположенный дальше всего от корня. Вычисление наименьших общих предков может быть полезно, например, как часть процедуры определения расстояния между парами узлов в дереве: расстояние от v до w может быть вычислено как расстояние от корня до v плюс расстояние от корня до w , минус вдвое большее расстояние от корня до их наименьшего общего предка ( Djidjev, Pantziou & Zaroliagis 1991 ). В онтологиях самый низкий общий предок также известен какнаименее общий предок .

В древовидной структуре данных, где каждый узел указывает на своего родителя, наименьшего общего предка можно легко определить, найдя первое пересечение путей от v и w до корня. В общем, вычислительное время, необходимое для этого алгоритма, составляет O (h), где h - высота дерева (длина самого длинного пути от листа до корня). Однако существует несколько алгоритмов обработки деревьев, чтобы можно было быстрее найти наименьших общих предков. Автономный алгоритм наименьших общих предков Тарьяна , например, предварительно обрабатывает дерево за линейное время, чтобы предоставить запросы LCA с постоянным временем. В целом в DAG существуют похожие алгоритмы, но с суперлинейной сложностью.

История [ править ]

Проблема наименьшего общего предка была определена Альфредом Ахо , Джоном Хопкрофтом и Джеффри Уллманом  ( 1973 ), но Дов Харел и Роберт Тарджан  ( 1984 ) были первыми, кто разработал оптимально эффективную структуру данных наименьшего общего предка. Их алгоритм обрабатывает любое дерево за линейное время, используя декомпозицию по тяжелому пути , так что последующие запросы с наименьшим общим предком могут получать ответы за постоянное время для каждого запроса. Однако их структура данных сложна и трудна для реализации. Тарьян также нашел более простой, но менее эффективный алгоритм, основанный на структуре данных объединение-поиск , длявычисление наименьших общих предков автономного пакета пар узлов .

Барух Шибер и Узи Вишкин  ( 1988 ) упростили структуру данных Харела и Тарьяна, что привело к реализуемой структуре с той же асимптотической предварительной обработкой и временными пределами запроса. Их упрощение основано на том принципе, что в двух особых типах деревьев наименьших общих предков легко определить: если дерево является путем, то наименьший общий предок может быть вычислен просто из минимума уровней двух запрашиваемых. узлов, а если дерево представляет собой полное двоичное дерево, узлы могут быть проиндексированы таким образом, чтобы самые низкие общие предки сводились к простым бинарным операциям с индексами. Структура Шибера и Вишкина разбивает любое дерево на набор путей, так что связи между путями имеют структуру двоичного дерева, и объединяет оба этих двух более простых метода индексации.

Омер Беркман и Узи Вишкин ( 1993 ) открыли совершенно новый способ ответа на запросы с наименьшим общим предком, снова достигнув линейного времени предварительной обработки с постоянным временем запроса. Их метод включает формирование эйлерова обхода графа, образованного из входного дерева, путем удвоения каждого ребра и использования этого обхода для записи последовательности номеров уровней узлов в порядке их посещения. затем запрос наименьшего общего предка может быть преобразован в запрос, который ищет минимальное значение, встречающееся в некотором подынтервале этой последовательности чисел. Затем они обрабатывают этот минимальный запрос диапазонаЗадача состоит в объединении двух методов, одна из которых основана на предварительном вычислении ответов на большие интервалы, размеры которых равны степеням двойки, а другая - на поиске в таблице для запросов с малым интервалом. Позднее этот метод был представлен в упрощенной форме Майклом Бендером и Мартином Фарач-Колтоном  ( 2000 ). Как ранее было замечено Габоу, Бентли и Тарджан (1984) , проблема минимума дальности, в свою очередь, может быть преобразована обратно в проблему наименьшего общего предка, используя технику декартовых деревьев .

Дальнейшие упрощения были сделаны Alstrup et al. (2004) и Fischer & Heun (2006) .

Sleator и Tarjan  ( 1983 ) предложили динамический вариант проблемы с LCA, в котором структура данных должна быть подготовлена ​​для обработки запросов LCA, смешанных с операциями, которые изменяют дерево (то есть переупорядочивают дерево путем добавления и удаления ребер). Этот вариант можно решить вовремя в общем размере дерева для всех модификаций и запросов. Это достигается за счет поддержки леса с использованием структуры данных динамических деревьев с секционированием по размеру; это затем поддерживает тяжелую-легкую декомпозицию каждого дерева и позволяет выполнять запросы LCA за логарифмическое время в размере дерева.

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

Расширение на ориентированные ациклические графы [ править ]

DAG, общие предки x и y выделены светло-зеленым, а их самые низкие общие предки - темно-зеленым.

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

  • Учитывая G = ( V , E ) , Aït-Kaci et al. (1989) определяют ЧУМ ( V , ≤) такое, что x ≤ y тогда и только тогда, когда x достижимо из y . Тогда наименьшие общие предки x и y являются минимальными элементами под ≤ ≤ множества общих предков { z ∈ V | x ≤ z и y ≤ z }.
  • Бендер и др. (2005) дали эквивалентное определение, где самые низкие общие предки х и у являются узлами вне степени нуля в подграфе из G индуцированного множества общих предков х и у .

В дереве уникален самый низкий общий предок; в DAG из n узлов каждая пара узлов может иметь до n -2 LCA ( Бендер и др., 2005 ), в то время как существование LCA для пары узлов даже не гарантируется в произвольно подключенных DAG.

Алгоритм прямого перебора для поиска самых низких общих предков представлен Aït-Kaci et al. (1989) : найти всех предков x и y , затем вернуть максимальный элемент пересечения двух наборов. Существуют лучшие алгоритмы, которые, аналогично алгоритмам LCA для деревьев, предварительно обрабатывают граф, чтобы обеспечить выполнение запросов LCA с постоянным временем. Проблема существования LCA может быть решена оптимально для разреженных DAG с помощью алгоритма O (| V || E |) , разработанного Ковалук и Лингас (2005) .

Dash et al. (2013) представляют унифицированную структуру для предварительной обработки ориентированных ациклических графов для вычисления наименьших общих предков за постоянное время. Их структура может достигать почти линейного времени предварительной обработки для разреженных графов и доступна для публичного использования. [2]

Приложения [ править ]

Проблема вычисления низших общих предков классов в иерархии наследования возникает при реализации систем объектно-ориентированного программирования ( Aït-Kaci et al. 1989 ). Проблема LCA также находит применение в моделях сложных систем, используемых в распределенных вычислениях ( Bender et al. 2005 ).

См. Также [ править ]

  • Проблема предка уровня
  • Полурешетка

Ссылки [ править ]

  1. ^ https://www.schoolofhaskell.com/user/edwardk/online-lca Эдвард Кметт (2012)
  2. ^ «Попробуйте наш исходный код бесплатно» .
  • Ахо, Альфред ; Хопкрофт, Джон ; Ульман, Джеффри (1973), "Об обнаружении самых низких общих предков у деревьев", Proc. 5-й симпозиум ACM. Теория вычислений (STOC) , стр 253-265,. DOI : 10,1145 / 800125,804056.
  • Aït-Kaci, H .; Boyer, R .; Lincoln, P .; Наср, R. (1989), "Эффективное осуществление операций решетки" (PDF) , ACM Сделки по Языки программирования и системы , 11 (1): 115-146, CiteSeerX  10.1.1.106.4911 , DOI : 10,1145 / 59287.59293.
  • Альструп, Стивен; Гавой, Сирил; Каплан, Хаим; Раухе, Тайс (2004), «Ближайшие общие предки: обзор и новый алгоритм для распределенной среды» , Теория вычислительных систем , 37 (3): 441–456, CiteSeerX  10.1.1.76.5973 , doi : 10.1007 / s00224 -004-1155-5. Предварительная версия появилась в SPAA 2002.
  • Бендер, Майкл А .; Farach-Колтон, Martin (2000), "Проблема LCA вновь", Труды 4 - й Латиноамериканской симпозиум по теоретической информатике , Lecture Notes в области компьютерных наук , 1776 , Springer-Verlag, стр.  88-94 , DOI : 10.1007 / 10719839_9 , ISBN 978-3-540-67306-4.
  • Бендер, Майкл А .; Фарач-Колтон, Мартин ; Пеммасани, Гиридхар; Скиена, Стивен ; Сумазин, Павел (2005), «Наименьшие общие предки в деревьях и ориентированных ациклических графах» (PDF) , Журнал алгоритмов , 57 (2): 75–94, DOI : 10.1016 / j.jalgor.2005.08.001.
  • Беркман, Омер; Vishkin, Узи (1993), "Рекурсивный Star-Tree параллельная структура данных" , SIAM журнал по вычислениям , 22 (2): 221-242, DOI : 10,1137 / 0222017.
  • Даш, Сантану Кумар; Шольц, Свен-Бодо; Херхут, Стефан; Кристиансон, Брюс (2013), «Масштабируемый подход к вычислению репрезентативного наименьшего общего предка в ориентированных ациклических графах» (PDF) , Теоретическая информатика , 513 : 25–37, DOI : 10.1016 / j.tcs.2013.09.030 , hdl : 2299/12152
  • Джиджев, Христо Н .; Pantziou, Grammati E .; Саролиагис, Христос Д. (1991), "Вычисление кратчайших путей и расстояний в плоских графах", Автоматы, языки и программирование: 18-й Международный коллоквиум, Мадрид, Испания, 8–12 июля 1991 г., Труды , Лекционные заметки по компьютерным наукам, 510 ., Springer, С. 327-338, DOI : 10.1007 / 3-540-54233-7_145 , ISBN 978-3-540-54233-9.
  • Фишер, Йоханнес; Хойн, Волкер (2006), «Теоретические и практические улучшения проблемы RMQ, с приложениями к LCA и LCE», Труды 17-го ежегодного симпозиума по комбинаторному сопоставлению с образцом , Lecture Notes in Computer Science, 4009 , Springer-Verlag, pp. . 36-48, CiteSeerX  10.1.1.64.5439 , DOI : 10.1007 / 11780441_5 , ISBN 978-3-540-35455-0.
  • Габоу, Гарольд Н .; Бентли, Джон Луи ; Тарьян, Роберт Э. (1984), "Масштабирование и связанные с ним методы для геометрических задач", STOC '84: Proc. Шестнадцатый ACM симпозиум по теории вычислений , Нью - Йорк, штат Нью - Йорк, США:. АКМ, С. 135-143, DOI : 10,1145 / 800057,808675 , ISBN 978-0897911337.
  • Харел, Дов; Тарьян, Роберт Е. (1984), "Быстрые алгоритмы поиска ближайших общих предков", SIAM журнал по вычислениям , 13 (2): 338-355, DOI : 10,1137 / 0213024.
  • Ковалук, Мирослав; Лингас, Анджей (2005), «LCA-запросы в ориентированных ациклических графах», в Кайресе, Луис; Итальяно, Джузеппе Ф .; Монтейро, Луис; Паламидесси, Катуша; Юнг, Моти (ред.), Автоматы, языки и программирование, 32-й международный коллоквиум, ICALP 2005, Лиссабон, Португалия, 11-15 июля 2005 г., Proceedings , Lecture Notes in Computer Science, 3580 , Springer, pp.  241–248 , CiteSeerX  10.1.1.460.6923 , DOI : 10.1007 / 11523468_20 , ISBN 978-3-540-27580-0
  • Шибер, Барух; Vishkin, Узи (1988), "О нахождении низких общих предков: упрощение и распараллеливания", SIAM журнал по вычислениям , 17 (6): 1253-1262, DOI : 10,1137 / 0217079.
  • Слеатор, ДД ; Tarjan, RE (1983), "Структура данных для динамических деревьев", Труды тринадцатого ежегодного симпозиума ACM по теории вычислений - STOC '81 (PDF) , стр. 114, DOI : 10,1145 / 800076,802464

Внешние ссылки [ править ]

  • Самый низкий общий предок двоичного дерева поиска , Камаль Рават
  • Реализация Python алгоритма Бендера и Фараха-Колтона для деревьев , автор Дэвид Эппштейн
  • Реализация Python для произвольно направленных ациклических графов
  • Конспект лекций по LCA из курса MIT Data Structures 2003 . Курс Эрика Демейна , заметки написали Лоизос Майкл и Христос Капуцис. Заметки о предложении того же курса 2007 года , написанные Элисон Циховлас.
  • Самые низкие общий предок в бинарных деревьев в C . Упрощенная версия техники Шибера – Вишкина, которая работает только для сбалансированных бинарных деревьев.
  • Видео от Дональда Кнута объясняя технику Шибер-Vishkin
  • Минимальный запрос диапазона и статья о наименьшем общем предке в Topcoder
  • Документация к пакету lca для Haskell от Эдварда Кметта, который включает алгоритм асимметрично-двоичного списка произвольного доступа. Чисто функциональные структуры данных для он-лайн слайдов LCA для того же пакета.