Найти путь
Pathfinding или pathfinding — это построение с помощью компьютерного приложения кратчайшего маршрута между двумя точками. Это более практичный вариант решения лабиринтов . Эта область исследований в значительной степени основана на алгоритме Дейкстры для поиска кратчайшего пути на взвешенном графе .
Поиск пути тесно связан с задачей поиска кратчайшего пути в рамках теории графов , которая исследует, как определить путь, который лучше всего соответствует некоторым критериям (кратчайший, самый дешевый, самый быстрый и т. д.) между двумя точками в большой сети.
По своей сути метод поиска пути ищет граф , начиная с одной вершины и исследуя соседние узлы , пока не будет достигнут узел назначения, как правило, с целью поиска самого дешевого маршрута. Хотя методы поиска по графу, такие как поиск в ширину, могли бы найти маршрут, если бы им дали достаточно времени, другие методы, которые «исследуют» граф, имели бы тенденцию достигать пункта назначения раньше. Аналогией может быть человек, идущий по комнате; вместо того, чтобы заранее изучать все возможные маршруты, человек обычно идет в направлении пункта назначения и отклоняется от пути только для того, чтобы избежать препятствия, и делает отклонения как можно меньшими.
Две основные проблемы поиска пути: (1) найти путь между двумя узлами в графе ; и (2) задача о кратчайшем пути — найти оптимальный кратчайший путь . Базовые алгоритмы, такие как поиск в ширину и в глубину, решают первую проблему, перебирая все возможности; начиная с данного узла, они перебирают все потенциальные пути, пока не достигнут узла назначения. Эти алгоритмы работают за линейное время, где V — количество вершин, а E — количество ребер между вершинами.
Более сложной задачей является поиск оптимального пути. Исчерпывающий подход в этом случае известен как алгоритм Беллмана-Форда , который дает временную сложность или квадратичное время. Однако не обязательно перебирать все возможные пути, чтобы найти оптимальный. Такие алгоритмы, как A* и алгоритм Дейкстры, стратегически устраняют пути либо с помощью эвристики , либо с помощью динамического программирования . Исключая невозможные пути, эти алгоритмы могут достигать временной сложности до [1]
Вышеупомянутые алгоритмы являются одними из лучших общих алгоритмов, которые работают с графом без предварительной обработки. Тем не менее, в практических системах маршрутизации поездок даже лучшие временные сложности могут быть достигнуты с помощью алгоритмов, которые могут предварительно обрабатывать граф для достижения лучшей производительности. [2] Одним из таких алгоритмов являются иерархии сжатия .
