Алгоритм Прима

Алгоритмы поиска по графам и деревьям
α – β А * B * Возврат Луч Беллман – Форд Лучший первый Двунаправленный Борувка Ветвь и граница BFS британский музей D * DFS Dijkstra Эдмондс Флойд – Уоршалл Поиск бахромы скалолазание ИДА* Итеративное углубление Джонсон Точка прыжка Крускал Лексикографическая BFS LPA * Prim SMA *
Списки
Алгоритмы графа Алгоритмы поиска Список алгоритмов графа
похожие темы
Динамическое программирование Обход графа Обход дерева Искать игры Раскраска графика
v т е

Демонстрация алгоритма Прима на основе евклидова расстояния

В информатике, алгоритм Примы (также известная как алгоритм Ярника) является жадным алгоритмом, который находит минимальное покрывающее дерево для взвешенного неориентированного графа. Это означает, что он находит подмножество ребер, которое формирует дерево, включающее каждую вершину, где общий вес всех ребер в дереве минимизирован. Алгоритм работает, строя это дерево по одной вершине за раз, из произвольной начальной вершины, на каждом шаге добавляя самое дешевое возможное соединение из дерева в другую вершину.

Алгоритм был разработан в 1930 году чешским математиком Ярник, а затем вновь и переиздана компьютерных ученых Роберт К. Прима в 1957 году и Дейкстра в 1959 г. Таким образом, он также иногда называют алгоритмом Ярника, Прима-Ярник алгоритм, Прима -Dijkstra алгоритм или алгоритм DJP.

Другие хорошо известные алгоритмы для этой задачи включают в себя алгоритм Крускала и алгоритм борувки. Эти алгоритмы находят минимальный остовной лес в возможно несвязном графе; Напротив, самая простая форма алгоритма Прима находит только минимальные остовные деревья в связанных графах. Однако, выполняя алгоритм Прима отдельно для каждого связного компонента графа, его также можно использовать для поиска минимального остовного леса. С точки зрения их асимптотической временной сложности эти три алгоритма одинаково быстры для разреженных графов, но медленнее, чем другие более сложные алгоритмы. Однако для достаточно плотных графов алгоритм Прима можно заставить работать в линейном времени, удовлетворяя или улучшая временные границы для других алгоритмов.

Алгоритм Прима начинается с вершины A. На третьем шаге ребра BD и AB имеют вес 2, поэтому BD выбирается произвольно. После этого шага AB больше не является кандидатом на добавление в дерево, потому что он связывает два узла, которые уже находятся в дереве.

СОДЕРЖАНИЕ

• 1 Описание
• 2 Временная сложность
• 3 Доказательство правильности
• 4 Параллельный алгоритм
• 5 См. Также
• 6 Ссылки
• 7 Внешние ссылки

Описание

Неформально алгоритм можно описать как выполнение следующих шагов:

1. Инициализируйте дерево с одной вершиной, произвольно выбранной из графа.
2. Вырастите дерево по одному ребру: из ребер, которые соединяют дерево с вершинами, которых еще нет в дереве, найдите ребро с минимальным весом и перенесите его в дерево.
3. Повторите шаг 2 (пока все вершины не окажутся в дереве).

Более подробно, это может быть реализовано с использованием псевдокода, приведенного ниже.

1. Свяжите с каждой вершиной v графа число C [ v ] (самая дешевая стоимость соединения с v) и ребро E [ v ] (ребро, обеспечивающее самое дешевое соединение). Чтобы инициализировать эти значения, установите все значения C [ v ] на + ∞ (или на любое число, превышающее максимальный вес ребра) и установите для каждого E [ v ] особое значение флага, указывающее, что нет ребра, соединяющего v с более ранним вершины.
2. Инициализируйте пустой лес F и набор Q вершин, которые еще не были включены в F (изначально все вершины).
3. Повторяйте следующие шаги, пока Q не станет пустым:
   1. Найдите и удалите вершину v из Q, имеющую минимально возможное значение C [ v ]
   2. Добавьте v к F и, если E [ v ] не является специальным значением флага, также добавьте E [ v ] к F
   3. Пройдем по ребрам vw, соединяющим v с другими вершинами w. Для каждого такого ребра, если w все еще принадлежит Q и vw имеет меньший вес, чем C [ w ], выполните следующие шаги:
      1. Установите C [ w ] равным стоимости ребра vw.
      2. Установите E [ w ], чтобы указать на край vw.
4. Возврат F

Как описано выше, начальная вершина для алгоритма будет выбрана произвольно, потому что первая итерация основного цикла алгоритма будет иметь набор вершин в Q, которые все имеют равные веса, и алгоритм автоматически запустит новое дерево в F, когда он завершает остовное дерево каждого связного компонента входного графа. Алгоритм может быть изменен так, чтобы он начинался с любой конкретной вершины s, задав для C [ s ] число меньшее, чем другие значения C (например, ноль), и его можно изменить, чтобы найти только одно связующее дерево, а не весь покрывающий лес (более точно соответствующий неформальному описанию), останавливаясь всякий раз, когда он встречает другую вершину, помеченную как не имеющую связанного ребра.

Различные варианты алгоритма отличаются друг от друга тем, как реализован набор Q: как простой связанный список или массив вершин, или как более сложная структура данных очереди приоритетов. Такой выбор приводит к различиям во временной сложности алгоритма. В общем, приоритетная очередь будет быстрее находить вершину v с минимальными затратами, но повлечет за собой более дорогие обновления при изменении значения C [ w ].

Сложность времени

Воспроизвести медиа Алгоритм Прима имеет множество применений, например, при создании этого лабиринта, который применяет алгоритм Прима к случайно взвешенному сеточному графу.

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

Структура данных минимального веса края	Сложность времени (общая)
матрица смежности, поиск	${\ Displaystyle O (| V | ^ {2})}$
двоичная куча и список смежности	${\ Displaystyle O ((| V | + | E |) \ log | V |) = O (| E | \ log | V |)}$
Куча Фибоначчи и список смежности	${\ Displaystyle O (| E | + | V | \ log | V |)}$

Простая реализация Prim, использующая матрицу смежности или представление графа списка смежности и линейный поиск по массиву весов для нахождения ребра минимального веса для добавления, требует времени выполнения O (| V | ²). Однако это время работы можно значительно улучшить, используя кучи для реализации поиска краев с минимальным весом во внутреннем цикле алгоритма.

Первая улучшенная версия использует кучу для хранения всех ребер входного графа, упорядоченных по их весу. Это приводит к наихудшему времени работы O (| E | log | E |). Но хранение вершин вместо ребер может улучшить его еще больше. Куча должна упорядочить вершины по наименьшему весу ребер, который соединяет их с любой вершиной в частично построенном минимальном остовном дереве (MST) (или бесконечности, если такое ребро не существует). Каждый раз, когда вершина v выбирается и добавляется к MST, операция уменьшения ключа выполняется для всех вершин w за пределами частичного MST, так что v соединяется с w, устанавливая ключ на минимум из его предыдущего значения и стоимости ребра из ( v, w).

Используя простую двоичную структуру данных кучи, теперь можно показать, что алгоритм Прима выполняется за время O (| E | log | V |), где | E | - количество ребер, а | V | количество вершин. Используя более сложную кучу Фибоначчи, это можно уменьшить до O (| E | + | V | log | V |), что асимптотически быстрее, когда граф достаточно плотный, чтобы | E | есть ω (| V |), и линейное время, когда | E | не меньше | V | журнал | V |. Для графов с еще большей плотностью (имеющих как минимум | V | ^c ребер для некоторого c  gt; 1) алгоритм Прима можно заставить работать в линейном времени еще проще, используя d- мерную кучу вместо кучи Фибоначчи.

Демонстрация доказательства. В этом случае график Y 1 = Y - е + е уже равно Y. В общем, процесс может потребоваться повторить.

Доказательство правильности

Пусть P - связный взвешенный граф. На каждой итерации алгоритма Прима должно быть найдено ребро, которое соединяет вершину в подграфе с вершиной вне подграфа. Поскольку точка P связна, к каждой вершине всегда будет путь. Выход Y алгоритма Прима представляет собой дерево, потому что ребро и вершина, добавленные к дереву Y, связаны. Пусть Y 1 - минимальное остовное дерево графа P. Если Y 1 = Y, то Y - минимальное остовное дерево. В противном случае пусть e будет первым ребром, добавленным во время построения дерева Y, которого нет в дереве Y 1, и пусть V будет набором вершин, соединенных ребрами, добавленными перед ребром e. Тогда одна конечная точка ребра e находится в множестве V, а другая - нет. Поскольку дерево Y 1 является остовным деревом графа P, в дереве Y 1 есть путь, соединяющий две конечные точки. Как один движется по пути, нужно столкнуться ребро е присоединения вершины в множестве V на тот, который не находится в множестве V. Теперь, на итерации, когда ребро e было добавлено к дереву Y, ребро f также могло быть добавлено, и оно было бы добавлено вместо ребра e, если его вес был меньше e, и поскольку ребро f не было добавлено, мы заключаем, что

${\ Displaystyle ш (е) \ geq ш (е).}$

Пусть tree Y 2 будет графом, полученным путем удаления ребра f и добавления ребра e к дереву Y 1. Легко показать, что дерево Y 2 связно, имеет такое же количество ребер, что и дерево Y 1, а суммарный вес его ребер не больше, чем у дерева Y 1, поэтому оно также является минимальным остовным деревом графа. Р и содержит ребро е и все ребра, добавленные перед ним во время строительства множества V. Повторите шаги, описанные выше, и в конечном итоге мы получим минимальный остовное дерево графа P, которая идентична дерево Y. Это показывает, что Y является минимальным остовным деревом. Минимальное остовное дерево позволяет расширить первое подмножество подобласти до меньшего подмножества X, которое мы считаем минимальным.

Параллельный алгоритм

Матрица смежности, распределенная между несколькими процессорами для параллельного алгоритма Prim. На каждой итерации алгоритма каждый процессор обновляет свою часть C, проверяя строку вновь вставленной вершины в своем наборе столбцов в матрице смежности. Затем собираются результаты, и следующая вершина для включения в MST выбирается глобально.

Основной цикл алгоритма Прима по своей сути является последовательным и, следовательно, не может быть распараллелен. Однако внутренний цикл, который определяет следующее ребро минимального веса, которое не образует цикл, можно распараллелить, разделив вершины и ребра между доступными процессорами. Следующий псевдокод демонстрирует это.

1. Назначьте каждому процессору набор последовательных вершин длины.${\ displaystyle P_ {i}}$${\ displaystyle V_ {i}}$${\ Displaystyle {\ tfrac {| V |} {| P |}}}$
2. Создайте C, E, F и Q, как в последовательном алгоритме, и разделите C, E, а также граф между всеми процессорами так, чтобы каждый процессор удерживал входящие ребра для своего набора вершин. Пусть, обозначает части C, E, хранящиеся на процессоре.${\ displaystyle C_ {i}}$${\ displaystyle E_ {i}}$${\ displaystyle P_ {i}}$
3. Повторяйте следующие шаги, пока Q не станет пустым:
   1. На каждом процессоре: найдите вершину, имеющую минимальное значение в [ ] (локальное решение).${\ displaystyle v_ {i}}$${\ displaystyle C_ {i}}$${\ displaystyle v_ {i}}$
   2. Минимизируйте локальные решения, чтобы найти вершину v, имеющую минимально возможное значение C [ v ] (глобальное решение).
   3. Передайте выбранный узел каждому процессору.
   4. Добавить V в F и, если E [ v ] не особое значение флага, а также добавить E [ v ] для F.
   5. На каждом процессоре: обновление и как в последовательном алгоритме.${\ displaystyle C_ {i}}$${\ displaystyle E_ {i}}$
4. Возврат F

Этот алгоритм обычно может быть реализован на распределенных машинах, а также на машинах с общей памятью. Это также было реализовано на графических процессорах (GPU). Время выполнения составляет, при условии, что операции сокращения и широковещательной передачи могут выполняться в. Также был исследован вариант алгоритма Прима для машин с общей памятью, в котором последовательный алгоритм Прима выполняется параллельно, начиная с разных вершин. Однако следует отметить, что существуют более сложные алгоритмы для более эффективного решения задачи распределенного минимального связующего дерева. ${\ Displaystyle O ({\ tfrac {| V | ^ {2}} {| P |}}) + O (| V | \ log | P |)}$${\ Displaystyle О (\ журнал | P |)}$

Смотрите также

• Алгоритм Дейкстры, очень похожий алгоритм для задачи о кратчайшем пути
• Гридоиды предлагают общий способ понять правильность алгоритма Прима.

использованная литература

внешние ссылки

• Прогресс алгоритма Прима по случайно распределенным точкам
• СМИ, связанные с алгоритмом Прима на Викискладе?