Как найти самую короткую дорогу

Учимся находить кратчайший путь через простой двумерный алгоритм на 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*, использующий эвристику, которая позволяет обходиться без сканирования всей карты.

Заключение

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

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

Алгоритмов оптимизации существует очень много. В этой статье будет разобран один из самых известных алгоритмов, заимствованных у природы – муравьиный алгоритм (ACO – Ant Colony Optimization).

Идея муравьиного алгоритма возникла в результате наблюдения за поведением реальных муравьёв. Отправной точкой положили исследования аргентинских муравьёв в 1989-1990 годах. Затем, в начале 90-х годов, Марко Дориго начал исследования для применения этой информации в практике. Он первый смог применить их стратегию для задачи по нахождению кратчайших маршрутов в графе.

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

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

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

Пока (не выполнены условия выхода) выполняются следующие операции алгоритма:

1. Создание муравьёв.

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

2. Поиск решений.

Формула для вычисления вероятности перехода муравья из вершины i в j:

где τij(t) – количество феромона между вершинами i и j, ηij – расстояние между этими вершинами. α, β – константные параметры. Их необходимо подбирать опытным путём, их значение должно быть такое, чтобы алгоритм не был слишком жадным и не застревал в локальных минимумах.

Чем ближе к нулю параметр β, тем меньше муравьи в выборе пути будут руководствоваться расстоянием между вершинами и будут ориентироваться только на феромон. С увеличением β значение близости растёт. Параметр α действует так же, но для уровня феромона.

Верхняя часть формулы описывает желание муравья перейти из вершины i в вершину j. Оно пропорционально близости вершины и уровню феромона на пути к ней.

Таким образом, вероятность перехода из вершины i в вершину j равняется желанию перейти в неё, делённому на сумму желаний перейти из вершины i ко всем доступным вершинам, которые ещё не были посещены. Сумма всех вероятностей равна 1.

Разложив все вероятности на числовой прямой от 0 до 1, можно сгенерировать рандомное вещественное число в этом интервале. Результат покажет, в какую вершину перейдёт муравей.

3. Обновление феромона.

Формула для пересчёта уровня феромона на каждой итерации алгоритма:

где ρ – скорость испарения, t – номер итерации, Lk(t) – цена текущего решения для k-ого муравья, а Q – параметр, имеющий значение порядка цены оптимального решения, то есть Q/Lk(t) – феромон, откладываемый k-ым муравьём, использующим ребро (i, j).

Таким образом, количество феромона на ребре между i и j на новой итерации равно количеству феромона на старой итерации, умноженное на коэффициент испарения (феромон постоянно испаряется), и к полученному результату добавляется сумма всех новых порций феромона, который отложили все муравьи на этом участке. Добавка феромона, которую делает муравей, проходя по ребру, равна константе Q, делённой на длину маршрута L, пройденную муравьём k, при условии, что это ребро попало в маршрут муравья.

Сложность муравьиного алгоритма зависит от количества вершин, количества муравьёв и времени жизни колонии.

При помощи алгоритма эффективно решать задачу на нахождение оптимального маршрута. Эту задачу принято называть задачей коммивояжёра (TSP – Travelling Salesman Problem).

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

Например, торговцу нужно посетить 5 городов и вернуться в исходный. Находясь в городе отправления, у него для выбора доступно 4 города. Дальше он делает выбор из трёх городов и так далее. Значит, количество всех возможных вариантов равно 4*3*2*1 = 24, то есть (n-1)!, где n – количество городов.

В этой постановке задачи торговцу нужно объехать все города и вернуться в исходный, а направление движения не имеет значения. Это называется симметричной задачей коммивояжёра. Следовательно, половину вариантов можно не учитывать, так как, например, варианты ABCDEA и AEDCBA будут эквивалентны. Значит, количество маршрутов для 5 городов равно 24/2=12, а конечная формула количества вариантов для симметричной задачи будет выглядеть так: (n-1)!/2.

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

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

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

Рассмотрим реализацию алгоритма на языке Python.

Код написан в соответствие с описанием алгоритма и формулами выше. В алгоритме есть два важных фактора: феромон τ и видимость η. Феромон τ относится к оставшейся информации на каждом пути, по которому проходят муравьи. Видимость η обозначает обратное расстояние между узлами. Вероятность P состоит из произведения феромона τ и видимости η и их суммы. При кратчайшем пути, высоком уровне феромона τ, а также высокой видимости η вероятность P становится выше. Следовательно, в строках 39-40 происходит подсчёт вероятности P. Затем, строка 41 выбирает последовательность кратчайших путей при помощи вероятности P. Наконец, строки 55-64 обновляют феромон τ с коэффициентом испарения ρ. Параметр Q – это сумма феромонов в постоянном значении. Вернувшись к строке 37, новая последовательность маршрутов определена для следующего вычисления.

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

Вывод программы:

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

Рассмотрим задачу с количеством муравьёв, равным 40 (size_pop=40), итераций, равным 30 (max_iter=30) и вершин – 40. Функция cal_total_distance рассчитывает длину пути. Затем при помощи matplotlib.pyplot происходит вывод графиков. Также выводится время выполнения программы, которое мы дальше будем сравнивать для разного количества вершин.

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

Как мы видим, маршрут очень длинный и беспорядочный. Никому бы не понравилось ездить по такому маршруту. Путём подбора значений параметров удалось выяснить, что при количестве муравьёв и итераций, равных 40 и 30 соответственно, алгоритм почти всегда останавливается на этом решении:

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

40 – относительно небольшое число вершин. Можно посмотреть, как алгоритм будет вести себя на более сложных графах и как долго будет находить решение. При тех же параметрах на более сложных графах время работы алгоритма заметно увеличивается. Чтобы как-то сократить время выполнения, уменьшим количество муравьёв до 20 и итераций – до 5. Так выглядит результат работы на графе из 1000 вершин:

А так – на 2000:

Выглядит очень страшно. И выполнение заняло больше двух минут. Результат работы алгоритма для большего количества вершин (например, для 10000) дождаться было бы уже гораздо сложнее.

В рейтинге самых быстрых языков программирования Python стабильно занимает одно из последних мест. Зачастую логика, выполняющаяся на других языках за миллисекунды, на Python занимает несколько секунд. Существуют способы ускорения кода на Python. Например, пакет PyPy, который делает код быстрее. Или Cython – расширение языка, в котором поддерживается прямой вызов функций и методов C/C++ и строгая типизация. Он может ускорить работу более чем в 30 раз.

Также можно использовать реализацию алгоритма на другом языке программирования, например, на C/C++. Или научить программу эффективно использовать ресурсы компьютера: оптимизировать её под многопоточность и использовать код на ассемблере, чтобы обращаться к процессору напрямую, без компилятора высокого уровня. Но скорость и оптимизация кода – это уже тема для других объёмных статей.

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

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

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

 

Инициализация

Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Первый шаг

Второй шаг

Третий шаг

Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим следующие результаты.

Четвертый шаг

Пятый шаг

Шестой шаг

Реализация алгоритма Дейкстры

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

Реализация на C++

Результат выполнения

Назад: Алгоритмизация