Автор оригинала: Vladimir Batoćanin.
Основные понятия ИИ: А* Алгоритм поиска
Вступление
Искусственный интеллект в своей основе стремится решать задачи огромной комбинаторной сложности. На протяжении многих лет эти проблемы сводились к проблемам поиска.
Задача поиска пути-это вычислительная задача, в которой вы должны найти путь из точки А в точку Б. В нашем случае мы будем сопоставлять задачи поиска с соответствующими графами, где узлы представляют все возможные состояния , в которых мы можем оказаться, и ребра , представляющие все возможные пути, которые мы имеем в нашем распоряжении.
Так что следующий логичный вопрос будет:
Как преобразовать проблему в проблему поиска?
Что такое A*?
Допустим, вам предстоит пройти через огромный лабиринт. Этот лабиринт настолько велик, что потребуется несколько часов, чтобы найти цель вручную. Кроме того, как только вы закончите лабиринт “пешком”, вы должны закончить еще один.
Чтобы сделать все значительно проще и менее трудоемким, мы сведем лабиринт к задаче поиска и придумаем решение, которое можно применить к любому дополнительному лабиринту, с которым мы можем столкнуться, – при условии, что он следует тем же правилам/структуре.
Каждый раз, когда мы хотим преобразовать любую проблему в проблему поиска, мы должны определить шесть вещей:
- Набор всех состояний, в которых мы можем оказаться
- Начальное и конечное состояние
- Финишная проверка (способ проверить, находимся ли мы в готовом состоянии)
- Набор возможных действий (в данном случае различных направлений движения)
- Функция обхода (функция, которая скажет нам, где мы окажемся, если пойдем в определенном направлении)
- Набор затрат на перемещение из состояния в состояние (которые соответствуют ребрам в графе)
Проблема лабиринта может быть решена путем сопоставления пересечений с соответствующими узлами (красные точки), а возможные направления мы можем перейти к соответствующим ребрам графа (синие линии).
Естественно, мы определяем начальное и конечное состояния как пересечения, где мы входим в лабиринт (узел А) и где мы хотим выйти из лабиринта (узел В).
Теперь, когда у нас есть готовый граф, мы можем обсудить алгоритмы поиска пути из состояния А в состояние В. В простых случаях (как этот), когда сгенерированный граф состоит из небольшого числа узлов и ребер, BFS , DFS и Dijkstra было бы достаточно.
Однако в реальном сценарии, поскольку мы имеем дело с проблемами огромной комбинаторной сложности, мы знаем, что нам придется иметь дело с огромным количеством узлов и ребер. Например, существует много состояний, в которых может находиться кубик Рубика, поэтому его решение так сложно. Поэтому мы должны использовать алгоритм, который в некотором смысле является управляемым . Вот где возникает информированный алгоритм поиска , A*.
Информированный поиск означает, что алгоритм имеет дополнительную информацию, для начала. Например, неосведомленный алгоритм задачи поиска будет находить путь от дома до работы полностью вслепую.
С другой стороны, информированный алгоритм поиска проблемы будет находить путь от дома до работы с помощью вашего зрения (видя, какой путь приближает вас к месту назначения) или карты (точно зная, как далеко каждая отдельная точка находится от места назначения).
A* выполняет шаг только в том случае, если он кажется перспективным и разумным, в соответствии со своими функциями, в отличие от других алгоритмов обхода графа. Он бежит к цели и не рассматривает никаких неоптимальных шагов, если ему не нужно их рассматривать.
Это делает A* очень полезным для искусственно интеллектуальных систем – особенно в машинном обучении и разработке игр, поскольку эти системы воспроизводят реальные сценарии.
Если вы хотите узнать больше об алгоритмах обхода графов , их приложениях и различиях, мы их рассмотрим!
Основные понятия А*
A* основан на использовании эвристических методов для достижения оптимальности и полноты и является вариантом алгоритма best-first.
Когда алгоритм поиска обладает свойством оптимальности, это означает, что он гарантированно найдет наилучшее из возможных решений, в нашем случае кратчайший путь к конечному состоянию. Когда алгоритм поиска обладает свойством полноты, это означает, что если решение данной задачи существует, то алгоритм гарантированно его найдет.
Каждый раз, когда A* входит в состояние, он вычисляет стоимость, f(n) (n-соседний узел), чтобы добраться до всех соседних узлов, а затем входит в узел с наименьшим значением f(n) .
Эти значения рассчитываются по следующей формуле:
$$ \mathcal f(n) = \mathcal g(n) + \mathcal h(n) $$
g(n) – значение кратчайшего пути от начального узла к узлу n , а h(n) – эвристическое приближение значения узла.
Чтобы мы могли восстановить любой путь, нам нужно пометить каждый узел относительным, имеющим оптимальное значение f(n) . Это также означает, что если мы вернемся к определенным узлам, нам придется обновить и их наиболее оптимальные родственники. Об этом позже.
Эффективность A* сильно зависит от эвристического значения h(n) , и в зависимости от типа задачи нам может потребоваться использовать другую эвристическую функцию для поиска оптимального решения.
Построение таких функций-задача не из легких и является одной из фундаментальных проблем ИИ. Двумя фундаментальными свойствами, которыми может обладать эвристическая функция, являются допустимость и согласованность .
Допустимость и последовательность
Данная эвристическая функция h(n) является допустимой , если она никогда не переоценивает реальное расстояние между n и целевым узлом.
Поэтому для каждого узла n применяется следующая формула:
$$ h(n)\leq h^*(n) $$
h*(n) – реальное расстояние между n и целевым узлом. Однако, если функция действительно переоценивает реальное расстояние, но никогда не более чем на d , мы можем с уверенностью сказать, что решение, которое производит функция, имеет точность d (то есть она не переоценивает кратчайший путь от начала до конца более чем на d ).
Данная эвристическая функция h(n) является последовательной , если оценка всегда меньше или равна расчетному расстоянию между целью n и любым заданным соседом плюс расчетные затраты на достижение этого соседа:
$$ c(n,m)+h(m)\geq h(n) $$
c(n,m) – расстояние между узлами n и m . Кроме того, если h(n) согласован, то мы знаем оптимальный путь к любому узлу, который уже был проверен. Это означает, что эта функция является оптимальной .
Теорема : Если эвристическая функция непротиворечива, то она также допустима.
Доказательство полной индукцией
Параметр индукции N будет числом узлов между узлом n и конечным узлом s на кратчайшем пути между ними.
База :
Если между n и s нет узлов и поскольку мы знаем , что h(n) непротиворечиво, то справедливо следующее уравнение:
$$ c(n,s)+h(s)\geq h(n) $$
Зная h*(n)=c(n,s) и h(s)=0 , мы можем с уверенностью сделать вывод, что:
$$ h^*(n)\geq h(n) $$
Индукционная гипотеза : N < k
Мы предполагаем, что данное правило верно для каждого N < k .
Индукционный шаг:
В случае N узлов на кратчайшем пути от n до s мы проверяем первый преемник (узел m ) конечного узла n . Поскольку мы знаем , что существует путь от m до n , и мы знаем, что этот путь содержит k-1 узлов, справедливо следующее уравнение:
$$ (𝑛, 𝑚) + ℎ^*(𝑚) ≥ 𝑐(𝑛, 𝑚) + ℎ(𝑚) ≥ ℎ(𝑛) $$
Q. E. D.
Реализация
Это прямая реализация A* на графовой структуре. Для простоты и краткости эвристическая функция определяется как 1 для всех узлов.
Граф представлен списком смежности, где ключи представляют узлы графа, а значения содержат список ребер с соответствующими соседними узлами.
Здесь вы найдете алгоритм A*, реализованный в Python:
from collections import deque
class Graph:
# example of adjacency list (or rather map)
# adjacency_list = {
# 'A': [('B', 1), ('C', 3), ('D', 7)],
# 'B': [('D', 5)],
# 'C': [('D', 12)]
# }
def __init__(self, adjacency_list):
self.adjacency_list = adjacency_list
def get_neighbors(self, v):
return self.adjacency_list[v]
# heuristic function with equal values for all nodes
def h(self, n):
H = {
'A': 1,
'B': 1,
'C': 1,
'D': 1
}
return H[n]
def a_star_algorithm(self, start_node, stop_node):
# open_list is a list of nodes which have been visited, but who's neighbors
# haven't all been inspected, starts off with the start node
# closed_list is a list of nodes which have been visited
# and who's neighbors have been inspected
open_list = set([start_node])
closed_list = set([])
# g contains current distances from start_node to all other nodes
# the default value (if it's not found in the map) is +infinity
g = {}
g[start_node] = 0
# parents contains an adjacency map of all nodes
parents = {}
parents[start_node] = start_node
while len(open_list) > 0:
n = None
# find a node with the lowest value of f() - evaluation function
for v in open_list:
if n == None or g[v] + self.h(v) < g[n] + self.h(n):
n = v;
if n == None:
print('Path does not exist!')
return None
# if the current node is the stop_node
# then we begin reconstructin the path from it to the start_node
if n == stop_node:
reconst_path = []
while parents[n] != n:
reconst_path.append(n)
n = parents[n]
reconst_path.append(start_node)
reconst_path.reverse()
print('Path found: {}'.format(reconst_path))
return reconst_path
# for all neighbors of the current node do
for (m, weight) in self.get_neighbors(n):
# if the current node isn't in both open_list and closed_list
# add it to open_list and note n as it's parent
if m not in open_list and m not in closed_list:
open_list.add(m)
parents[m] = n
g[m] = g[n] + weight
# otherwise, check if it's quicker to first visit n, then m
# and if it is, update parent data and g data
# and if the node was in the closed_list, move it to open_list
else:
if g[m] > g[n] + weight:
g[m] = g[n] + weight
parents[m] = n
if m in closed_list:
closed_list.remove(m)
open_list.add(m)
# remove n from the open_list, and add it to closed_list
# because all of his neighbors were inspected
open_list.remove(n)
closed_list.add(n)
print('Path does not exist!')
return None
Давайте рассмотрим пример со следующим взвешенным графом:
Мы запускаем код так:
adjacency_list = {
'A': [('B', 1), ('C', 3), ('D', 7)],
'B': [('D', 5)],
'C': [('D', 12)]
}
graph1 = Graph(adjacency_list)
graph1.a_star_algorithm('A', 'D')
И выход будет выглядеть так:
Path found: ['A', 'B', 'D'] ['A', 'B', 'D']
Таким образом, оптимальный путь от A до D , найденный с помощью A*, равен A -> B -> D .
Вывод
A* – это очень мощный алгоритм с почти неограниченным потенциалом. Однако она хороша лишь настолько, насколько хороша ее эвристическая функция, которая может быть весьма изменчивой, учитывая природу проблемы.
Он нашел применение во многих программных системах, от машинного обучения и поисковой оптимизации до разработки игр, где персонажи NPC перемещаются по сложной местности и препятствиям, чтобы добраться до игрока.