Алгоритмы, Логистика | Максим Голубь, Михаил Арно, Олег Брагинский
Построение минимального остовного дерева взвешенного связного неориентированного графа гораздо проще, чем может казаться ленивым-нерадивым! Основатель «Школы траблшутеров» Олег Брагинский, ученики Михаил Арно и Максим Голубь пройдут для вас кратчайший путь.
С развитием логистики, востребованной бумирущими индустриями, возникла задача прокладки асфальтовых и железных дорог между населёнными пунктами и точками производств. На помощь пришли учёные, подсказавшие формулировку проблемы: поиск оптимального остовного дерева.
В 1926-м году чешский математик Отакар Борувка в работе «O jistém problému minimálním» предложил метод развёртывания эффективной электрической сети для Моравии. Спустя 30 лет, в 1956 году Джозеф Краскал нашёл более элегантный алгоритм решения задач подобного класса.
Начнём с определений. Взвешенным называют граф с вершинами которым присвоен вес, имеющий физическую сущность (расстояние). Минимальным остовным деревом взвешенного графа считают вписанный в него незацикленный подграф, в состав которого входят рёбра с минимальным весом.
Не все знакомы с понятием остова, но в жизни сталкивались точно: каркасы высотных зданий, несущие конструкции сооружений, блоки заводских машин, стойки мудрёных механизмов, принимающие основные нагрузки и предназначенные для крепления навесных элементов.
Туристические палатки имеют каркас в виде альпенштоков и натяжных линей. Игрушечные модели кораблей собираются с киля и шпангоутов, образующих скелет будущего судна – миниатюры покорителя морей. Они-то и несут на себе остальные компоненты вплоть до штрихов такелажа.
Остовы можно найти не только в предметах, но и в закономерностях построения связей. К крупным городам ведут широкие магистрали, словно массивные кости, соединяющие наиболее важные узлы. К далёким деревенькам петляют не разбалованные пассажиропотоком робкие узкоколейки.
В классе подобных задач требуется объединить все вершины графа между собой таким образом, чтобы сумма взвешенных включённых рёбер была минимальна и не щеголяла петлями избыточных циклов. Под которыми понимается замкнутый маршрут, ведущий к повторному прохождению пути.
Алгоритм Краскала состоит из четырёх этапов:
- Сортируем рёбра по возрастанию весов: от минимального до максимального.
- Создаём итеративное множество, включая величины с наибольших.
- Избегаем образования циклических путей в создаваемом остове.
- Завершаем процесс при отсутствии вершин для добавления.
Предположим, заказчики из мэрии поставили задачу найти оптимальную схему прокладки дорог. Имеем набор объектов от A до L которые нужно соединить километровой лентой асфальта (1). Каждый отрезок имеет важность для муниципалитета, выраженную в виде цифрового значения.
Начнём с инвентаризации. Выпишем все возможные связи объектов и их значения-веса. Строкам зададим вид по образцу: Вершина 1, Вершина 2, Вес ребра. Полученные данные занесём в таблицу (2). Упорядочим набор, произведя сортировку по столбцу «Вес» в порядке возрастания (3).
Найдём связи с малыми весом и соединим их вершины между собой. Первым на очереди будут C и K с весом равным трём (4), D и E с весом равным четырём (5) После каждого добавления ребра к будущему остову проверяем, не образовался ли цикл и повторяем поиск следующих вершин.
Продолжаем построение, добавляя новые рёбра JL (6) и HG (7). Не смущаемся разрозненностью и удалённостью, вычёркиваем вновь добавленные из начальной таблицы, наращивая скелет будущих дорог. Проверяем на отсутствие петель, любуемся наращиванием мощи союза Атлантов.
Зажигаются как гирлянды на ёлки новые связи. Растут группы отрезков: уверенно прокладывает новый путь AC (8). ВL и JG как крылья, расправляются в верхней части карты (9). Не отстаёт и правая коалиция, принимая в свои ряды FG, приютившуюся на периферийной части локации (10).
Завершающим этапом строим СE, EI, IH, стрелами соединяющие архипелаг «островков» остальных рёбер в единый и ладный скелет (11). Обратим внимание, что в обойме доступных связей в итоге оказалось больше половины, обеспечивающей экономию ресурсов при умной прокладке (12).
Заметим, что в некоторых случаях равенство веса некоторых рёбер вокруг одного графа на финальном шаге предлагает вариативность выбора, помогая автору взять на карандаш более оптимальное решение в случае, если станут известны дополнительные переменные.
Алгоритм Краскала относят к категории «жадных». Название обязывает: позволяет находить минимальное количество узлов, помогающее при малых «капитальных» затратах получать связанную конструкцию, прохождение по которой позволит обслужить сеть в приоритетном порядке.