Использование алгоритма A * для поиска ЛУЧШЕГО решения в задаче, смоделированной графом

Привет всем, сегодня мы поговорим об одном из лучших и самых известных алгоритмов поиска, широко известном алгоритме A*. До сих пор у нас была возможность изучить и реализовать на Python несколько алгоритмов поиска, таких как поиск в ширину (BFS), поиск в глубину (DFS), жадный алгоритм и т. д. Сегодня мы закрываем главу с помощью Алгоритмы поиска говорят об A*. В частности, мы поговорим о следующих темах:

1. Introduction
2. Pseudocode
3. Pen and Paper Example
4. Python implementation
5. Example
6. Conclusion

Как обычно, у нас много дел, так что давайте начнем.

Введение

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



Структура данных графа — теория и реализация Python
Руководство по реализации структуры данных графа в Python.python.plainenglish.io



Алгоритмы поиска делятся на две основные категории. К первой категории относятся так называемые «слепые» алгоритмы. Эти алгоритмы не учитывают стоимость между узлами. Алгоритмы поиска в ширину и поиска в глубину характеризуются как «слепые». С другой стороны, алгоритмы второй категории выполняют эвристический поиск,принимая во внимание стоимость пути или другие эвристики. Последняя категория относится к жадному алгоритму и алгоритму USC, о которых мы говорили в предыдущих статьях. A* также является эвристическим алгоритмом.

Псевдокод

Алгоритм A* работает примерно так же, как алгоритмы Greedy и UCS. Как вы, наверное, помните, эвристическая функция жадного алгоритма пытается оценить стоимость пути от текущего узла до конечного узла (назначения), используя метрики расстояния, такие как манхэттенское расстояние, евклидово расстояние и т. д. На основе этого значения алгоритм определяет следующий выбранный узел. С другой стороны, эвристическая функция алгоритма ПСК вычисляет расстояние текущего узла от начального узла (начальное состояние — узел) и выбирает в качестве следующего узла узел с наименьшим значением, или другими словами узел ближе к начальный узел.

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

Алгоритм A* принимает в качестве входных данных граф вместе с начальной и конечной точками и возвращает путь, если он существует, не обязательно оптимальный. Для этого он использует два списка, называемые открытыми и закрытыми. Открытый список содержит узлы, которые можно выбрать, а закрытый список содержит уже выбранные узлы. Во-первых, алгоритм вычисляет эвристическое значение первого узла и добавляет этот узел в открытый список (этап инициализации). После этого удалите исходный узел из открытого списка и поместите его в закрытый список. Затем алгоритм расширяет дочерние элементы выбранного узла и вычисляет эвристическое значение каждого из них. Если дочерний элемент не существует в обоих списках или находится в открытом списке, но с большей эвристической ценностью, то соответствующий дочерний элемент добавляется в открытый список на позицию соответствующего узла с более высокой эвристической ценностью. В противном случае он опускается. На каждом шаге узел с минимальным эвристическим значением выбирается и удаляется из открытого списка. Весь процесс завершается, когда решение найдено или открытый список пуст, что означает отсутствие возможного решения связанной проблемы. Псевдокод алгоритма A* следующий:

1.   function Greedy(Graph, start, target):
2.      calculate the heurisitc value h(v) of starting node
3.      add the node to the opened list
4.      while True:
5.         if opened is empty:
6.            break # No solution found
7.         selecte_node = remove from opened list, the node with
8.                        the minimun heuristic value
9.         if selected_node == target:
10.           calculate path
11.           return path
12.        add selected_node to closed list
13.        new_nodes = get the children of selected_node
14.        if the selected node has children:
15.           for each child in children:
16.              calculate the heuristic value of child
17.              if child not in closed and opened lists:
18.                 child.parent = selected_node
19.                 add the child to opened list
20.              else if child in opened list:
21.                 if the heuristic values of child is lower than 
22.                  the corresponding node in opened list:
23.                    child.parent = selected_node
24.                    add the child to opened list
where h(v) is the sum of the distance of the v node from the initial node and the estimated cost from v node to the final node.

Пример ручки и бумаги

Чтобы лучше понять алгоритм A*, мы запустим пример вручную. Мы будем использовать тот же пример, что и в статье о жадном алгоритме, с той разницей, что теперь мы будем использовать веса на ребрах графа. Итак, у нас получился следующий лабиринт:

Предположим, у нас есть робот, и мы хотим, чтобы робот перемещался из точки S в позиции (0, 0) в точку T в позиции (3, 2). Серые квадраты — препятствия, которые не может пройти робот. Чтобы найти путь из точки А в точку Т, воспользуемся жадным алгоритмом. В качестве эвристической функции мы будем использовать Манхэттенское расстояние. Таким образом, мы собираемся вычислить Манхэттенское расстояние всех ячеек лабиринта, используя следующую формулу.

манхэттен((x1, y1), (x2, y2)) = |x1 — x2| + |у1 — у2|

Сначала вычисляем манхэттенское расстояние для всех ячеек лабиринта. Соответствующие расстояния следующие:

Теперь мы готовы превратить (смоделировать) вышеприведенный лабиринт в граф. Итак, мы имеем следующий график:

Обратите внимание, что мы вставили веса в каждое ребро, которые представляют необходимую энергию для перехода робота из одного узла в другой. Более того, внутри каждого узла мы отметили манхэттенское расстояние. Теперь мы готовы выполнить алгоритм A*.

Шаг 1. Инициализация

Мы помещаем узел в открытый список после оценки его эвристического значения.

Шаг 2. Выбран узел S

Узел S удаляется из открытого списка и добавляется в закрытый список. Причем потомки S, узлы B, D добавляются в открытый список после вычисления их эвристических значений.

Шаг 3. Выбран узел B

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

Шаг 4. Выбран узел E

Узел E выбран, так как он имеет наименьшее эвристическое значение. Узел E удаляется из списка открытых и добавляется в список закрытых. После этого вычисляется эвристическое значение его дочерних элементов (узлов D и F), и узел F добавляется в открытый список. С другой стороны, узел D уже находится в открытом списке с эвристическим значением, равным 9, новое эвристическое значение узла D равно 11, что означает, что он больше, и поэтому мы сохраняем старый узел D (с узлом S в качестве его родитель) в открытом списке.

Шаг 5. Выбран узел D

Узел D выбран, так как он имеет наименьшее эвристическое значение. Узел D удаляется из списка открытых и добавляется в список закрытых. После этого вычисляется эвристическое значение его дочерних элементов (узлов E и H), и узел E добавляется в открытый список. С другой стороны, узел E уже находится в закрытом списке, поэтому он опущен.

Шаг 6. Выбран узел H

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

Шаг 7. Выбран узел J

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

Шаг 8. Выбран узел F

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

Шаг 9. Выбран узел K

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

Шаг 10. Выбран узел T

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

Реализация Python

Поняв, как работает алгоритм A*, пришло время реализовать его на Python.

Во-первых, мы создаем класс Node, который представляет каждый узел (вершину) графа. Этот класс имеет пару атрибутов, таких как координаты x и y, эвристическое значение, расстояние от начального узла и т. д. Более того, этот класс оснащен методами, помогающими нам взаимодействовать с узлами графа. На следующем изображении у нас есть обзор класса.

После этого мы реализуем класс AStar, представляющий алгоритм. Класс AStar имеет несколько атрибутов, таких как граф (пространство поиска проблемы), начальная точка, целевая точка, открытый и закрытый список и т. д. Обзор класса следующий:

Чтобы вычислить эвристическое значение, мы добавляем манхэттенское расстояние к расстоянию от начального узла. Обзор этих функций следующий:

Наконец, основной алгоритм следующий

Пример

Теперь у нас есть алгоритм, и мы можем выполнить алгоритм A* в любой задаче с графами. Мы собираемся проверить алгоритм на примере выше. График следующий:

поэтому мы смоделируем приведенный выше график следующим образом и выполним алгоритм.

Мы можем заметить, что мы получили те же результаты. Помните, что алгоритм A* всегда возвращает оптимальное решение.

Посмотреть и скачать весь код можно здесь.

Заключение

В этой статье у нас была возможность поговорить об алгоритме A*, чтобы найти оптимальный путь от начального узла к целевому узлу. Алгоритм A*, как и алгоритмы Greedy и USC, использует эвристическое значение для определения следующего шага. Более того, алгоритм A* всегда возвращает оптимальное решение. С A* мы закончили с поисковыми алгоритмами. В будущем у нас будет возможность сравнить их все на одних и тех же данных, визуализируя весь алгоритмический процесс. А пока продолжайте учиться и продолжайте программировать. Спасибо за прочтение.

Если вам нравится читать мои статьи, подписывайтесь на меня в LinkedIn и Twitter. Кроме того, вы можете зарегистрироваться, чтобы стать участником Medium. Как член, у вас есть неограниченный доступ к тысячам статей. Членство стоит 5$ в месяц. Вы можете использовать следующую ссылку, чтобы стать средним членом.



Присоединяйтесь к Medium по моей реферальной ссылке — Андреас Соуларидис
Прочитайте все статьи Андреаса Суларидиса (и тысяч других авторов на Medium). Ваш членский взнос напрямую…medium.com



Подробнее об алгоритмах поиска.



Решение лабиринта с помощью алгоритма поиска в ширину (BFS) в Python
Узнайте, как использовать и реализовать алгоритм поиска в ширину (BFS) для решения реальных задач. python.plainenglish.io





Как решать судоку с помощью алгоритма поиска в глубину (DFS) в Python
Руководство по решению головоломки судоку с использованием алгоритма поиска, называемого поиском в глубину.python.plainenglish.io





Жадный алгоритм в Python
Использование жадного алгоритма для поиска решения задачи, моделируемой графомpython.plainenglish.io





Алгоритм унифицированного поиска (UCS) в Python
Использование унифицированного алгоритма поиска для поиска наилучшего решения в задаче, моделируемой графомpython.plainenglish.io



Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter и LinkedIn. Присоединяйтесь к нашему сообществу Discord.