Временная сложность проблемы алгоритма MST Прима
У меня есть проблема с графиком, где у нас есть:
- Имеется ровно н вершин и п-1 ребер.
- Все вершины связаны друг с другом – т.е. сеть состоит из только один связанный компонент. Таким образом, сеть представляет собой дерево.
- Все ребра имеют положительную длину (строго больше 0). Все края могут нести движение в обоих направлениях.
- Мне задано кратчайшее расстояние пути между каждой парой вершин.
Более формально: пусть реальная сеть вершин будет деревом Т. Учитывая только Кратчайшие расстояния пути Т, вы должны восстановить исходную сеть Т.
Вход: Матрица расстояний п × пЧАС с Hi,j = δT (i,j), где T — фактическое сеть вершин, а δT — кратчайшее расстояние пути между вершины я и Дж в Т.
Выход: ребра п-1Т.
Пример:
•T — фактическая вершинная сеть.
•H — матрица расстояний кратчайшего пути п × п.
•G(H) — полный граф на узлах н, где ребро (i,j) имеет вес Hi,j – т. е. кратчайшее расстояние пути в T.
Мой вопрос о сложности времени:
Каково время работы алгоритма в результате запуска алгоритма Prim на входе и возврата списка ребер в виде функции п? (Обратите внимание, что |E(G(H))|= Θ(n2)). Следует ли здесь использовать амортизированный анализ? Я не совсем уверен.
@kcsquared - это обычный алгоритм Прима, поэтому я думаю, что мне просто нужно найти сложность для общего случая, которую другой парень Пьетро сказал в своем ответе, хотя я нахожу его ответ немного запутанным.
@kcsquared я добавил свой ответ, который я сформулировал в своем посте, можете ли вы проверить, правильно ли он?
Спасибо за добавление дополнительной информации, это полезно. Ответ говорит, что H (матрица прил.) имеет n членов, это опечатка? Кроме того, реализация Прима с прил. матрица, о которой я знаю (например, этот), не изменяет этот прил. матрица вообще. Вам просто нужен отдельный 1D-список длины n, который отслеживает текущие минимальные расстояния (и набор для вершин уже в MST). Этот алгоритм работает в тета (n ^ 2) времени.
@kcsquared хм, да, я понял, что совершил ошибку. Это должно быть входной информацией для моей конкретной проблемы, не могли бы вы помочь мне правильно ее сформулировать? Ввод должен быть тем, который я указал жирным шрифтом в сообщении вверху. например, "Матрица H размера n x n с ..."
@kcsquared, потому что в моей конкретной проблеме с входными данными кажется, что как есть (см. Это выше в исходном вопросе), это отличается от общего случая? Поскольку наше «кратчайшее расстояние пути» является частью нашей матрицы смежности
Вы все еще можете использовать ту же формулировку и алгоритм: полный граф будет иметь уникальный MST, который является исходным деревом. Тот факт, что ввод поступил из матрицы расстояний, которую вы рассматриваете как матрицу смежности, похоже, не влияет на алгоритм Прима по сравнению с обычным использованием матрицы смежности.
@kcsquared В таком случае моя формулировка верна или я сделал что-то не так? Может быть, мне следует просто назвать это матрицей кратчайшего пути вместо матрицы смежности? Я предполагаю, что тогда у него n x n членов, изменит ли это время выполнения?
Ваше первоначальное описание проблемы и обращение с матрицей расстояний как с матрицей смежности полного графа кажется прекрасным и совершенно логичным. MST этого полного графа — это дерево, которое вам нужно, и Prim будет правильно возвращать его. Часть, которая неясна, связана только с изображением текста, который вы разместили. «Массив расстояний» в Prim, иногда называемый «затратами» или «ключами», отличается от вашей матрицы расстояний/смежности. Это одномерный список текущего самого дешевого подключения каждой вершины к MST. Я опубликую ответ с более подробной информацией и псевдокодом для всего алгоритма.
@kcsquared, если вы имеете в виду ответ, который я добавил, то не обращайте на это внимания, я думаю, я был неправ, но чтобы прояснить ситуацию: традиционно алгоритм Прима имеет матрицу смежности и массив расстояний, которые в сумме составляют время выполнения O (n ^ 2) ОДНАКО, в моем случае матрица «смежности» представляет собой матрицу расстояний по кратчайшему пути. Я не уверен, изменит ли это время выполнения и как бы я описал это в этом случае.
Ответы 1
Временная сложность алгоритма Прима, использующего матрицу смежности полного графа, равна Theta(n^2). Мы можем видеть это из псевдокода алгоритма Прима с нашей матрицей смежности H:
- Инициализировать набор
Qвершин не в дереве, изначально все вершины. Выберите первую вершину, которая будет нашим корнемR. - Инициализируйте два массива длины
n,keyиparent.keyсохранит в позицииiребро минимального веса, соединяющееi-ю вершину с текущим MST; изначально это +бесконечность.parentбудет хранить после выполнения алгоритма родителя каждой вершины в MST с корнем вR. Изначальноparent[i] = Rдля всехi, кроме корня, у которого нет родителя. - Зациклите первую строку
H(соответствует корнюR) и назначьтеkey[i] = H[0][i]. УдалитеRиз нашего набораQ. - Пока
Qне пусто:- Зациклитесь на
Qи извлеките любую вершинуuс минимальнымkey[u] - Для каждой вершины
vот 0 до n-1:- Если
vвQиH[u][v] < key[v]:- Установить
key[v]=H[u][v] - Установить
parent[v]=u
- Установить
- Если
- Зациклитесь на
Здесь цикл в (4) выполняется n-1 раз, а внутри цикла мы делаем Theta(n) работу. В сумме это дает время выполнения Theta(n^2), что является оптимальным для любого алгоритма, которому необходимо прочитать всю матрицу смежности. В частности, для общего полного графа это оптимально, но это не означает, что алгоритм Прима оптимален для вашего конкретного случая с более узким классом графов, сформированных из матриц расстояний.
Чтобы показать, что ваше преобразование задачи правильное, нам нужно убедиться, что для дерева T с положительными весами полный граф G(H), сформированный путем использования матрицы расстояний T в качестве матрицы смежности, будет удовлетворять:
G(H)имеет уникальное минимальное остовное деревоTявляется минимальным остовным деревомG(H).
Это требует доказательства нескольких свойств минимальных остовных деревьев в целом. Одна теорема о минимальных остовных деревьях, доказанная как следствие 3.5 в эти конспекты лекций Массачусетского технологического института, гласит, что:
Let
G = (V,E,w)be a connected, weighted, undirected graph. LetTbe any MST and let(U, V \ U)be any cut. ThenTcontains a light edge for the cut.
Здесь «легкое ребро для разреза (U, V \ U)» означает ребро, вес которого равен минимальному весу всех ребер с ровно одним концом в U.
Теперь нам просто нужно выбрать подходящие сокращения, чтобы доказать, что мы хотим. Для произвольного ребра e в исходном дереве T рассмотрим два дерева T1 и T2, которые мы получили, удалив e.
Возьмите вершины T1, которые мы будем называть V(T1), как наш разрез. Нам нужно показать, что в полном графе G(H) ребро e является единственным светлым ребром для этого разреза. В нашем исходном дереве Te — единственное ребро, пересекающее разрез. Это означает, что любой путь с одной конечной точкой u в V(T1) и другой конечной точкой v в V(T2) должен включать e.
Поскольку все веса положительны, это означает, что расстояние в T равно distance(u,v) > weight(e) для любого u, v such that (u in V(T1), v in V(T2), and (u, v) != e). Поскольку расстояние в T между u и v — это вес ребра (u, v) в нашем полном графе G(H), это означает, что e — единственное ребро минимального веса, пересекающее разрез. Поскольку e было произвольным ребром в T, теперь это означает, что все ребра T должны быть в нашем MST для G(H), поэтому уникальным MST G(H) является T.
Можете ли вы уточнить, какую реализацию алгоритма Прима вы используете? Для полного графа нет специальных вычислений, которые отличали бы ваши входные данные для задачи от других графов, за исключением того, что мы знаем, что |E| равно Θ(n^2). обычные ограничения времени выполнения применяется в зависимости от используемой структуры данных.