Назад к основам — Божественные алгоритмы Том III: Алгоритм A*

Вы здесь!

ХА! Я вижу, вы… нашли свой путь к моему блогу *BA DUM TS*. Хорошо, оглядываясь назад, эта шутка не будет иметь смысла, пока я не объясню тему сегодняшнего блога. Но, если вам удалось найти подсказку в моем предыдущем блоге, возможно, вы поняли, о чем я говорю, и шутка, вероятно,… не прошла мимо вас *BA DU… хорошо извините, последний каламбур, обещание. Если вы не читали мой последний блог, что должно быть удивительно, или не нашли подсказку, вот она:

В конце концов, вы же не хотите застрять в лабиринте.

Итак, без лишних слов, добро пожаловать обратно в раздел «Назад к основам — Божественные алгоритмы», где мы говорим об алгоритме A*.

Алгоритм поиска A* — один из лучших и наиболее часто используемых алгоритмов для реализации поиска пути и обхода графа. Сегодня мы сосредоточимся на использовании алгоритма для поиска пути. А теперь пристегнитесь и давайте поговорим об А*!

Студент? Хозяин!

Итак, что такое алгоритм A*? В отличие от предыдущих блогов, где алгоритмы находили кратчайший путь в дереве, что является довольно абстрактным понятием, когда речь идет о реальных приложениях, этот алгоритм находит кратчайший путь в реальных ситуациях. Примером реальной ситуации может быть, например, двухмерная карта сетки. Правильный способ попытаться объяснить, как работает этот алгоритм, — показать пример:

Здесь мы уже видим одно ключевое различие между выполнением других алгоритмов на дереве и выполнением A* на сетке 2D-карты. Здесь мы видим, что не каждый путь доступен. У нас есть заблокированные пути, которые алгоритм не может пройти. Это делает варианты использования этого алгоритма менее абстрактными и более ориентированными на реальную жизнь, как упоминалось выше. Подумайте о дороге, которая является частью карты. Дороги часто блокируют из-за ремонта, блокируют из-за того, что закрыты, или даже из-за пробок. Вот где A* действительно сияет.

Мало того, что А* способен находить эти препятствия, он также запрограммирован выбирать оптимальный путь. Если мы посмотрим на приведенный выше пример, у нас будет представление о принятии решений, которые выполняет алгоритм. Вместо того, чтобы идти по маршруту [4,2] → [4,3] → [3,3], алгоритм выбрал маршрут [4,2] → [3,3], исключая один дополнительный шаг. Оптимальное принятие решений и обнаружение блокировки — вот почему алгоритм A* является наиболее популярным и наиболее часто используемым алгоритмом в отношении поиска пути.

Получите пятёрку*

Терминология

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

• F: общая стоимость достижения одного узла на графике. Это рассчитывается путем выполнения G+H. Но что такое G и что такое H?
• G: расстояние между текущим узлом, который в данный момент посещает алгоритм, и начальным узлом, на котором алгоритм запустился.
• H: Эвристика. Это означает расчетное расстояние между текущим узлом, который в данный момент посещает алгоритм, и конечным узлом. Это можно вычислить с помощью таких способов, как теорема Пифагора

Имейте в виду, что это не мои соглашения об именах, а это означает, что я не просто выбрал случайные буквы. Это фактические имена переменных, согласованные сообществом информатики. Сейчас эти буквы кажутся неактуальными, однако они имеют решающее значение, когда мы проходим этапы алгоритма. Вот шаги алгоритма, объясненные с помощью вышеупомянутых букв:

• Инициализируйте свои списки.Первое, что нам нужно сделать, это инициализировать два списка. Список открытых узлов и список закрытых узлов. Список открытых узлов будет содержать все непосещенные и жизнеспособные узлы. Список закрытых узлов будет содержать посещенные или нежизнеспособные узлы.
• Начальный узел: добавьте начальный узел лабиринта в открытый список.
• Теперь время повторить некоторые шаги!
• 1 – Самое низкое значение F. Ранее мы объяснили, что такое значение F. После вычисления значения F для узлов в открытом списке мы пытаемся найти наименьшее значение F. Получив его, мы перемещаем его в список закрытых/посещенных узлов. Назовем это текущим квадратом!
• 2- Для каждого соседнего квадрата, окружающего текущий квадрат (всего 8), мы делаем шаги A-C
• A- Если это заблокированный узел или он находится в закрытом списке, мы пропускаем этот конкретный квадрат. Если нет, переходим к шагу B
• B- Если он еще не был распознан как часть открытого списка, мы добавляем его туда, мы также распознаем его как родительский узел для текущего узла, на котором мы находимся. Мы также записываем F, G, H. Как правило, вы всегда записываете эти значения. Они также известны как показатели.
• C- Если текущая клетка находится в открытом списке, вы проверяете балл F. Если оценка F ниже, мы используем этот новый текущий путь и обновляем родительский узел. Текущий путь обновляется путем возврата от родительского узла к начальному узлу.
• Стоп!. Это шаги, которые вы продолжаете выполнять до тех пор, пока не выполните одно из следующих действий:
• 1- Найдите целевой узел, обычно указанный кем-то, добавляющим целевой узел в список закрытых узлов.
• 2- Не было успешной попытки найти целевой узел, на что обычно указывает пустой список открытых узлов, который никогда не попадал в целевой узел.

Глядя на это, может показаться, что это сложный алгоритм. Однако реализация кода, которую я собираюсь представить в следующем разделе, определенно будет полезна для более глубокого понимания. Если этого недостаточно, вот анимация алгоритма A*, которая поможет облегчить ожидание, пока вы не увидите код!

🎶 Научи меня программировать, научи меня, научи меня кодировать 🎶

У меня появилась привычка включать реализацию кода в темы блогов, которые я пишу, как я делал с Деревьями поиска RB и Алгоритмом Беллмана-Форда. Люди нашли это очень полезным! Всегда полезно закрепить теоретические знания кодом. Тем более, что, как ни странно, программировать алгоритм A* не так уж и сложно. Еще один балл для A*!

Вместо включения реализации кода с веб-сайта по информатике, как я делал в своих предыдущих блогах, на этот раз у меня есть небольшой сюрприз. Мой коллега в Capgemini Дэниел Олиманс фактически работал над реализацией алгоритма A* для побочного проекта, над которым он работает. Я спросил его, могу ли я использовать его ОЧЕНЬ хорошо сделанную реализацию, и он был вполне готов к этой идее! Итак, без лишних слов, вот Mr. Реализация Олиманса алгоритма A* с использованием Java

Сказав это, чтобы попытаться привлечь как можно больше людей, Даниэль самоотверженно направил меня на веб-сайт, на котором есть реализации, отличные от его собственной, A* с использованием Python и C++, на всякий случай, если кто-то предпочитает эти языки Java.

Случаи применения

Как мы уже говорили ранее, это алгоритм кратчайшего пути, поэтому варианты использования, упомянутые в моем блоге Дейкстры, также применимы здесь. Но есть один вариант использования, который предпочитает использование A* другим алгоритмам, и это самый короткий поиск пути в играх. Причина, по которой люди используют это в играх, заключается в том, что A * довольно быстр, а также учитывает заблокированные проходы, которые игрок не может пройти в игре. Итак, всякий раз, когда вы видите врага с искусственным интеллектом, который, например, охотится за вами, путь, который он выбирает, чтобы следовать за вами, вероятно, использует алгоритм A *!

Что теперь?

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

• Доказательство полноты
• Доказательство оптимальности

Эти две вещи берут теоретическую концепцию, такую ​​как алгоритм, и экстраполируют ее, а каратэ нарезает ее в другую теоретическую область! Я не буду углубляться в то, что означают оба эти термина, но кто знает, что нас ждет в будущем? Тем не менее, это очень интересные темы, которые помогут укрепить ваши теоретические знания!

Надеюсь, вам понравилась эта статья! Написание заняло больше всего времени по сравнению со всеми моими предыдущими. Вы также должны проверить все другие кодовые проекты Дэниела Олиманса и проверить его ближайшие будущие проекты, у него много чего готовит! На этом пока все, увидимся в следующем блоге Back to Basics!

Ресурсы

Чтобы освежить свои знания об алгоритме A*, мне пришлось провести небольшое исследование. Ниже вы найдете все ресурсы, которые я использовал, чтобы написать этот блог для вас!