Интеллект — это сила человеческого рода; мы использовали его, чтобы улучшить нашу жизнь. Затем мы создали концепцию искусственного интеллекта, чтобы усилить человеческий интеллект и способствовать развитию и процветанию цивилизаций, как никогда раньше.
ИИ помогает нам решать задачи различной сложности. Вычислительные задачи, такие как задачи поиска пути, можно решить с помощью ИИ. Поисковые задачи, где вам нужно найти путь из одной точки в другую, скажем, из точки А в точку Б. Иногда вам нужно решить ее, сопоставив эти задачи с графами, где все возможные результаты представлены узлами. Алгоритм A* является ответом на эти проблемы.
Созданный в рамках проекта Shakey, направленного на создание мобильного робота с искусственным интеллектом для планирования своих действий, A* изначально разрабатывался как общий алгоритм обхода графа. Он широко используется при решении задач поиска пути в видеоиграх. Благодаря своей гибкости и универсальности его можно использовать в самых разных контекстах. A* составлен с использованием взвешенных графов, что означает, что он может найти лучший путь с наименьшими затратами с точки зрения расстояния и времени. Это делает A* информативным алгоритмом поиска для поиска наилучших результатов. Давайте подробно рассмотрим различные аспекты A*.
Читайте о бизнес-приложениях искусственного интеллекта.
Что такое алгоритм A* в искусственном интеллекте?
Самое важное преимущество алгоритма A* search, отличающее его от других методов обхода, заключается в том, что у него есть мозг. Это делает A* очень умным и значительно опережает другие традиционные алгоритмы.
Рассмотрим диаграмму ниже:
Давайте попробуем понять основные концепции ИИ и понять, как работает алгоритм A*. Представьте себе огромный лабиринт, слишком большой, чтобы добраться до конечной точки вручную можно за несколько часов. После того, как вы завершите его пешком, вам нужно идти за другим. Это означает, что вы в конечном итоге потратите много времени и усилий, чтобы найти возможные пути в этом лабиринте. Теперь вы хотите, чтобы это занимало меньше времени. Чтобы упростить задачу, мы будем рассматривать этот лабиринт как задачу поиска и попытаемся применить ее к другим возможным лабиринтам, с которыми мы можем столкнуться в свое время, при условии, что они следуют той же структуре и правилам.
В качестве первого шага к преобразованию этого лабиринта в задачу поиска нам нужно определить эти шесть вещей.
- Набор предполагаемых состояний, в которых мы могли бы находиться
- Начальное и конечное состояние
- Способ решить, достигли ли мы конечной точки
- Набор действий при возможных изменениях направления/пути
- Функция, которая сообщает нам о результате действия
- Набор затрат, возникающих в различных состояниях/путях движения
Чтобы решить задачу, нам нужно сопоставить пересечения с узлами (обозначены красными точками) и всеми возможными способами движения к краям (обозначены синими линиями).
A обозначает начальную точку и B обозначает конечную точку. Мы определяем начальную и конечную точки в узлах A и B соответственно.
Если мы используем неосведомленный алгоритм поиска, это будет похоже на поиск слепого пути, в то время как информированный алгоритм для поисковой задачи выберет путь, который приблизит вас к ваш пункт назначения. Например, рассмотрим кубик Рубика; у него есть много предполагаемых состояний, в которых вы можете находиться, и это очень усложняет решение. Это требует использования управляемого алгоритма поиска для поиска решения. Это объясняет важность A*.
В отличие от других алгоритмов, A* решает предпринять шаг только в том случае, если он убедительно разумен и разумен в соответствии со своими функциями. Это означает, что он никогда не рассматривает какие-либо неоптимальные шаги. Вот почему A* — популярный выбор для систем искусственного интеллекта, которые воспроизводят реальный мир, таких как видеоигры и машинное обучение.
A* Этапы алгоритма
- Во-первых, добавьте начальный узел в список открытых
- Затем повторите следующий шаг
– В открытом списке найдите клетку с наименьшей стоимостью F — и это обозначает текущую клетку.
– Теперь переходим к закрытой клетке.
– Рассмотрим 8 клеток, примыкающих к текущей клетке, и
- Игнорируйте его, если он находится в закрытом списке или если он не работает. Сделайте следующее, если это работает
- Проверьте, есть ли он в открытом списке; если нет, добавьте его. Вам нужно сделать текущий квадрат родителем этого квадрата. Теперь вы будете записывать различные затраты квадрата, такие как затраты F, G и H.
- Если он находится в открытом списке, используйте стоимость G для измерения лучшего пути. Чем ниже стоимость G, тем лучше путь. Если этот путь лучше, сделайте текущий квадрат родительским. Теперь вам нужно пересчитать другие оценки — оценки G и F этого квадрата.
– Вы остановитесь:
- Если вы найдете путь, вам нужно проверить закрытый список и добавить в него целевой квадрат.
- Пути нет, если открытый список пуст и вы не смогли найти целевую клетку.
3. Теперь вы можете сохранить путь и работать в обратном направлении, начиная с целевой клетки, переходя к родительской клетке из каждой клетки, по которой вы идете, пока она не приведет вас к начальной клетке. Теперь вы нашли свой путь.
Почему алгоритм поиска A* предпочтительнее?
Легко придать движение предметам. Но найти путь не так-то просто. Это сложное упражнение. Объясняет это следующая ситуация.
Задача состоит в том, чтобы вывести единицу, которую вы видите внизу схемы, на ее вершину. Вы видите, что ничто не указывает на то, что объект не должен идти по пути, обозначенному розовыми линиями. Поэтому он выбирает двигаться таким образом. Как и когда он достигает вершины, он должен изменить свое направление из-за препятствия в форме буквы «U». Затем он меняет направление, огибает препятствие, чтобы достичь вершины. В отличие от этого, A* просканировал бы область над объектом и нашел бы короткий путь (обозначенный синими линиями). Таким образом, алгоритмы поиска пути, такие как A*, помогают вам планировать, а не ждать, пока вы обнаружите проблему. Они действуют проактивно, а не реагируют на ситуацию. Недостатком является то, что он немного медленнее, чем другие алгоритмы. Вы можете использовать комбинацию обоих для достижения лучших результатов — алгоритмы поиска пути дают более полную картину и длинные пути с препятствиями, которые меняются медленно; и алгоритмы движения для локальной картины и коротких путей с препятствиями, которые меняются быстрее.
Алгоритм A* и его основные понятия
Алгоритм A* работает на основе эвристических методов, что позволяет достичь оптимальности. A* — это другая форма алгоритма поиска лучших. Оптимальность позволяет алгоритму найти наилучшее возможное решение проблемы. Такие алгоритмы также предлагают полноту: если существует какое-либо решение существующей проблемы, алгоритм обязательно его найдет.
Когда A* сталкивается с проблемой, он сначала вычисляет стоимость перехода к соседним узлам и выбирает узел с наименьшей стоимостью. Если f(n) обозначает стоимость, A* выбирает узел с наименьшим значением f(n). Здесь «n» обозначает соседние узлы. Расчет значения можно выполнить, как показано ниже:
f(n)=g(n)+h(n)f(n)=g(n)+h(n)
g( n) = показывает значение кратчайшего пути от начального узла к узлу n
h(n) = эвристическая аппроксимация значения узла
Значение эвристики играет важную роль в эффективности A * алгоритм. Чтобы найти наилучшее решение, вам, возможно, придется использовать различные эвристические функции в зависимости от типа проблемы. Однако создание этих функций — сложная задача, и это основная проблема, с которой мы сталкиваемся в ИИ.
Что такое эвристическая функция?
Эвристика, как ее просто называют, эвристическая функция, которая помогает ранжировать альтернативы, указанные в алгоритме поиска на каждом из его шагов. Он может либо производить результат сам по себе, либо работать в сопряжении с заданным алгоритмом для создания результата. По сути, эвристическая функция помогает алгоритмам быстрее и эффективнее принимать наилучшее решение. Это ранжирование производится на основе наилучшей доступной информации и помогает алгоритму выбрать наилучшую возможную ветвь для следования. Допустимость и непротиворечивость — два фундаментальных свойства эвристической функции.
Допустимость эвристической функции
Эвристическая функция допустима, если она может эффективно оценить реальное расстояние между узлом «n» и конечным узлом. Он никогда не завышает, а если и завышает, то обозначается буквой «d», что также означает точность решения.
Непротиворечивость эвристической функции
Эвристическая функция непротиворечива, если оценка данной эвристической функции оказывается равной или меньшей, чем расстояние между целью (n) и соседом, а также стоимость, рассчитанная для достижения этого соседа.
A* действительно очень мощный алгоритм, используемый для повышения производительности искусственного интеллекта. Это один из самых популярных алгоритмов поиска в ИИ. Небеса — это предел, когда речь заходит о потенциале этого алгоритма. Однако эффективность алгоритма A* сильно зависит от качества его эвристической функции. Интересно, почему этот алгоритм предпочтительнее и используется во многих программных системах? Нет ни одного аспекта ИИ, в котором алгоритм A* не нашел бы своего применения. От поисковой оптимизации до игр, робототехники и машинного обучения — алгоритм A* является неотъемлемой частью умной программы.
Реализация с Python
В этом разделе мы узнаем, как можно использовать алгоритм A* для поиска наиболее рентабельного пути в графе. Рассмотрим следующий график ниже:
Числа, написанные на ребрах, представляют собой расстояние между узлами, а числа, написанные на узлах, представляют собой эвристические значения. Давайте найдем наиболее экономичный путь для достижения из начального состояния A в конечное состояние G с использованием алгоритма A*.
Начнем с узла A. Поскольку A является начальным узлом, поэтому значение g(x) для A равно нулю, а из графика мы получаем эвристическое значение A равно 11, поэтому
- g(x) + h(x) = f(x)
- 0+ 11 =11
- Таким образом, для A мы можем написать
- A=11
Теперь из A мы можем перейти в точку B или точку E, поэтому мы вычисляем f(x) для каждой из них.
- A → B = 2 + 6 = 8
- A → E = 3 + 6 = 9
Поскольку стоимость перехода A → B меньше, мы продвигаемся вперед по этому пути и вычисляем f(x) для дочерних узлов B.
Поскольку пути между C и G нет, эвристическая стоимость устанавливается бесконечной или очень высокой.
- A → B → C = (2 + 1) + 99= 102
- A → B → G = (2 + 9 ) + 0 = 11
Здесь путь A → B → G имеет наименьшую стоимость, но она все же больше, чем стоимость пути A → E, поэтому мы исследуем этот путь дальше.
A → E → D = (3 + 6) + 1 = 10
Сравнивая стоимость A → E → D со всеми путями, которые мы получили до сих пор, и поскольку эта стоимость меньше всего, мы движемся вперед по этому пути. И вычислить f(x) для потомков D
A → E → D → G = (3 + 6 + 1) +0 =10
Теперь, сравнивая все пути, которые ведут нас к цели, мы приходим к выводу, что A → E → D → G — наиболее рентабельный путь из A в G.
Затем мы пишем программу на Python, которая может найти наиболее экономичный путь, используя алгоритм звездочки.
Во-первых, мы создаем два набора, а именно открытый и закрытый. Открытый содержит узлы, которые были посещены, но их соседи еще не исследованы. С другой стороны, close содержит узлы, которые были посещены вместе с их соседями.
<code>def aStarAlgo(start_node, stop_node):
open_set = set(start_node)
closed_set = set()
g = {} #store distance from starting node
parents = {}# parents contains an adjacency map of all nodes
#ditance of starting node from itself is zero
g[start_node] = 0
#start_node is root node i.e it has no parent nodes
#so start_node is set to its own parent node
parents[start_node] = start_node
while len(open_set) > 0:
n = None
#node with lowest f() is found
for v in open_set:
if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
n = v
if n == stop_node or Graph_nodes[n] == None:
pass
else:
for (m, weight) in get_neighbors(n):
#nodes 'm' not in first and last set are added to first
#n is set its parent
if m not in open_set and m not in closed_set:
open_set.add(m)
parents[m] = n
g[m] = g[n] + weight
#for each node m,compare its distance from start i.e g(m) to the
#from start through n node
else:
if g[m] > g[n] + weight:
#update g(m)
g[m] = g[n] + weight
#change parent of m to n
parents[m] = n
#if m in closed set,remove and add to open
if m in closed_set:
closed_set.remove(m)
open_set.add(m)
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:
path = []
while parents[n] != n:
path.append(n)
n = parents[n]
path.append(start_node)
path.reverse()
print('Path found: {}'.format(path))
return path
# remove n from the open_list, and add it to closed_list
# because all of his neighbors were inspected
open_set.remove(n)
closed_set.add(n)
print('Path does not exist!')
return None
#define fuction to return neighbor and its distance
#from the passed node
def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
else:
return None
#for simplicity we ll consider heuristic distances given
#and this function returns heuristic distance for all nodes
def heuristic(n):
H_dist = {
'A': 11,
'B': 6,
'C': 99,
'D': 1,
'E': 7,
'G': 0,
}
return H_dist[n]
#Describe your graph here
Graph_nodes = {
'A': [('B', 2), ('E', 3)],
'B': [('C', 1),('G', 9)],
'C': None,
'E': [('D', 6)],
'D': [('G', 1)],
}
aStarAlgo('A', 'G')
</code>
Вывод:
Откройте для себя карьеру в AIML сегодня!
