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 рублей

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

  • 4 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 2022 / All rights reserved

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