Алгоритм Примса - Википедия - Prims algorithm

График и дерево
алгоритмы поиска
Списки
похожие темы
Демонстрация алгоритма Прима, основанного на евклидовом расстоянии.

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

Алгоритм был разработан в 1930 г. Чешский математик Войтех Ярник[1] а позже переоткрыл и переиздал компьютерные ученые Роберт С. Прим в 1957 г.[2] и Эдсгер В. Дейкстра в 1959 г.[3] Поэтому его также иногда называют Алгоритм Ярника,[4] Алгоритм Прима – Ярника,[5] Алгоритм Прима – Дейкстры[6]или Алгоритм DJP.[7]

Другие известные алгоритмы решения этой проблемы включают: Алгоритм Краскала и Алгоритм Борувки.[8] Эти алгоритмы находят минимальный остовный лес в возможно несвязном графе; Напротив, самая основная форма алгоритма Прима находит только минимальные остовные деревья в связанных графах. Однако запуск алгоритма Прима отдельно для каждого связный компонент графа, его также можно использовать для поиска минимального остовного леса.[9] С точки зрения их асимптотических временная сложность, эти три алгоритма одинаково быстры для разреженные графики, но медленнее, чем другие более сложные алгоритмы.[7][6]Однако для достаточно плотных графов алгоритм Прима можно заставить работать в линейное время, соблюдение или улучшение временных рамок для других алгоритмов.[10]

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

Описание

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

  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 в другие вершины ш. Для каждого такого ребра, если ш все еще принадлежит Q и vw имеет меньший вес, чем C[ш] выполните следующие действия:
      1. Набор C[ш] к стоимости края vw
      2. Набор E[ш], чтобы указать на край vw.
  4. Возвращаться F

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

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

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

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

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

Структура данных минимального веса краяСложность времени (общая)
матрица смежности, поиск
двоичная куча и список смежности
Куча Фибоначчи и список смежности

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

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

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

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

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

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

Пусть дерево Y2 - граф, полученный удалением ребра ж от и добавление края е к дереву Y1. Легко показать, что дерево Y2 связно, имеет такое же количество ребер, что и дерево Y1, а суммарный вес его ребер не больше веса дерева Y1, поэтому это также минимальное остовное дерево графа п и он содержит край е и все ребра, добавленные перед ним при построении набора V. Повторите шаги выше, и мы в конечном итоге получим минимальное остовное дерево графа п это идентично дереву Y. Это показывает Y минимальное остовное дерево. Минимальное остовное дерево позволяет расширить первое подмножество подобласти до меньшего подмножества. Икс, который мы считаем минимальным.

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

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

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

  1. Назначьте каждому процессору множество последовательных вершин длины .
  2. Создайте C, E, F и Q, как в последовательный алгоритм и разделить C, E, а также граф между всеми процессорами таким образом, чтобы каждый процессор удерживал входящие ребра в свой набор вершин. Позволять , обозначить части C, E хранится на процессоре .
  3. Повторяйте следующие шаги, пока Q пусто:
    1. На каждом процессоре: найдите вершину имеющий минимальное значение в [] (локальное решение).
    2. Мин-уменьшить локальные решения для поиска вершины v имеющий минимально возможное значение C[v] (глобальное решение).
    3. Транслировать выбранный узел на каждый процессор.
    4. Добавлять v к F и если E[v] не является специальным значением флага, также добавьте E[v] к F.
    5. На каждом процессоре: обновить и как в последовательном алгоритме.
  4. Возвращаться F

Этот алгоритм обычно можно реализовать на распределенных машинах.[12] а также на машинах с общей памятью.[13] Это также было реализовано на графических процессорах (GPU).[14] Время работы , предполагая, что уменьшать и транслировать операции могут выполняться в .[12] Также был исследован вариант алгоритма Прима для машин с общей памятью, в котором последовательный алгоритм Прима выполняется параллельно, начиная с разных вершин.[15] Однако следует отметить, что существуют более сложные алгоритмы для решения распределенное минимальное остовное дерево проблема более эффективным способом.

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

Рекомендации

  1. ^ Ярник, В. (1930), "O jistém problému minimálním" [Об одной минимальной проблеме], Práce Moravské Přírodovědecké Společnosti (на чешском языке), 6 (4): 57–63, HDL:10338.dmlcz / 500726.
  2. ^ Прим, Р.С. (Ноябрь 1957 г.), «Сети кратчайших соединений и некоторые обобщения», Технический журнал Bell System, 36 (6): 1389–1401, Bibcode:1957BSTJ ... 36.1389P, Дои:10.1002 / j.1538-7305.1957.tb01515.x.
  3. ^ Дейкстра, Э. В. (Декабрь 1959 г.), «Заметка о двух проблемах, связанных с графиками» (PDF), Numerische Mathematik, 1 (1): 269–271, CiteSeerX  10.1.1.165.7577, Дои:10.1007 / BF01386390.
  4. ^ Седжвик, Роберт; Уэйн, Кевин Дэниел (2011), Алгоритмы (4-е изд.), Addison-Wesley, p. 628, г. ISBN  978-0-321-57351-3.
  5. ^ Розен, Кеннет (2011), Дискретная математика и ее приложения (7-е изд.), McGraw-Hill Science, стр. 798.
  6. ^ а б Черитон, Дэвид; Тарджан, Роберт Эндре (1976), «Нахождение минимальных остовных деревьев», SIAM Журнал по вычислениям, 5 (4): 724–742, Дои:10.1137/0205051, МИСТЕР  0446458.
  7. ^ а б Петти, Сет; Рамачандран, Виджая (январь 2002 г.), «Оптимальный алгоритм минимального остовного дерева» (PDF), Журнал ACM, 49 (1): 16–34, CiteSeerX  10.1.1.110.7670, Дои:10.1145/505241.505243, МИСТЕР  2148431.
  8. ^ Тарджан, Роберт Эндре (1983), "Глава 6. Минимальные остовные деревья. 6.2. Три классических алгоритма", Структуры данных и сетевые алгоритмы, Серия региональных конференций CBMS-NSF по прикладной математике, 44, Общество промышленной и прикладной математики, стр. 72–77.
  9. ^ Кепнер, Джереми; Гилберт, Джон (2011), Графовые алгоритмы на языке линейной алгебры, Программное обеспечение, среды и инструменты, 22, Общество промышленной и прикладной математики, п. 55, ISBN  9780898719901.
  10. ^ а б Тарджан (1983), п. 77.
  11. ^ Джонсон, Дональд Б. (Декабрь 1975 г.), «Приоритетные очереди с обновлением и поиском минимальных остовных деревьев», Письма об обработке информации, 4 (3): 53–57, Дои:10.1016/0020-0190(75)90001-0.
  12. ^ а б c Грама, Анант; Гупта, Аншул; Карипис, Джордж; Кумар, Випин (2003). Введение в параллельные вычисления. С. 444–446. ISBN  978-0201648652.
  13. ^ Куинн, Майкл Дж .; Део, Нарсинг (1984). «Алгоритмы параллельных графов». Опросы ACM Computing. 16 (3): 319–348. Дои:10.1145/2514.2515.
  14. ^ Ван, Вэй; Хуанг, Юнчжун; Го, Шаочжун (2011). «Разработка и реализация алгоритма Прима на базе графического процессора». Международный журнал современного образования и информатики 3.4.
  15. ^ Сетия, Рохит (2009). «Новый параллельный алгоритм для задачи минимального остовного дерева». Proc. Международная конференция по высокопроизводительным вычислениям (HiPC).

внешняя ссылка