Введение:
Вы сидите в своей машине, застряв в печально известном трафике Хайдарабада, и ждете, когда загорится зеленый сигнал. Или, может быть, вы бродите по оживленным улицам Бангалора, отчаянно пытаясь успеть на важную встречу вовремя. По мере того, как тикают минуты, и кажется, что пункт назначения отдаляется, вы не можете не желать, чтобы появился волшебный путь — секретный маршрут, о котором знаете только вы, ведущий прямо к месту назначения. Звучит как фантастика, правда?
Но что, если я скажу вам, что есть алгоритм, который может сделать именно это, только не для многолюдных городских улиц, а для сложных лабиринтов и сеток в мире программирования. Войдите в алгоритм A* (произносится как «A-star»), лучший дорожный полицейский в компьютерном мире, плавно направляющий данные из точки А в точку Б.
Как и у вас, у каждой точки данных в вычислительной системе есть пункт назначения. Иногда он точно знает, как туда добраться. Но часто он оказывается посреди кодового эквивалента перекрестка Silk Board в Бангалоре или трафика HITEC City в Хайдарабаде. Вот когда на помощь приходит алгоритм A*. Он использует комбинацию известных путей и умных прогнозов, чтобы найти кратчайший путь к месту назначения.
В этом блоге мы окунемся в шумный город алгоритмов поиска пути и демистифицируем правила дорожного движения, которые A* использует для навигации. И кто знает, к концу этого вы, возможно, просто пожалеете, что не можете вызвать A *, чтобы очистить городское движение. Так что пристегните ремни, пора отправиться в увлекательное путешествие по закоулкам алгоритма А*! В путь!
Предыстория:
Когда движение в Хайдарабаде, наконец, начинает двигаться вперед, трудно не думать о том, как мы здесь оказались. Эти многолюдные улицы, лабиринт автомобилей, какофония гудков — все началось с простого путешествия из точки А в точку Б. Но, как скажет вам каждый, кто хоть раз попадал в пробку, кратчайший путь не всегда самый очевидный. Иногда он спрятан, ожидая, пока его обнаружат.
В мире компьютерных наук данные часто оказываются в похожей ситуации. Ему нужно добраться из одной точки в другую, преодолевая сложную сеть узлов. Это может быть что угодно: поисковый робот, просматривающий страницы веб-сайта, устройство GPS, находящее лучший маршрут, или искусственный интеллект в игре, пытающийся достичь цели.
На протяжении десятилетий программисты пытались решить эту проблему с помощью различных алгоритмов, каждый из которых имел свои сильные и слабые стороны. Некоторые из них были быстрыми, но неточными, в то время как другие были точными, но медленными. Только в 1968 году трое ученых-компьютерщиков — Питер Харт, Нильс Нильссон и Бертрам Рафаэль из Стэнфордского исследовательского института в Калифорнии — нашли решение, которое было одновременно эффективным и точным. Они назвали этот революционный алгоритм «A*», и мир поиска пути уже никогда не был прежним.
Подобно опытному горожанину, знающему все тонкости местных улиц, A* может найти кратчайший путь в лабиринте вариантов. Но вместо того, чтобы полагаться на личный опыт или удачу, он использует умную смесь расчетов и прогнозов.
По мере того, как мы углубляемся в работу алгоритма A*, легко увидеть параллели с нашей повседневной навигацией. Таким образом, хотя мы, возможно, и не сможем разделить море трафика по пути домой, мы, безусловно, можем помочь нашим программам найти путь в самых сложных лабиринтах. Давайте приготовимся раскрыть науку, стоящую за искусством поиска пути!
Связанные условия:
Хорошо, давайте разобьем это на еще более простые термины. Алгоритм A*, как и навигация по оживленному городу, имеет свой собственный жаргон. Но не волнуйтесь — вам не нужна степень в области компьютерных наук, чтобы понять их. Вот ключевые термины, которые нам нужно знать, объясненные как можно проще:
Узлы. Подумайте об узлах как о различных остановках, которые вы делаете во время путешествия — например, в любимой кофейне, на заправочной станции или в доме вашего друга. В алгоритме A* узлы — это просто точки в нашей структуре данных, которые нам нужно проверить.
Пути. Пути — это маршруты, по которым вы перемещаетесь от одного узла (или остановки) к другому. Это как дороги, по которым вы едете, идете или едете на велосипеде, чтобы добраться от дома до офиса.
G-стоимость. G-стоимость похожа на счетчик пути: она показывает, как далеко вы проехали от начальной точки. В A* это стоимость кратчайшего пути от начального узла (или начальной точки) до определенного узла (или остановки).
H-cost (эвристическая стоимость). Представьте, что у вас есть волшебный GPS, который предсказывает, как далеко вы находитесь от пункта назначения, не зная точного маршрута. Вот что такое H-стоимость в A*. Это оценка или «наилучшее предположение» расстояния от узла до целевого узла (или пункта назначения).
F-cost:F-cost — это общая предполагаемая «стоимость» вашего путешествия, если вы проедете через определенный узел или остановку. Это сумма ваших G-стоимости и H-стоимости. Как и вы, A* хочет достичь цели с наименьшими усилиями, поэтому для продолжения всегда выбирает узел с наименьшей F-стоимостью.
Итак, вот оно. Основные термины, которые необходимо знать для понимания алгоритма A*. Не беспокойтесь, если вам покажется, что это слишком сложно — так же, как научиться ориентироваться в новом городе, вы освоитесь по мере того, как мы будем углубляться. Итак, давайте приготовимся исследовать увлекательный мир алгоритма A*!
Алгоритм:
Мы познакомились с некоторыми терминами, которые являются ключевыми для понимания алгоритма A* — G-стоимость, H-стоимость и F-стоимость. Это как координаты на карте нашего города, помогающие нам решить, какой маршрут выбрать. Теперь, когда мы изучили «язык» A*, давайте углубимся в то, как эти термины взаимодействуют, помогая алгоритму найти наиболее эффективный путь.
Алгоритм A * в основном работает с тремя факторами стоимости, как мы обсуждали выше, а именно:
G-стоимость: представляет точную стоимость пути от начального узла до любого другого узла. С математической точки зрения, предположим, что вы в настоящее время находитесь в узле «N», тогда G-стоимость будет стоимостью от «Начального» узла до этого узла «N».
H-стоимость (эвристическая стоимость): это оценочная стоимость от текущего узла до конечного узла (цель). Это своего рода «догадка», которая помогает А* выбрать наилучший путь. Существует несколько способов расчета H-стоимости, из них два наиболее распространенных:
Манхэттенское расстояние. Если путь допускает только четыре направления (вверх, вниз, влево, вправо), мы используем это. Формула
H = абс(текущий_узел.х — целевой_узел.х) + абс(текущий_узел.у — целевой_узел.у)
Евклидово расстояние. Если путь допускает восемь направлений (добавляет диагональное движение к предыдущим четырем), мы используем это. Формула
H = sqrt((current_node.x — target_node.x)² + (current_node.y — target_node.y)²)
F-стоимость: это просто общая стоимость конкретного узла, которая представляет собой сумму G-стоимости и H-стоимости. Математически,
F = G + H
Это как когда вы планируете поездку и хотите рассчитать общую стоимость. Вы добавляете стоимость поездки от дома до аэропорта (G-стоимость), а затем добавляете оценку оставшихся дорожных расходов (H-стоимость), чтобы получить общую ориентировочную стоимость поездки (F-стоимость). Просто, верно?
Используя эти факторы стоимости, алгоритм A* всегда выбирает узел с наименьшей F-стоимостью (т. е. с наименьшей общей стоимостью) для следующего хода. Он продолжает исследовать, пока не достигнет места назначения. Затем он возвращается от пункта назначения к началу, тем самым предоставляя нам наиболее эффективный маршрут!
Абсолютно, давайте соберем все вместе:
Задача лабиринта:
Подумайте об этом: вы находитесь в лабиринте, сетке размером 5x6. Эта сетка представляет трафик нашего прекрасного города, и каждая ячейка представляет собой улицу. Некоторые улицы перекрыты, а некоторые открыты. В нашей сетке «0» представляет открытые улицы, а «1» — заблокированные улицы или стены. Вот так выглядит наш лабиринт:
лабиринт = [[0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 0],
[0, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0]]
Теперь представьте, что вы застряли в левом верхнем углу города (позиция [0,0]), и вам нужно добраться до своего друга, который застрял в середине (позиция [3,2]). Как бы вы передвигались, чтобы добраться до своего друга, учитывая, что вы не можете пройти по заблокированным улицам?
Вот где A* приходит нам на помощь! A* — замечательный алгоритм поиска пути, который предоставляет нам кратчайший путь от начала до конца, маневрируя по заблокированным улицам. Теперь давайте разберем, как работает A*, используя нашу задачу о лабиринте:
1. Начальная точка ([0, 0]):
— G-стоимость: 0 (Мы еще не двинулись!)
— H-стоимость (манхэттенское расстояние до конца): `abs( 0–3) + абс(0–2) = 5`.
— F-стоимость: `F = G + H = 0 + 5 = 5`.
2. Исследуйте соседей ([1, 0] и [0, 1]):
— Для [1, 0] (вниз) G-стоимость равна 1 (всего один шаг от начала), H- стоимость равна `abs(1–3) + абс(0–2) = 4`, поэтому F-стоимость равна `F = G + H = 1 + 4 = 5`.
— Для [0, 1] (справа), G-стоимость равна 1, H-стоимость равна «абс (0–3) + абс (1–2) = 4», поэтому F-стоимость равна «F = G + H = 1 + 4 = 5». .
3. Выбор следующего шага ([1, 0]):
— У нас есть два узла с одинаковой F-стоимостью, можем выбрать любой. Давайте спустимся для этого примера. Теперь мы повторяем шаг 2 для новой позиции [1, 0].
4. Продолжаем:
— Мы продолжаем этот процесс, всегда выбирая узел с наименьшей F-стоимостью, пока либо не достигнем нашего друга в [3,2], либо не выясним, что нет никакого возможного пути (что было бы настоящий облом).
Таким образом, A* помогает нам маневрировать по улицам города, гарантируя, что мы выберем кратчайший и наиболее эффективный путь к нашему другу. Если бы только в реальном трафике было так легко ориентироваться, верно? Но, по крайней мере, мы можем использовать A* для навигации по нашему лабиринту!
Наконец код
Пришло время воплотить в жизнь наш алгоритм A* с помощью некоторого кода Python и применить его к нашей определенной проблеме лабиринта. Благодаря теоретическим знаниям, которые вы получили об алгоритме A*, вы сможете понять, как мы переводим их в рабочий код.
Наш сценарий Python в основном состоит из определения класса для узлов, функций для алгоритма A* и функций построения графиков для визуализации нашего лабиринта и найденного пути.
import numpy as np
import warnings
warnings.filterwarnings('ignore')
import matplotlib.pyplot as plt
class Node:
"""
parent is parent of the current Node
position is current position of the Node in the maze
g is cost from start to current Node
h is heuristic based estimated cost for current Node to end Node
f is total cost of present node i.e. : f = g + h
"""
def __init__(self, parent=None, position=None):
self.parent = parent
self.position = position
self.g = 0
self.h = 0
self.f = 0
def __eq__(self, other):
return self.position == other.position
def euclidean(self, end_node):
dist = (((self.position[0] - end_node.position[0]) ** 2) +
((self.position[1] - end_node.position[1]) ** 2))
return dist
def manhattan(self, end_node):
dist = (abs(self.position[0] - end_node.position[0]) +
abs(self.position[1] - end_node.position[1]))
return dist
def return_path(current_node,maze):
path = []
no_rows, no_columns = np.shape(maze)
result = [[-1 for i in range(no_columns)] for j in range(no_rows)]
current = current_node
while current is not None:
path.append(current.position)
current = current.parent
path = path[::-1]
start_value = 0
for i in range(len(path)):
result[path[i][0]][path[i][1]] = start_value
start_value += 1
return result
def A_star(maze, start, end, move, heuristic='euclidean'):
start_node = Node(None, tuple(start))
start_node.g = start_node.h = start_node.f = 0
end_node = Node(None, tuple(end))
end_node.g = end_node.h = end_node.f = 0
yet_to_visit_list = []
visited_list = []
yet_to_visit_list.append(start_node)
outer_iterations = 0
max_iterations = (len(maze) // 2) ** 10
"""
1) We first get the current node by comparing all f cost and selecting the lowest cost node for further expansion
2) Check max iteration reached or not. Set a message and stop execution
3) Remove the selected node from yet_to_visit list and add this node to visited list
4) Perform Goal test and return the path else perform below steps
5) For selected node find out all children (use move to find children)
a) if move is diagonal, then cost = sqrt(2), else cost = 1
b) get the current postion for the selected node (this becomes parent node for the children)
c) check if a valid position exist (boundary will make few nodes invalid)
d) if any node is a wall then ignore that (obstacle)
e) add to valid children node list for the selected parent
For all the children node
a) if child in visited list then ignore it and try next neighbour node
b) calculate child node g, h and f values
c) if child in yet_to_visit list then ignore it
d) else move the child to yet_to_visit list
"""
no_rows, no_columns = np.shape(maze)
while len(yet_to_visit_list) > 0:
outer_iterations += 1
current_node = yet_to_visit_list[0]
current_index = 0
for index, item in enumerate(yet_to_visit_list):
if item.f < current_node.f:
current_node = item
current_index = index
if outer_iterations > max_iterations:
print ("giving up on pathfinding too many iterations")
return return_path(current_node,maze)
yet_to_visit_list.pop(current_index)
visited_list.append(current_node)
if current_node == end_node:
return return_path(current_node,maze)
children = []
for new_position in move:
if 0 in new_position:
cost = 1
else:
cost = np.sqrt(2)
node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
if (node_position[0] > (no_rows - 1) or
node_position[0] < 0 or
node_position[1] > (no_columns -1) or
node_position[1] < 0):
continue
if maze[node_position[0]][node_position[1]] != 0:
continue
new_node = Node(current_node, node_position)
children.append(new_node)
for child in children:
if len([visited_child for visited_child in visited_list if visited_child == child]) > 0:
continue
child.g = current_node.g + cost
if heuristic=='manhattan':
child.h = child.manhattan(end_node)
elif heuristic=='euclidean':
child.h = child.euclidean(end_node)
else:
child.h = 0
child.f = child.g + child.h
if len([i for i in yet_to_visit_list if child == i and child.g > i.g]) > 0:
continue
yet_to_visit_list.append(child)
def plot_path(maze, start, end, path):
if path is None:
print("No solution found")
m,n = len(maze), len(maze[0])
pt = [[0 for j in range(n)] for i in range(m)]
for i in range(m):
for j in range(n):
if path[i][j]!=-1:
if [i,j]==start:
pt[i][j] = 1
elif [i,j]==end:
pt[i][j] = 3
else:
pt[i][j] = 2
if maze[i][j]==1:
pt[i][j] = 4
plt.pcolormesh(pt)
plt.axes().set_aspect('equal')
plt.xticks([])
plt.yticks([])
plt.axes().invert_yaxis()
plt.show()
def plot_maze(maze, start, end):
m,n = len(maze), len(maze[0])
pt = [[0 for j in range(n)] for i in range(m)]
for i in range(m):
for j in range(n):
if [i,j]==start:
pt[i][j] = 1
elif [i,j]==end:
pt[i][j] = 3
elif maze[i][j]==1:
pt[i][j] = 4
plt.pcolormesh(pt)
plt.axes().set_aspect('equal')
plt.xticks([])
plt.yticks([])
plt.axes().invert_yaxis()
plt.show()
maze = [[0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 0],
[0, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0]]
start = [0, 0]
end = [3,2]
'''
Generating all the 8 successor of this cell
N.W N N.E
\ | /
\ | /
W----Cell----E
/ | \
/ | \
S.W S S.E
N --> North (-1, 0)
S --> South (1, 0)
E --> East (0, 1)
W --> West (0, -1)
N.E--> North-East (-1, 1)
N.W--> North-West (-1, -1)
S.E--> South-East (1, 1)
S.W--> South-West (1, -1)
'''
move = [[-1, 0 ],
[ 1, 0 ],
[ 0, 1 ],
[ 0, -1],
[-1, 1],
[-1, -1],
[1, 1],
[1, -1]]
path = A_star(maze, start, end, move, heuristic='manhattan')
plot_maze(maze, start, end)
plot_path(maze, start, end, path)
1. Класс узла. Этот класс служит образцом для каждой ячейки или узла в нашем лабиринте. Он отслеживает родительский узел (откуда мы пришли), положение узла в лабиринте и показатели стоимости (`g`, `h` и `f`), связанные с узлом. Он также предоставляет методы для расчета эвристики (h-значения) на основе либо евклидова, либо манхэттенского расстояния, придерживаясь наших предыдущих обсуждений этих мер расстояния.
2. Функция return_path: эта функция делает именно то, что мы обсуждали в теоретической части. Он отслеживает обратный путь от цели к началу, используя родительские указатели, собирая воедино наш оптимальный путь от начала к цели.
3. Функция A_star: это сердце нашей реализации, где оживают шаги алгоритма A*:
- Он начинается с инициализации `start_node` и `end_node`. Для этих узлов значения g, h и f инициализируются равными нулю.
— Создаются `yet_to_visit_list` (аналогично нашему открытому списку) и `visited_list` (аналогично нашему закрытому списку), и начальный узел добавляется в `yet_to_visit_list`.
— здесь начинается основной цикл функции. Пока в `yet_to_visit_list` есть узлы, алгоритм продолжает свое путешествие.
— На каждой итерации функция выбирает узел с наименьшей f-стоимостью из `yet_to_visit_list` как есть. считается наиболее многообещающим узлом для достижения цели.
— Затем этот выбранный узел перемещается из списка `посещенных_посетителей` в список `посещенных_списков`. Если окажется, что этот узел является нашим целевым узлом, мы успешно нашли наш путь, и алгоритм может закончиться.
— Далее функция генерирует все допустимые соседние ячейки (потомки текущего узла) . Любая ячейка, которая является стеной (обозначается как «1» в лабиринте) или за пределами сетки лабиринта, не считается допустимым дочерним элементом.
— для каждого допустимого дочернего элемента функция вычисляет свои g, h , и значения f. Если дочерний элемент уже находится в списке `yet_to_visit_list`, но с более высоким значением g, его стоимость обновляется. Если его нет в `yet_to_visit_list`, оно добавляется.
4. Функции `plot_path` и `plot_maze`: после решения лабиринта мы хотели бы визуализировать путь, который нашел алгоритм. Эти функции заботятся об этом, обеспечивая графическое представление лабиринта и пути от начала до цели.
5. Наконец, мы определяем фактическую задачу лабиринта с помощью схемы лабиринта, начальной и конечной точек и возможных ходов. Затем мы вызываем функцию `A_star` с этими параметрами, чтобы решить лабиринт.
После запуска этого кода вы увидите начальный лабиринт и оптимальный путь от начала до цели согласно алгоритму A*, демонстрируя тем самым успешную реализацию алгоритма на Python. Алгоритм A* с помощью своей интеллектуальной эвристики перемещается по лабиринту так же, как и мы, находя кратчайший возможный путь. Путешествие из Хайдарабада в Бангалор может быть загружено пробками, но с A* мы нашли плавную поездку!
Ссылки
Полный код: https://github.com/Mouli53/A-star-Algorithm-and-other-Algorithms/blob/main/A_Algorithm.ipynb
