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

Question

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

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

Answer 1

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

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

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

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

Answer 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)

Answer 3

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

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

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

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

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

Как

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

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

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

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