Как найти короткий путь между точками

Когда вы пользуетесь навигатором, вы указываете точку А и точку Б, и дальше навигатор как-то сам строит маршрут. Сегодня посмотрим, что лежит в основе алгоритма, который это делает. Просто ради интереса. 

Графы и «задача коммивояжёра»

Ещё до появления навигаторов у людей была такая же проблема: как найти кратчайший путь из одного места в другое, если есть ограниченное количество промежуточных точек? Или как объехать ограниченное количество точек, затратив минимальные усилия. В общем виде это называется «задачей коммивояжёра», и мы уже рассказывали, в чём там идея:

Если взять просто города и расстояния между ними, то с точки зрения математики это называется графом: города будут вершинами графа, а дороги между ними — рёбрами графа. Если мы знаем длину каждой дороги, то это будет значением (весом) рёбер графа. Этой теории нам уже хватит, чтобы понять, как работает навигатор в машине.

Алгоритм Дейкстры — ищем самый быстрый путь

Как только появилось решение полным перебором, математики стали искать другой подход, который работал бы гораздо быстрее и не требовал бы вычисления такого огромного объёма данных. В 1959 году Эдсгер Дейкстра придумал свой алгоритм, которым пользуются до сих пор. Идея его в том, чтобы не перебирать все варианты, а находить самый короткий путь только между соседними графами — и так, шаг за шагом, продвигаться к конечной точке.

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

Чтобы найти самый быстрый путь из А в Б, мы смотрим сначала, какие пути у нас выходят из точки А. Видно, что поехать вниз будет быстрее, чем поехать направо:

Значит, выбираем путь вниз. Теперь делаем то же самое для этой точки — смотрим, где быстрее: справа или внизу. Вниз быстрее (1 меньше, чем 4), поэтому едем по ней:

При этом мы не отбрасываем уже сделанные вычисления (всё равно уже посчитали), а запоминаем их на всякий случай. Из нижней точки есть только одна дорога — направо, поэтому едем по ней:

А теперь у нас получилась интересная ситуация: в центральную точку мы можем попасть как сверху, так и снизу, при этом и там, и там у нас одинаковое время — 3 минуты. Значит, посчитаем оба варианта — вдруг сверху будет быстрее и нам нужно будет перестроить маршрут заново:

Оказывается, снизу ехать до центра быстрее, чем сверху — 4 минуты вместо 6, поэтому оставляем нижний маршрут. Наконец, из центральной точки до точки Б всего один путь — направо, поэтому выбираем его:

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

Что ещё учитывает навигатор

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

Комфорт. Если нам нужно построить не самый быстрый, а самый комфортный маршрут, то мы можем отдать предпочтение автомагистралям и дорогам с несколькими полосами — на них обычно и асфальт получше, и резких поворотов поменьше. Чтобы навигатор выбирал именно такие дороги, им можно присвоить коэффициент 0,8 — это виртуально сократит время на дорогу по ним на 20%, а навигатор всегда выберет то, что быстрее. 

С просёлочными и грунтовыми дорогами ситуация обратная. Они редко бывают комфортными, а значит, им можно дать коэффициент 1,3, чтобы они казались алгоритму более долгими и он старался их избегать. А лесным дорогам можно поставить коэффициент 5 — навигатор их выберет, только если это единственная дорога то точки назначения.

Сложность маршрута и реальное время. Маршрут из А в Б почти никогда не бывает прямым — на нём всегда есть повороты, развороты и съезды, которые отнимают время. Чтобы навигатор это учитывал, в графы добавляют время прохождения поворота — либо коэффициентом, либо отдельным параметром. Из-за этого алгоритм будет искать действительно быстрый маршрут с учётом геометрии дорог.

Пробки. Если есть интернет, то всё просто: навигатор получает данные о состоянии дорог и добавляет разные коэффициенты в зависимости от загруженности. Иногда навигатор ведёт дворами, когда трасса свободна — это не ошибка навигатора, а его прогноз на время поездки: если через 10 минут в этом месте обычно собираются пробки, то там лучше не ехать, а заранее поехать в объезд.

Если интернета нет, то алгоритм просто использует усреднённую модель пробок на этом участке. Эта модель скачивается заранее и постоянно обновляется в фоновом режиме.

Как построить маршрут по всей России

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

Если мы в Яндекс Картах построим такой маршрут, то навигатор нам предложит сразу 4 варианта:

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

Например, если мы поедем в Тулу не из Брянска, а из Синезёрок, то поменяется только начальный маршрут по трассе М3, а всё остальное останется прежним:

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

Что дальше

Следующий этап — напишем алгоритм Дейкстры сами и посмотрим, как он работает по шагам.

Учимся находить кратчайший путь через простой двумерный алгоритм на Python

Как именно мы находим выход из лабиринта? Как быстрее всего проехать из точки А в ближайшую пиццерию? Можем ли мы провести игрового персонажа к выходу так, чтобы он не уперся в стену?

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

В этом руководстве рассмотрен простейший алгоритм поиска пути, основанный на алгоритме Дейкстры. Этот алгоритм также известен под названием поиск по первому наилучшему совпадению, ключевая логика у него общая со многими другими алгоритмами, например, A*, заливка методом наводнения и диаграммы Вороного.

Здесь мы рассмотрим практическое применение этого алгоритма. Вам понадобятся базовые знания программирования и языка Python.

Настройка Python

Весь код к этому посту находится в репозитории path-finding. Его нужно клонировать и переключиться в ветку tutorial_1. Также установите пакет pygame, он понадобится нам для графики.

python3 -m pip install -U pygame
git clone git@github.com:mortoray/path-finding.git
cd path-finding
git checkout path_finding_1

Теперь проверим, все ли сделали правильно:

python3 find-basic.py

Должно появиться окно с клетками, а в клетках – цифры. Теперь можете закрыть это окно. Мы вернемся к нему позже.

Лабиринт

Поиск пути – это продвижение из точки А в точку B. Алгоритм может описывать прогулку человека по парку, движение автомобиля по городу, либо курс персонажа, который преследует вас в игре. Давайте сведем все эти окружения к абстракции, которую назовем «лабиринт».

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

На схеме стартовая клетка обозначена желтым цветом, в ней стоит «0». Все допустимые шаги обозначены как «1». Мы должны перейти в зеленую клетку, это наша цель.

Запускаем код

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

import mortoray_path_finding as mpf

maze = mpf.create_wall_maze( 20, 12 )

Мы создали лабиринт размером 20x12. Поле maze.board – это решетка из объектов Cell. Нам нужен способ отобразить наш лабиринт.

finder = mpf.Finder()
finder.set_board(maze.board)
finder.run()

Исходный файл: tutorial_1_1.py

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

Измерение расстояния

Поиск пути во многом основан на исходном алгоритме Дейкстры. Существует множество его вариаций, например, алгоритм Флойда-Уоршелла, он же B*. Они действуют по схожему принципу: в них используются списки узлов и подсчитывается расстояние. Для разных ситуаций можно сочетать различные приемы.

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

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

1. Получаем из списка открытых узлов тот узел, от которого нас отделяет наименьшее расстояние  

2. Вычисляем расстояние до каждого из соседних узлов

3. Если расстояние до соседнего узла меньше, чем вычисленное – то добавляем этот узел в список открытых

Термины

Для начала рассмотрим некоторые термины, поскольку они могут быть вам неизвестны.

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

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

«Список открытых узлов» — это в буквальном смысле список узлов. «Открытые» узлы – это узлы, которые алгоритм все равно должен проверить. Например, если вы ищете елочные игрушки, разложенные в ящиках у вас в подвале, то вы просматриваете каждый из ящиков и отмечаете его в списке. Если внутри большого ящика обнаружатся более мелкие, то их также можно добавить в список.

Алгоритм

Алгоритм, реализованный в этой функции, называется fill_shortest_path. Держите его перед глазами, читая это объяснение. Эта функция непосредственно не находит кратчайший путь, а измеряет расстояние от стартовой позиции до других клеток в лабиринте. Позже мы рассмотрим, как эта информация используется для генерации пути.

def fill_shortest_path(board, start, end, max_distance = math.inf):
  nboard = board.clone()
  nboard.clear_count(math.inf)

«Список открытых узлов» – это вектор позиций в решетке. В нем содержатся все местоположения, необходимые нам для поиска пути. Инициализируем список стартовой позицией лабиринта. Также мы должны установить счетчик в 0, поскольку на старте расстояние равно нулю.

nboard.at( start ).count = 0
    
open_list = [ start ]

Этого достаточно, чтобы запустить алгоритм. Перебираем узлы, пока open_list не опустеет.

  while open_list:
    	cur_pos = open_list.pop(0)
    	cur_cell = nboard.at( cur_pos )

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

Для каждого узла рассмотрим всех его соседей.

# (x,y) смещения от текущей клетки
neighbours = [ [-1,0], [1,0], [0,-1], [0,1] ]
for neighbour in neighbours:
  ncell_pos = mpf.add_point(cur_pos, neighbour)
  if not nboard.is_valid_point(ncell_pos):
continue
  
  cell = nboard.at( ncell_pos )

Каждый элемент в neighbors – это Евклидово смещение от текущей клетки до соседней. Например, [-1,0] – это сосед слева. Если cur_pos равно [ 5, 7 ], то сложив его с [-1, 0] получим [4, 7], то есть, ход на клетку влево. Аналогично, [1,0] – это движение в положительном направлении по оси x, то есть, на клетку вправо. [0,-1] влияет только на y и является переходом на одну позицию вверх, тогда как [0,1] – на одну вниз.

Пользуясь численными абстракциями направлений, можно в рамках данного алгоритма точно так же обработать любые другие переходы. Можно учесть и другие направления, например, [1,1], это ход по диагонали вверх и далее вправо. Но при этом мы должны держать в уме и края решетки, за что и отвечает is_valid_point. Например, если мы дойдем до правого края решетки,  то смещение [1,0], соответствующее одному переходу вправо, выведет нас за пределы графа, поэтому мы такой ход пропустим.

Также будем пропускать все непустые клетки, поскольку это стены лабиринта, и пройти через них мы не можем.

if cell.type != mpf.CellType.Empty:
  continue

Переходим к вычислению расстояния.

dist = cur_cell.count + 1

Поскольку мы все время движемся по прямой, клетка за клеткой, здесь можно вспомнить о «Манхэттенском расстоянии», то есть, расстояниями между двумя точками, которое можно покрывать лишь в направлении x или y, причем, ни в один ход нельзя перейти сразу по двум осям. Название обусловлено тем, как пересекаются улицы на Манхэттене, образующие именно такую сетку. Манхэттенское расстояние применимо к Евклидовой геометрии, например, к такой сетке, с которой мы здесь работаем.

Если это расстояние меньше, чем до соседа, то мы укажем нового соседа и добавим его в список открытых узлов.

if cell.count > dist:
  cell.count = dist
  cell.path_from = cur_cell
  open_list.append(ncell_pos)

Используем обобщенное поле cell.count для измерения расстояния, а также обновим поле path_from, указывающее, каким путем мы пришли в данную точку.

Ранее мы говорили, что первым в open_list всегда идет узел с наименьшим значением count. Уже понятно, почему, ведь каждый соседний узел удален от нас ровно на 1. Стартовый узел считается как 0, поэтому добавляем в список открытых несколько узлов, значения которых равны 1. Теперь, поскольку все узлы мы обрабатываем по порядку, добавляем в список несколько двоек, пока не будут охвачены все единицы. В итоге у нас в списке останутся двойки. Продолжим охватывать двойки, также добавляя в список некоторые тройки.

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

Визуализируем

Давайте уделим немного времени визуализации. Вызовем fill_shortest_path из кода, входящего в дистрибутив.

import mortoray_path_finding as mpf
    
maze = mpf.maze.create_wall_maze( 20, 12 )
filled = mpf.tutorial_1.fill_shortest_path(maze.board, maze.start, maze.end)

finder = mpf.draw.Finder()
finder.set_board(filled)
finder.run()

Исходник: tutorial_1_2.py

Откроется такое окно, как показано ниже. Стартовая клетка обозначена желтым, в ней стоит 0. Числа увеличиваются по мере отдаления от этой точки, с инкрементом в единицу. Все клетки в решетке обозначены в соответствии с манхэттенским расстоянием от стартовой точки до них. Находим клетку, обозначенную зеленым, и вычисляем, каково расстояние от стартовой точки до нее.

Получение пути

Кратчайшего пути у нас пока нет, но есть пара способов, которыми его можно получить.

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

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

Альтернативный способ – отслеживать путь, заполняя расстояния. Это именно тот код, который мы пока игнорировали.

if cell.count > dist:
  cell.count = dist
  cell.path_from = cur_cell
  open_list.append(ncell_pos)

Всякий раз, добавляя узел в список открытых узлов, мы также устанавливаем cell.path_from. Здесь хранятся записи о кратчайшем входящем пути, что упрощает отслеживание обратного курса от места назначения.

def backtrack_to_start(board, end):
  """ Возвращает путь до конечной точки, при этом предполагается, что поле заполнялось при помощи алгоритма fill_shortest_path """
  cell = board.at( end )
  path = []
  while cell != None:
    	path.append(cell)
    	cell = cell.path_from
   	 
  return path

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

import mortoray_path_finding as mpf
    
maze = mpf.maze.create_wall_maze( 20, 12 )
filled = mpf.tutorial_1.fill_shortest_path(maze.board, maze.start, maze.end)
path = mpf.tutorial_1.backtrack_to_start(filled, maze.end)

finder = mpf.draw.Finder()
finder.set_board(filled)
finder.set_path(path)
finder.run()

Исходник: tutorial_1_3.py

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

Заключение

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

Расстояние между городами