Я знаю алгоритм Prim, и я знаю его реализацию, но всегда пропускаю часть, которую я хочу задать сейчас. Было написано, что реализация алгоритма Prim с использованием кучи Фибоначчи O(E + V log(V)) и мой вопрос:
Фибоначчи кучи довольно сложна очередь приоритетом, который имеет отличные amoritzed асимптотическое поведение на всех своих операциях - вставка, поиск-мин, и уменьшить ключ все работать в O (1) амортизируются время, в то время удаления и извлечения-мин пробег в амортизированном времени O (lg n). Если вам нужна хорошая рекомендация по этому вопросу, я настоятельно рекомендую собрать копию "Введение в алгоритмы, второе издание" в CLRS и прочитать главу об этом. Это замечательно хорошо написано и очень показательно. Оригинальная статья о кучих Фибоначчи от Фредмана и Тарьяна доступна в Интернете, и вы можете проверить ее. Он плотный, но дает хорошую обработку материала.
Если вы хотите увидеть реализацию кучи Fibonacci и алгоритма Prim, я должен дать бесстыдную версию для моих собственных реализаций:
Комментарии в обеих этих реализациях должны содержать довольно хорошее описание того, как они работают; дайте мне знать, если что-нибудь, что я могу сделать, чтобы уточнить!
Примитный алгоритм выбирает край с самым низким весом между группой уже выбранных вихрей и остальными вихрями.
Поэтому для реализации алгоритма Prim вам нужна минимальная куча. Каждый раз, когда вы выбираете край, вы добавляете новый вихрь в группу вихрей, которую вы уже выбрали, и все ее смежные края попадают в кучу.
Затем вы выбираете край с минимальным значением снова из кучи.
Итак, время, которое мы получаем:
Фибоначчи:
Выбор минимального края = 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 минимальные выборки (это дерево в конце).
Итак, в Min heap вы получите:
O (Vlog (V) + Elog (V)) == O (Elog (V))
И в куче Фибоначчи вы получите:
O (Vlog (V) + E)
Я реализовал Dijkstra, используя кучи Fibonacci несколько лет назад, и проблема довольно похожа. В принципе, преимущество кучи Фибоначчи заключается в том, что он делает поиск минимума набора постоянной работы; так что это очень подходит для Prim и Dijkstra, где на каждом шаге вам нужно выполнить эту операцию.
Почему это хорошо
Сложность этих алгоритмов с использованием биномиальной кучи (которая является более "стандартным" способом) - это O (E * log V), потому что - грубо - вы будете пытаться использовать каждое ребро (E), и для каждого из них вы либо добавит новую вершину в вашу биномиальную кучу (log V), либо уменьшит ее ключ (журнал V), а затем найдет минимум вашей кучи (другой журнал V).
Вместо этого, когда вы используете кучу Фибоначчи, стоимость вставки вершины или уменьшения ее ключа в вашей куче постоянна, поэтому у вас есть только O (E). BUT удаляет вершину O (log V), так что в конце каждая вершина будет удалена, что добавит O (V * log V) для общего O (E + V * log V).
Итак, если ваш граф достаточно плотный (например, E → V), использование кучи Фибоначчи лучше, чем биномиальная куча.
Как
Идея заключается в том, чтобы использовать кучу Фибоначчи для хранения всех вершин, доступных из уже созданного поддерева, индексированного по весу наименьшего края, ведущего к нему. Если вы поняли реализацию или алгоритм Prim с использованием другой структуры данных, нет реальной трудности в использовании кучи Fibonacci вместо этого - просто используйте методы insert и deletemin кучи, как обычно, и используйте метод reducekey для обновления вершины когда вы отпустите край, ведущий к нему.
Единственная сложная задача - реализовать фактическую кучу Фибоначчи.
Я не могу дать вам все детали реализации здесь (это займет страницы), но когда я сделал это, я в значительной степени полагался на Введение в алгоритмы (Cormen и др.). Если у вас его еще нет, но вы заинтересованы в алгоритмах, я настоятельно рекомендую вам получить его копию! Это язык агностик, и он дает подробные объяснения по всем алгоритмам стандартов, а также их доказательствам и, безусловно, повысит ваши знания и умение использовать их все, а также спроектирует и докажет новые. Этот PDF (со страницы со ссылками на Википедии) содержит некоторые детали реализации, но это определенно не так ясно, как введение в алгоритмы.
У меня есть отчет и презентация Я написал после этого это немного объясняет, как действовать (для Дийкстры - см. конец ppt для функций кучи Фибоначчи в псевдокоде), но все это на французском языке... и мой code находится в Caml (и на французском языке), поэтому я не уверен, что это помогает!!! И если вы можете понять что-то из этого, пожалуйста, будьте снисходительны, я только начинал программировать, поэтому мои навыки кодирования были довольно плохими в то время...