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

Question

Я знаю Prim's algorithm, и я знаю его реализацию, но всегда пропущу часть, которую я хочу задать сейчас. Это было написано, что реализация алгоритма Прима с Fibonacci heap является O(E + V log(V)) и мой вопрос:

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

Answer 1

Фибоначчи кучи является довольно сложной приоритетной очереди, который имеет отличные amoritzed асимптотическое поведение на всех своих операций - вставка, поиск-мин, и уменьшение Все запускать в O (1) время амортизации, в то время как удаление и извлечение-мин запускаются в амортизированном O (lg n) времени. Если вам нужна хорошая рекомендация по этому вопросу, я настоятельно рекомендую собрать копию «Введение в алгоритмы, второе издание» в CLRS и прочитать главу об этом. Это замечательно хорошо написано и очень показательно. The original paper on Fibonacci heaps by Fredman and Tarjan доступен онлайн, и вы можете проверить его. Он плотный, но дает хорошее отношение к материалу.

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

1. My implementation of a Fibonacci heap.
2. My implementation of Prim's algorithm using a Fibonacci heap.

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

Answer 2

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

Так что раз мы получаем, являются:
Фибоначчи:
Выбор минимального края = O (время удаления минимум) = O (журнал (E)) = O (журнал (V))
Вставка края до кучи = 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 (видеоблог (V) + ELOG (V)) == O (ELOG (V))

А Фибоначчи кучи тебя» LL получить:

O (Видеолог (V) + E)

Answer 3

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

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

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

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

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

Как

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

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

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

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