Алгоритмы, Программы | Олег Брагинский, Михаил Арно, Владимир Глотов
Построение минимального остовного дерева взвешенного связного неориентированного графа намного проще, чем кажется на первый взгляд. Основатель «Школы траблшутеров» Олег Брагинский, ученики Михаил Арно и Владимир Глотов бегло разбирают алгоритм Прима.
Алгоритм был открыт и подробно описан в 1930 году чешским математиком Войтехом Ярником. Из-за отсутствия скоростной передачи информации в эпоху того времени, подход был пересмотрен Робертом Примом в 1957 году, а в 1959 году его усовершенствовал Эдсгер Вибе Дейкстра.
В задачах подобного класса требуется объединить вершины графа таким образом, чтобы сумма взвешенных включённых рёбер была минимальной и не имела циклов. С понятиями остова и Минимального Остовного Дерева мы познакомились в ходе исследования алгоритма Краскала.
Итак, пусть на входе имеется неориентированный взвешенный граф. Фундаментальную задачу считаем неизменной и состоящей в нахождении остовного дерева минимального веса. Отличительной особенностью условия будет наличие заранее известной начальной вершины.
Реализация алгоритма Краскала начиналась c сортировки рёбер по неубыванию и продолжалась соединением вершин графа согласно первоначальному отсортированному списку. Фактически планировался прямой доступ к любой вершине графа на каждом этапе построения связей.
В алгоритме Прима в реальных условиях первая вершина задана инфраструктурной логистикой, и это отнюдь не означает, что вокруг данной точки окажутся самые маленькие по весу рёбра. Доступа к другим вершинам не имеем, но в ходе решения задачи непременно построим «мостик» и к ним.
Итак, сам алгоритм Прима состоит из трех шагов:
- Из вариативности путей, исходящих от стартовой вершины, выбираем минимальное по весу ребро, дотягиваясь до очередной точки.
- Из множества рёбер графа, один конец которых уже принадлежит дереву, выбираем путь наименьшего веса. Новое ребро присоединяем к дереву, если исключена цикличность.
- Продолжаем повторение второго шага, взращивая дерево до полного задействования всех исходных вершин графа.
В алгоритме Краскала может одновременно ветвиться несколько деревьев, которые позже объединятся. В Прима граф растёт с первого шага. Подход Краскала и Прима относят к категории «жадных» алгоритмов. Второй метод также имеет схожесть с алгоритмом Дейкстра.
При геологоразведке не мостят дорогу к отдалённым поисково-разведочным скважинам на дальнем горизонте месторождения. Начинают с ближайшей локации: пока идёт постройка дороги до других точек, на первых скважинах ведут активную работу по изучению перспектив участка недр:
Обеспечим доступ к первой вершине будущего графа. Первым шагом выберем минимальное ребро от начальной точки F. В правой таблице ниже отобразим пути, примыкающие к проложенному. В левой – отсортируем исходящие рёбра по весам от минимального к максимальному:
Найдём наименьшее по весу ребро GF и используем его, чтобы проложить первый участок дороги. Теперь в нашем распоряжении уже две вершины (F и G) и пять незадействованных рёбер, т.к. одно уже точно замостим. Каждый раз проводим сортировку путей, включая новые добавленные:
Ребро GJ оказывается минимальным из списка незадействованных путей, поэтому в нашем списке появляется третья вершина островного графа – J. Продолжаем обновлять списки доступных рёбер из рассматриваемых вершин, на каждом шаге прокладывая всё новые дороги:
Проверку на образование циклов начинаем при добавлении третьего ребра и более не прекращаем до финального свистка. Если появляется замкнутый маршрут, убираем образовавшее его ребро в сторону и упрямо движемся дальше по списку взвешенных путей.
Таким образом дотянемся до пяти скважин. При добавлении ребра FH задействуем новую вершину, при этом свежих путей для рассмотрения на следующем шаге в список не добавится: внесены в таблицу на более ранних шагах, так как вершины I-K-J-G располагаются вокруг точки H:
Приблизившись к финальному варианту, заметим, что ребро KH с небольшим весом во время прокладки дорог образовало бы цикл F-I-K-H-F. Поэтому такой путь не сможем включить в построение Минимального Остовного Дерева и подсветим в таблице красной строкой:
Невооружённым взглядом видно, что добрая половина рёбер из сформированного списка осталась незадействованной, здорово сэкономив капитальные затраты. Именно поэтому алгоритм Прима применяется там, где необходимо отыскать оптимальное связующее дерево или кратчайшую сеть.
Подобный подход широко используется для построения оптимальных структур:
- Телекоммуникация: для экономии соединяющих кабелей и минимизации задержек связи.
- Транспорт и логистика: поиск маршрутов для перевозки грузов между локациями.
- Электроэнергетика: расчёт оптимальных распределений между подстанциями.
- Строительство: планирование размещения дорог, мостов, трубопроводов.
- Анализ: кластеризация данных, выявление групп связанных объектов.