Найти наиболее посещаемый узел на графике

Question

В графе N узлов, соединенных ровно N-1 ребрами. Существует ровно 1 кратчайший путь от одного узла к любому другому узлу. Узлы пронумерованы от 1 до N. Даны Q запросов, которые сообщают исходный узел и узлы назначения. Найдите наиболее посещаемый узел после прохождения этих Q путей. Например, скажем, Q=3 и 3 запроса:

1 5

2 4

3 1

Итак, перейдите от узла 1 к узлу 5, затем от узла 2 к узлу 4, затем от узла 3 к узлу 1. Наконец, найдите самый посещаемый узел после Q запросов. Поиск каждого пути и увеличение количества посещенных узлов - наивный подход. Интервьюер попросил меня оптимизировать его.

Answer 1

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

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

Итак, имея это в виду.,,

• Я вижу, что вы уже пометили свой вопрос с помощью [tree] и [наименьшего общего ответа], поэтому вы, вероятно, уже сделали самые большие наблюдения, а именно:
  • Граф это дерево. Мы можем произвольно выбрать "корень", так чтобы у каждого другого узла был "родитель", ненулевая "глубина", один или несколько "предков" и т. Д.
  • Как только мы это сделаем, кратчайший путь от узла a к узлу b состоит из узла a, узла b, всех предков a, которые не являются предками b, всех предков b, которые не являются предками a, и их "Наименьший общий предок". (Это остается верным, если a является предком b или наоборот: если a является предком b, то это наименьший общий предок a и b, и наоборот. Это даже остается верным, если a и b одинаковы.)
• Итак, мы можем сделать следующую предварительную обработку:
  • Представьте граф как отображение от каждого узла к списку его соседей. (Поскольку узлы пронумерованы от 1 до N, это отображение представляет собой массив из N списков.)
  • Выберите корневой узел.
  • Рассчитайте и сохраните "родителя" и "глубины" каждого узла. (Мы можем сделать это за O(N) время, используя поиск в глубину или поиск в ширину.)
  • Для каждой пары узлов рассчитайте и сохраните их "наименьшего общего предка". (Мы можем сделать это за общее время O(N²), используя результаты предыдущего шага и запоминания, потому что запоминание обеспечивает амортизацию.)
  • Инициализируйте сопоставление от каждого узла числу раз, которое является конечной точкой пути, и сопоставление от каждого узла количеству раз, когда он является наименьшим общим предком конечных точек пути. (Примечание: если данный путь от одного узла к самому себе, мы посчитаем, что это в два раза больше, чем это конечная точка пути, а также один раз, когда это последний общий предок конечных точек.)
• Для каждого запроса обновите два сопоставления. Мы можем сделать это за O(1) раз за запрос, всего за O(Q).
• В заключение:
  • Выполните обход графа по порядку, рассчитав количество путей, которые посетили этот узел. Логика для этого заключается в следующем: общее количество путей, которые посетили узел a, равно сумме числа путей, которые посетили каждый из его дочерних элементов, минус сумма количества раз, когда каждый из его дочерних элементов был последним общий предок конечной точки пути, плюс число раз, когда a сам был конечной точкой, минус количество раз, когда a сам был последним общим предком конечной точки пути (для отмены двойного счета).
  • Вернуть узел, для которого предыдущий шаг вернул наибольшее число. Если несколько узлов связаны для наибольшего, то.,, Я не знаю, формулировка проблемы была неопределенной по этому поводу, вам нужно будет спросить о требованиях.

В целом, для этого требуется O(N²) предварительная обработка, O(Q) обработка в реальном времени для каждого запроса и O(N) постобработка.

Если N достаточно велико, и мы ожидаем, что будет возможно, что только небольшое подмножество узлов было посещено хотя бы один раз, тогда мы можем ускорить постобработку, игнорируя невидимые части дерева. Это включает в себя поддержание набора узлов, которые были конечными точками путей, а затем выполнение постобработки "снизу вверх", запуск с самых глубоких таких узлов и перемещение "родительского узла" от данного узла, только если число посещенных путей этот узел меньше, чем количество раз, когда он был наименьшим общим предком. Если мы обозначим число различных конечных точек через P, а число различных посещенных узлов - через M, то это можно сделать чем-то вроде O(P log P + M).