Share This
Связаться со мной
Крути в низ
Categories
//Алгоритм А* и его реализация на Python

Алгоритм А* и его реализация на Python

19.07.2021Category : Python

Алгоритм А* — один из самых эффективных алгоритмов поиска кратчайшего пути между двумя точками графа. Он был опубликован Питером Хартом, Нильсом Нильссоном и Бертрамом Рафаэлем в 1968 году. В каком-то смысле его можно назвать расширением алгоритма Дейкстры. Однако, несмотря на это он является одним из самых часто используемых алгоритмов поиска пути. 

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

  • f(n) = g(n) + h(n)
  • f(n): общая стоимость пути
  • g(n): стоимость пути между текущей и начальной вершиной
  • h(n): эвристическая функция

Разберем пример. У нас есть граф:

algoritm a i ego realizacija na python 996c368 - Алгоритм А* и его реализация на Python

Допустим, мы хотим попасть из точки X в точку Y. Так как вершина Х не меняет своего положения, мы можем отбросить g(n) — ее значение равно 0. Эвристическое значение этой вершины выделено красным шрифтом — 5.

В подобных задачах эвристическое значение —  стоимость достижения рассматриваемой вершины из начальной.

Из вершины Х есть два пути. 

Если мы перейдем в вершину А, g(n) будет равна 5 (стоимость пути), так как мы перемещаемся в новую вершину. Значение h(n) теперь равно 1. Значение f(n) в точке А будет равно 5+1 = 6. Теперь найдем значение f(n) каждой точки:

  • X— A => g(A) + f(A) = 5 + 1 = 6,
  • A — Y=> g(Y) + f(Y) = 6+ 0= 6,
  • X— B => g(B) + f(B) = 1+ 4= 5,
  • B — C => g(C) + f(C) = 3+ 2= 5,
  • C — Y=> g(Y) + f(Y) = 5 + 0= 5,

Как видно из наших вычислений, кратчайший путь — X-B-C-Y. Его стоимость равна 5, в то время как X-A-Y — 6. С этим примером разобрались, рассмотрим следующий.

algoritm a i ego realizacija na python da18f96 - Алгоритм А* и его реализация на Python

Допустим, мы хотим найти кратчайший путь от вершины А до вершины J.

Из А есть только два пути — B и F. Вычислим стоимость: f(B) = 8 + 6 = 14 и f(F) = 3+6 =9. Следовательно, нам нужно перейти в вершину F — алгоритм продолжит работу отсюда.

Из точки F есть два пути — G и H. Снова вычислим стоимость:  f(G) = 4 +5 = 9 and f(H) = 10 + 3 = 13. Значит, мы переходим в точку G.

Следуя пути I—J, получаем следующее:  f(I) = 7 + 1 = 8 и f(J) = 10. Так как все значения, следующие за вершиной F, меньше f(B), возвращаться к вершине B не имеет смысла.

Но допустим другой вариант. Предположим, что f(I) больше f(B) при прохождении через F и G (f(I) > 14). В этом случае алгоритм A* прекратит дальнейшую работу и переместится в вершину В. Но, так как f(C) > f(I), работа алгоритма продолжается именно в вершине I. 

Реализация алгоритма на Python

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

Для начала нам нужно создать сетку. Некоторые узлы отметим как препятствия. После этого выбираем начальную и конечную вершину — и запускаем алгоритм!

Логика алгоритма основана на двух списках — open_set и closed_set. Обратите внимание, что вершины в этих двух списках не должны повторяться! (При некоторых подходах препятствия сразу же помещаются в closed_set, а при других рассматриваются как возможные варианты). В результате работы алгоритма эти списки опустошаются и заполняются и в итоге достигается результат. 

    def main(self):          grid = AStar.create_grid(self.cols, self.rows)         grid = AStar.fill_grids(grid, self.cols, self.rows, obstacle_ratio = self.obstacle_ratio, obstacle_list = self.obstacle_list)         grid = AStar.get_neighbors(grid, self.cols, self.rows)         open_set  = []         closed_set  = []         current_node = None         final_path  = []         open_set.append(grid[self.start[0]][self.start[1]])         self.end = grid[self.end[0]][self.end[1]]         while len(open_set) > 0:             open_set, closed_set, current_node, final_path = AStar.start_path(open_set, closed_set, current_node, self.end)             if len(final_path) > 0:                 break          return final_path

Псевдокод вы можете найти в Википедии.

В репозитории проекта есть GIF-ка, наглядно демонстрирующая работу алгоритма А*. Для визуализации использована библиотека Pyp5js.

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

python AStar.py -c 25 -r 25 -s 1 -q 3 -e 23 -t 21 -l True

В результате получаем:

The way found!!! 23 20 23 19 23 18 23 17 23 16 23 15 23 14 23 13 23 12 23 11 23 10 23 9 23 8 23 7 23 6 23 5 23 4 23 3 22 3 21 3 20 3 19 3 18 3 17 3 16 3 15 3 14 3 13 3 12 3 11 3 10 3 9 3 8 3 7 3 6 3 5 3 4 3 3 3 2 3 1 3

Pyp5js

Pyp5js — это фреймворк для визуализации программ, написанных на Python, прямо в браузере! С его помощью запускается JavaScript-библиотека p5.js. После установки фреймворк запускается следующей командой: 

$ SKETCHBOOK_DIR='~/my-custom-sketchbook' pyp5js serve

После этого все, что нужно, настраивается в интерфейсе по адресу http://localhost:5000/. В папке SKETCHBOOK_DIR все операции осуществляются в соответствии с Python-кодом в файле, имя которого совпадает с именем проекта. 

Итоги

Алгоритм А* — один из самых часто используемых алгоритмов поиска кратчайшего пути. В этой статье мы разобрали принципы его работы и обсудили его реализацию на Python. Для визуализации мы использовали библиотеку pyp5js. 

algoritm a i ego realizacija na python 87498ce - Алгоритм А* и его реализация на Python

Кодинг-марафон по Python

Реши 10 задач и выиграй 5500 рублей

Подписаться ×

  • 1 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Свежие комментарии

    Рубрики

    About Author 01.

    blank
    Roman Spiridonov

    Моя специальность - Back-end Developer, Software Engineer Python. Мне 39 лет, я работаю в области информационных технологий более 5 лет. Опыт программирования на Python более 3 лет. На Django более 2 лет.

    Categories 05.

    © Speccy 2020 / All rights reserved

    Связаться со мной
    Close