Изменение алгоритма минимального связующего дерева (MST)

Question

Мне задали следующий вопрос в интервью, и я не могу найти эффективное решение.

Вот проблема:

• Мы хотим построить сети, и нам дается c узлов / городов и D возможных ребер / соединений, сделанных дорогами. Края являются двунаправленными, и мы знаем стоимость края. Стоимость ребер может быть представлена ​​как d [i, j], что обозначает стоимость ребра ij. Обратите внимание, что не все c узлы могут быть напрямую связаны друг с другом (D - набор возможных ребер).

• Теперь нам дан список из k потенциальных ребер / соединений, которые имеют бесплатно. Тем не менее, вы можете выбрать только один край в списке из k ребер (например, получить бесплатное финансирование для строительства аэропорта между двумя городами).

Так что вопрос ... найти набор дорог (и один бесплатный аэропорт), который минимизирует общую стоимость, необходимую для построения сети, соединяющей все города в эффективном времени выполнения.

Короче говоря, решите проблему минимального связующего дерева, но там, где вы можете выбрать 1 ребро в списке из k потенциальных ребер, которые будут бесплатными. Я не уверен, как решить ... Я попытался найти все связующие деревья в порядке увеличения стоимости и выбора самой низкой стоимости, но я все еще не уверен, как рассмотреть один свободный край из списка потенциальных возможностей свободные края. Я также пытался найти MST потенциальных соединений D и затем настроить его в соответствии с параметрами в k, чтобы получить результат.

Спасибо за любую помощь!

Answer 1

Одной из идей было бы рассматривать ваш любимый алгоритм MST как черный ящик и подумать об изменении ребер на графике, прежде чем запрашивать MST. Например, вы можете попробовать что-то вроде этого:

for each edge in the list of possible free edges:
    make the graph G' formed by setting that edge cost to 0.
    compute the MST of G'

return the cheapest MST out of all the ones generated this way

Время выполнения этого подхода - O (kT (m, n)), где k - количество проверяемых ребер, а T (m, n). ) - это стоимость вычисления MST с использованием вашего любимого алгоритма черного ящика.

Мы можем добиться большего успеха, чем это. Существует хорошо известная проблема следующего вида:

Предположим, у вас есть MST T для графа G. Затем вы уменьшаете стоимость некоторого ребра {u, v}. Найдите MST T 'в новом графе G'.

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

Run a DFS in T starting at u until you find v.
If the heaviest edge on the path found this way costs more than {u, v}:
   Delete that edge.
   Add {u, v} to the spanning tree.
Return the resulting tree T'.

(Доказательство того, что эта работа утомительна, но выполнима.) Это даст алгоритм стоимости O (T (m, n) + kn), так как вы будете строить начальный MST (время T (m, n)), затем выполните k запусков DFS в дереве с n узлами.

Однако это потенциально может быть улучшено еще больше, если у вас все в порядке с использованием некоторых более сложных алгоритмов. В статье «О декартовых деревьях и минимальных запросах по дальности» Демейна и др. Показано, что за время O (n) можно предварительно обработать минимальное остовное дерево, чтобы во время O (1) выполнялись запросы вида «что является самое дешевое ребро на пути в этом дереве между узлами u и v? " во времени O (1). Поэтому вы могли бы построить эту структуру вместо того, чтобы выполнять DFS, чтобы найти узкое место между u и v, сократив общее время выполнения до O (T (m, n) + n + k). Учитывая, что T (m, n) очень низкое (самая известная граница - O (m α (m)), где α (m) - обратная функция Аккермана и меньше пяти для всех входных значений в выполнимом универсуме), это асимптотически очень быстрый алгоритм!

Answer 2

Сначала сгенерируйте MST. Теперь, если вы добавите свободный край, вы создадите ровно один цикл. Затем вы можете удалить самое тяжелое ребро в цикле, чтобы получить более дешевое дерево.

Чтобы найти лучшее дерево, которое вы можете сделать, добавив одно свободное ребро, вам нужно найти самое тяжелое ребро в MST, которое вы можете заменить со свободным.

Вы можете сделать это, проверяя по одному свободному ребру за раз:

1. Выберите свободный край
2. Найдите наименьшего общего предка в дерево (из произвольного root) смежных с ним вершин
3. Запомните самое тяжелое ребро на пути между вершинами свободного ребра

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

Чтобы ускорить шаги (2) и (3), вы можете запомнить глубину каждого узел и подключить его к нескольким предкам, как пропустить список. Затем вы можете выполнить эти шаги за O (log | V |), что приведет к общей сложности O ((| E | + k) log | V |), что довольно неплохо.

РЕДАКТИРОВАТЬ: еще более простой способ

Подумав немного, кажется, есть супер простой способ выяснить, какой свободный край использовать и какой край MST заменить.

Независимо от k возможных свободных ребер, вы строите MST из других ребер, используя алгоритм Крускала, но модифицируете обычную структуру данных несвязанных множеств следующим образом:

• Используйте объединение по размеру или ранг, но не сжатие пути. Затем каждая операция объединения устанавливает sh ровно одну ссылку и занимает O (log N) времени, а длина всех путей будет не более O (log N).
• Для каждой ссылки запомните индекс ребра, вызвавшего его создание.

Затем для каждого возможного свободного ребра вы можете пройти вверх по ссылкам в структуре непересекающихся множеств, чтобы точно определить, в какой точке его конечные точки были соединены с тот же связанный компонент. Вы получите индекс последнего необходимого ребра, т. Е. Тот, который он заменит, и свободный край с наибольшим целевым индексом замены - это тот, который вы должны использовать.