Практическое применение алгоритмов поиска пути.

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

Во-первых, у этих алгоритмов есть прямое назначение – поиск пути на модели реальной местности (как правило, граф или навигационная сетка), что позволяет активно использовать эти алгоритмы и их модификации в навигационных программах, наиболее простым примером которых является система навигации GPS(Global Positioning System – глобальная система позиционирования).

Также, поиск пути по реальной местности актуален в роботостроении, поскольку в функции многих роботов входит перемещение по местности, а если эта местность не имеет форму выпуклой однородной геометрической фигуры, то для поиска пути по ней придётся использовать более или менее сложный алгоритм поиска пути.

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

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

Заключение

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

Более подробную информацию о результатах анализа и о самих анализируемых алгоритмов вы можете посмотреть в соответствующих разделах (Основные алгоритмы поиска пути; Сравнительный анализ алгоритмов поиска пути).

Список использованной литературы

1. Ian Millington и John Funge – «AI For Games» оригинальная английская версия.

2. DavidMerz– цикл статей «ОчаровательныйPython» оригинальная английская версия.

3. Иван Орехов – цикл статей «Программирование на Python» оригинальная русская версия.

4. Pierre-MarieBaty– статья «navmeshtutorial» - оригинальная английская версия.

5. Материалы сайта http://ru.wikipedia.org/

6. Материалы сайта http://algolist.ru

7. Материалы сайта http://pmg.org.ru

58