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

Читать далее

https://habr.com/ru/post/708914/?utm_source=habrahabr&utm_medium=rss&utm_campaign=708914

В двух предыдущих постах в блоге на тему анализа поля боя (вычислительное военное мышление и тактический искусственный интеллект), я рассказал, как программа может определять ключевые тактические позиции, как то: закрепленные / не закрепленные фланги и ограниченные / неограниченные пути атаки и отступления. Сегодня мы рассмотрим, как TIGER / MATE выполняет анализ фронтов и реализует маневры проникновения и инфильтрации.

Читать далее

https://habr.com/ru/post/708856/?utm_source=habrahabr&utm_medium=rss&utm_campaign=708856

Приветствую Вас, хабровчане!

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

Читать далее

https://habr.com/ru/post/700462/?utm_source=habrahabr&utm_medium=rss&utm_campaign=700462

Приветствую Вас, хабровчане!

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

Читать далее

https://habr.com/ru/post/699466/?utm_source=habrahabr&utm_medium=rss&utm_campaign=699466

Всем доброго времени суток!

Публикую обзор книги "Грокаем алгоритмы". Автор: Адитья Бхаргава

Стоит читать? Да! Почему? Опишу в статье.

Алгоритмы - важны для программиста, а это лучшая книга для начала их изучения с нуля.

Читать далее

https://habr.com/ru/post/676966/?utm_source=habrahabr&utm_medium=rss&utm_campaign=676966

Привет, меня зовут Валерий Антонов, я руковожу направлением Java в Уральском банке реконструкции и развития (УБРиР). Сегодня расскажу, как я смог переложить систему алгоритмов на, казалось бы никак с этим не связанное хобби, - рыбалку.

Читать далее

https://habr.com/ru/post/657689/?utm_source=habrahabr&utm_medium=rss&utm_campaign=657689

Цель этой статьи — пробудить интерес читателей к удивительному миру и показать различные способы решения таких же интересных головоломок, как «Пятнашки». Создайте свою базу данных с шаблонами и начните решать головоломки менее чем за 50 миллисекунд. Материалом делимся к старту курса по разработке на C#.

Читать далее

https://habr.com/ru/post/655629/?utm_source=habrahabr&utm_medium=rss&utm_campaign=655629

Навигация по лесу

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





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



Как один алгоритм решает обе эти задачи? Давайте начнём с краткого описания того, как работает A*.

Алгоритм A*

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



На каждом шаге алгоритма A* оценивает множество частичных путей и генерирует новые пути, расширяя наиболее многообещающий путь из множества. Для этого A* хранит частичные пути в очереди с приоритетами, отсортированном по приблизительной длине — истинной измеренной длине пути плюс примерное оставшееся расстояние до цели. Это приближение должно быть недооценкой; то есть приближение может быть меньше истинного расстояния, но не больше него. В большинстве задач поиска пути хорошей преуменьшенной оценкой является геометрическое расстояние по прямой от конца частичного пути до конечной точки. Истинный наилучший путь до цели от конца частичного пути может быть длиннее, чем это расстояние по прямой, но не может быть короче.
Читать дальше ->

https://habr.com/ru/post/451642/?utm_source=habrahabr&utm_medium=rss&utm_campaign=451642

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

Классификация лабиринтов

Лабиринты в целом (а значит, и алгоритмы для их создания) можно разбить по семи различным классификациям: размерности, гиперразмерности, топологии, тесселяции, маршрутизации, текстуре и приоритету. Лабиринт может использовать по одному элементу из каждого класса в любом сочетании. Читать дальше ->

https://habr.com/ru/post/445378/?utm_source=habrahabr&utm_medium=rss&utm_campaign=445378

Часть 1. Общий алгоритм поиска

Введение

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



Цель данной статьи — объяснить поиск пути в целом и A* в частности очень понятным и доступным образом, положив таким образом конец распространённому заблуждению о том, что эта тема сложна. При правильном объяснении всё достаточно просто.



Учтите, что в статье мы будем рассматривать поиск пути для игр; в отличие от более академических статей, мы опустим такие алгоритмы поиска, как поиск в глубину (Depth-First) или поиск в ширину (Breadth-First). Вместо этого мы постараемся как можно быстрее дойти от нуля до A*.
Читать дальше ->

https://habr.com/ru/post/444828/?utm_source=habrahabr&utm_medium=rss&utm_campaign=444828