Я знаю алгоритм Прима и знаю его реализацию, но всегда пропускаю ту часть, которую хочу спросите сейчас. Было написано, что реализация алгоритма Прима с кучей Фибоначчи O(E + V log(V)) и мой вопрос: < / сильный>
Куча Фибоначчи - это довольно сложная очередь с приоритетами, которая имеет отличное амортизированное асимптотическое поведение для всех своих операций - вставка, поиск-мин и уменьшение ключа выполняются за O (1) амортизированное время, а удаление и извлечение-мин - за амортизированное O. (lg n) время. Если вам нужна хорошая справочная информация по этому вопросу, я настоятельно рекомендую взять копию «Введение в алгоритмы, 2-е издание» от CLRS и прочитать соответствующую главу. Он замечательно написан и очень нагляден. Оригинальная статья Фредмана и Тарьяна о кучах Фибоначчи доступен в Интернете, и вы, возможно, захотите его проверить. Он плотный, но хорошо обрабатывает материал.
Если вы хотите увидеть реализацию кучи Фибоначчи и алгоритма Прима, я должен дать бесстыдный плагин для моих собственных реализаций:
Комментарии в обеих реализациях должны дать довольно хорошее описание того, как они работают; дайте мне знать, если я могу что-нибудь уточнить!
Алгоритм Прима выбирает ребро с наименьшим весом между группой уже выбранных вершин и остальными вершинами.
Итак, чтобы реализовать алгоритм Прима, вам понадобится минимальная куча. Каждый раз, когда вы выбираете ребро, вы добавляете новую вершину в группу вершин, которую вы уже выбрали, и все ее смежные ребра попадают в кучу.
Затем вы снова выбираете ребро с минимальным значением из кучи.
Итак, временные сложности, которые мы получаем:
Фибоначчи:
Выбор минимального края = O (время удаления минимума) = O (log (E)) = O (log (V))
Вставка ребер в кучу = O (время вставки элемента в кучу) = 1
Мин. Куча:
Выбор минимального края = O (время удаления минимума из кучи) = O (log (E)) = O (log (V))
Вставка ребер в кучу = O (время вставки элемента в кучу) = O (журнал (E)) = O (журнал (V))
(Помните, что E = ~ V ^ 2 ... поэтому log (E) == log (V ^ 2) == 2Log (V) = O (log (V))
Итак, всего у вас есть E вставок и минимум V вариантов выбора (в конце концов, это дерево).
Итак, в куче Min вы получите:
O (Vlog (V) + Elog (V)) == O (Elog (V))
А в куче Фибоначчи вы получите:
O (Vlog (V) + E)
Я реализовал Дейкстру с использованием кучи Фибоначчи несколько лет назад, и проблема очень похожа. По сути, преимущество кучи Фибоначчи состоит в том, что она делает поиск минимума набора постоянной операцией; так что это очень подходит для Прима и Дейкстры, где на каждом этапе вы должны выполнять эту операцию.
Почему это хорошо
Сложность этих алгоритмов, использующих биномиальную кучу (что является более «стандартным» способом), составляет O (E * log V), потому что - грубо - вы попробуете каждое ребро (E), и для каждого из них вы либо добавите новую вершину в вашу биномиальную кучу (журнал V) или уменьшите ее ключ (журнал V), а затем вам нужно найти минимум вашей кучи (другой журнал V).
Вместо этого, когда вы используете кучу Фибоначчи, стоимость вставки вершины или уменьшения ее ключа в вашей куче постоянна, поэтому для этого у вас есть только O (E). НО удаление вершины - это O (log V), поэтому, поскольку в конце будет удалена каждая вершина, которая добавляет O (V * log V), всего O (E + V * log V).
Поэтому, если ваш график достаточно плотный (например, E >> V), использование кучи Фибоначчи лучше, чем биномиальная куча.
Как сделать
Таким образом, идея состоит в том, чтобы использовать кучу Фибоначчи для хранения всех вершин, доступных из уже построенного поддерева, индексированных по весу наименьшего ребра, ведущего к нему. Если вы разобрались в реализации или алгоритме Прима с использованием другой структуры данных, нет никаких реальных трудностей в использовании вместо этого кучи Фибоначчи - просто используйте методы insert и deletemin кучи. как обычно, и используйте метод reducekey для обновления вершины, когда вы отпускаете ребро, ведущее к ней.
Единственная сложная часть - это реализовать фактическую кучу Фибоначчи.
Я не могу предоставить вам все подробности реализации здесь (для этого потребуются страницы), но когда я делал свою, я сильно полагался на Введение в алгоритмы (Кормен и др.). Если у вас его еще нет, но вы интересуетесь алгоритмами, я настоятельно рекомендую вам получить его копию! Он не зависит от языка и предоставляет подробные объяснения всех стандартных алгоритмов, а также их доказательства, и определенно повысит ваши знания и способность использовать все из них, а также разрабатывать и проверять новые алгоритмы. Этот PDF-файл (со страницы Википедии, на которую вы указали ) предоставляет некоторые детали реализации, но они определенно не так ясны, как Введение в алгоритмы.
У меня есть отчет и презентация Я написал после этого, что немного объясняет, как действовать (для Дейкстры - см. Куча Фибоначчи работает в псевдокоде), но все на французском ... и мой код находится на Caml (и французском), поэтому я не уверен, что это поможет !!! И если вы понимаете что-то из этого, пожалуйста, проявите снисходительность, я только начинал программировать, поэтому мои навыки программирования в то время были довольно плохими ...
