Как реализовать алгоритм Прима с кучей Фибоначчи?

Я знаю алгоритм Прима и знаю его реализацию, но всегда пропускаю часть, которую хочу сейчас спросить. Было написано, что реализация алгоритма Прима с кучей Фибоначчи O(E + V log(V)) и мой вопрос:

  • что такое куча Фибоначчи?
  • Как это реализовано? А также
  • Как вы можете реализовать алгоритм Прима с кучей Фибоначчи?
Источник

3 ответа

Решение

Куча Фибоначчи - это довольно сложная очередь с приоритетами, которая имеет отличное амортизированное асимптотическое поведение для всех своих операций - вставка, поиск-мин и ключ уменьшения - все выполняются за время амортизации O(1), тогда как операции удаления и извлечения-мин выполняются в амортизированном O (LG N) время. Если вы хотите получить хорошую справку по этому вопросу, я настоятельно рекомендую взять копию "Введение в алгоритмы, 2-е издание" CLRS и прочитать главу об этом. Это удивительно хорошо написано и очень показательно. Оригинальная статья Фредмана и Тарьяна о кучах Фибоначчи доступна в Интернете, и вы можете проверить ее. Он плотный, но хорошо обрабатывает материал.

Если вы хотите увидеть реализацию куч Фибоначчи и алгоритма Прима, я должен дать бесстыдный плагин для моих собственных реализаций:

  1. Моя реализация кучи Фибоначчи.
  2. Моя реализация алгоритма Прима с использованием кучи Фибоначчи.

Комментарии в обеих этих реализациях должны дать довольно хорошее описание того, как они работают; дайте мне знать, если я могу что-то сделать, чтобы уточнить!

Источник

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

Итак, времена, которые мы получаем:
Фибоначчи:
Выбор минимального ребра = O (время удаления минимума) = O (log (E)) = O (log (V))
Вставка ребер в кучу = O (время вставки элемента в кучу) = 1

Мин куча:
Выбор минимального ребра = O (время удаления минимума из кучи) = O (log (E)) = O (log (V))
Вставка ребер в кучу = O (время вставки элемента в кучу) = O (log (E)) = O (log (V))

(Помните, что E =~ V^2 ... так что log(E) == log(V^2) == 2Log(V) = O(log(V))

Итак, всего у вас есть E вставок и V минимальных выборов (в конце концов, это дерево).

Таким образом, в Мин куче вы получите:

O (Vlog (V) + Elog (V)) == O (Elog (V))

А в куче Фибоначчи вы получите:

O (Vlog (V) + E)

Источник

Я реализовал Dijkstra с использованием куч Фибоначчи несколько лет назад, и проблема довольно похожа. По сути, преимущество кучи Фибоначчи состоит в том, что она делает нахождение минимума множества постоянной операцией; так что это очень подходит для Prim и Dijkstra, где на каждом шаге вы должны выполнить эту операцию.

Почему это хорошо

Сложность этих алгоритмов, использующих биномиальную кучу (которая является более "стандартным" способом), составляет O(E * log V), потому что - примерно - вы будете пробовать каждое ребро (E), и для каждого из них вы будете либо добавлять новая вершина к вашей биномиальной куче (log V) или уменьшите ее ключ (log V), а затем должны найти минимум вашей кучи (еще один log V).

Вместо этого, когда вы используете кучу Фибоначчи, стоимость вставки вершины или уменьшения ее ключа в куче постоянна, поэтому у вас есть только O(E) для этого. НО удаление вершины - это O(log V), так как в конце будет удалена каждая вершина, которая добавляет O(V * log V) для общего O(E + V * log V).

Поэтому, если ваш график достаточно плотный (например, E >> V), использование кучи Фибоначчи лучше, чем биномиальной кучи.

Как

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

Единственная сложная часть заключается в реализации фактической кучи Фибоначчи.

Я не могу дать вам все детали реализации здесь (это заняло бы страницы), но когда я сделал это, я сильно полагался на Введение в алгоритмы (Cormen et al). Если у вас его еще нет, но вас интересуют алгоритмы, я настоятельно рекомендую вам получить его копию! Он не зависит от языка и предоставляет подробные объяснения обо всех алгоритмах стандартов, а также их доказательства, и, безусловно, расширит ваши знания и способность использовать все из них, а также разрабатывать и доказывать новые. Этот PDF-файл (со страницы Википедии, на который вы ссылаетесь) содержит некоторые детали реализации, но он определенно не так понятен, как " Введение в алгоритмы".

У меня есть отчет и презентация, которую я написал после этого, которая объясняет немного, как действовать (для Дейкстры - см. Конец ppt для функций кучи Фибоначчи в псевдокоде), но все это на французском языке... и мой код написан на Caml (и на французском), поэтому я не уверен, поможет ли это!!! И если вы можете что-то понять, пожалуйста, будьте снисходительны, я только начинал программировать, поэтому мои навыки кодирования были довольно плохими в то время...

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