Публикация Школы траблшутеров

Добраться до карибских ритмов помогут Дейкстры алгоритмы

Время чтения: 8 мин 10 сек
22 июня 2023 г. Просмотров: 315

Алгоритмы, Логистика | Валерий Хлебнов, Даниил Шмитт, Олег Брагинский

Навигация в мегаполисах важна пассажирам и водителям. Грузоперевозчики озабочены континентальными маршрутами. Основатель «Школы траблшутеров» Олег Брагинский, партнёр Даниил Шмитт и ученик Валерий Хлебнов описывают основы логистических изысков.

Навигатор 2ГИС, Яндекс.Пробки, Google Maps и подражатели взвалили на себя бремя планирования и оптимизации пассажиропотока в крупных городах и между ними. Водители не представляют поездки без смартфона или другого электронного автомобильного помощника.

Ушли в забвение времена бумажных карт и атласов, бережно хранящихся в бардачках шофёров, которые до поездки аккуратно отмечали карандашом необходимые магистрали, повороты и места отдыха. Дальнобойщики ориентировались по памяти, монотонно повторяя заученные маршруты.

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

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

Нидерландский учёный Эдсгер Вибе Дейкстра (1930-2002) озаботился поиском оптимального маршрута из пункта «А» в пункт «Б». Выбрал приоритетом разработку алгоритма, позволяющего найти кратчайший путь за минимальное время, избегая полного перебора возможных вариантов.

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

В качестве примера взяли полигонометрическую сеть с 14 вершинами. Жёлтым подписали рёбра – указанные числа отражают время в минутах для преодоления дистанции между точками. Белым пронумеровали узлы транспортного маршрута с задачей поскорее добраться из «1» в «14»:

Расчёты и записи вели в таблице справа от паутины:

  • Т         – номер отправной точки
  • Н         – время, за которое можно быстрее всего доехать до узла «Т»
  • 2..14    – номера вершин, до которых можно добраться из «Т»: под ними пишем минимальное время, за которое можно в них оказаться – не обязательно прокладывать путь через «Т»
  • Путь    – схематичная запись наикратчайшего маршрута в строке.

До точки «1» можно доехать без временных затрат, поэтому «Н» равно нулю. Со старта доступны четыре варианта движения: ставим жёлтые прочерки под прочими вершинами, а под возможными – записываем время пути. Лучший результат отмечаем зелёным, заполняем последний столбец:

В следующей строчке «Н» будет равно пяти: в узле «4» быстрее оказаться невозможно. Заполняем время под доступными вариантами, переносим с предыдущих строк те, что не побывали в столбце «Путь». Обращаем внимание, что в «3» быстрее всего прибыть можно за 12 минут из «1»:

Оказалось, что двигаться из «1» в «4» и дальше – не так выгодно, как из «1» в «3». Но это не значит, что в будущем на «4» табу: может статься лучшей промежуточной точкой, чтобы добраться до «6», «10» или «5». Важен победитель итогового расчёта, а не текущих предварительных вычислений:

Нет необходимости заново искать путь до «3»: знаем, что самый быстрый – «1-3». Также обстоят дела с «4», поэтому под ними в четвёртой строке ставим красные крестики, как и под теми вершинами, что повторяются с «Т» – до них тоже добираться не нужно:

На предыдущем шаге выяснилось, что вершина «5», ранее проигравшая прочим, на самом деле – более выгодный вариант для быстрого продвижения вглубь. Отметим, что вершины алгоритма просчитываются единожды: нет возможности дублировать их в столбце «Т»:

На шестом этапе отбрасывается затея двигаться поверху: на 11 минут оказывается выгоднее путь через «9». Открываются новые горизонты и пересадочные станции, неумолимо приближается заветная финальная вершина – вкус победы уже чувствуется на губах:

«2», «3», «4», «5», «6» уже побывали в последнем столбце – ставим под ними красные кресты. Из «Т» ещё можно попасть в «7», «8», «10», «11» и «14». С предыдущих этапов спускаем время для «12» – нижний «объездной» путь. Очередной расчёт – вот и «10» попадает в финальный столбец:

Маршрут опять переигрался – хорошо, что это не застало в пути, а произошло «на суше»: в момент планирования будущей поездки. Досадно только одно – финальная вершина уже маячила на горизонте, но снова отдалилась. За оптимальную длительность приходится платить вычислениями:

На девятом этапе у новичков могут опуститься руки: снова топчемся у начала, оказываясь ближе к старту чем к финишу. Хоть раз применившие алгоритм безмятежны: уверовали в безотказность методики, понимают, что кривая так или иначе выведет к долгожданной вершине:

На десятом этапе у маршрутов появляются фанбазы: приверженцы верхнего пути досадуют: «Говорили же двигаться по внешней дуге!» Продвижение вперёд возвращает веру у новобранцев, впитавшим тонкости алгоритма благодаря многократному повторению расчётов:

Не даром говорят, что 13 – несчастливое число: умаявшиеся выводить маршруты и складывать в уме двузначные числа досадуют, что нельзя сделать операцию по смене «13» на «14»: ведь тогда можно было завершить упражнение и заявить, что быстрее чем за 47 минут до конца не добраться:

Эх, жаль нельзя полагаться на сохранённое в уме: путь через «8» оказывается тупиковым. Пока что есть один вариант добраться до финиша: 1-3-9-14, прочие – менее выгодные. Но ещё не просчитан маршрут через «13», выясняем что до этой вершины можно добраться за 47 минут:

9 минут «запаса» оказывается достаточно, чтобы обойти 1-3-9-14: теперь можно официально объявить, что кратчайший маршрут лежит через вершину «13». На последнем этапе расчёта может показаться, что остался один вариант, но это не так – выбирали между 52 и 56 «в уме»:

Так был найден наибыстрейший путь 1-4-10-12-13-14. Несмотря на количество узловых точек переломов и визуальной несуразности, алгоритм нашёл решение, аналогичное обходу дорожных пробок. В случае изменения временных значений отрезков расчёты повторяем в полном объёме:

Датский математик Кристиан Вульф-Нильсен не согласился с ограничениями алгоритма и попытался найти альтернативное решение: реальность в отличие от моделей не терпит упрощений. Отрицательные значения рёбер необходимы электрокарам, летательным аппаратам и биржам.

Подход был представлен на всеобщее обозрение в 2020 году, но до сих пор не признан научным сообществом. Охватывает большее количество атрибутов и объектов реального мира. Позволяет значительно снизить нагрузку на портативные вычислительные устройства.

Итоговая таблица проявила выгоду использования пошаговой инструкции Дейкстры. В рассмотренном примере решение было найдено за 60 итераций. Таблица имеет размерность в 169 ячейки. Получаем почти тройную выгоду по времени от полного перебора.

Алгоритмы упрощают жизнь посвящённым, минимизируя количество затрачиваемых ресурсов. Ищите истоки успеха в математических закономерностях, а не среди звёзд!