Comments 31
А как же A*, в котором есть эвристика? Интересно бы было почитать про возможности нахождения пути с использованием GPU.
+2
Когда я писал эту статью, я забыл упомянуть в заголовке, что я рассматриваю только взвешенные графы.
-1
Разве волновой алгоритм не подходит для любого графа?
0
Волново́й алгори́тм — алгоритм, позволяющий найти минимальный путь в графе с рёбрами единичной длины.
0
Не вижу проблем его использовать для ребер разного веса.
+2
в случае взвешенного графа асимптотика что поиска в глубину, что поиска в ширину начинает сильно отличаться от O(e + v) в худшую сторону, грубо говоря мы в каждую вершину вместо одного раза сможем попасть ~v^2 раз каждый раз релаксируя результат и пуская новую волну, что и говорит о его неприменимости для поиска кратчайших путей
0
Вроде, зависит от реализации?
0
зависит от теста, и в вашем примере граф невзвешенный, очевидно
имеется в виду случай, когда путь через меньшее количество ребер до цели будет длиннее, чем путь через большее количество за счет подбора весовых коэффициентов, тогда будет невозможно выполнить ограничение входа в каждую вершину только одним разом, и, как следствие, алгоритм теряет всю свою привлекательность
имеется в виду случай, когда путь через меньшее количество ребер до цели будет длиннее, чем путь через большее количество за счет подбора весовых коэффициентов, тогда будет невозможно выполнить ограничение входа в каждую вершину только одним разом, и, как следствие, алгоритм теряет всю свою привлекательность
0
Из той же статьи в википедии.
Практическое применениеИ да, как правильно заметили, то, что он ориентирован на ребра единичной длинны не мешает модифицировать его для прочих нужд.
Волновой алгоритм — один из основных при автоматизированной трассировке (разводке) печатных плат. Также одно из характерных применений волнового алгоритма — поиск кратчайшего расстояния на карте в стратегических играх.
0
В одном своём проекте я использую А* именно в взвешенном графе. Веса неотрицательные. Просто А* не считается базовым с точки зрения математики, потому что там самое важное — эвристическая функция оценки расстояния.
0
Почему бы для вашего псевдокода не использовать тег source?
<source lang="java">
<!-- Code here -->
</source>
0
+2
К сожалению, А* показывает не очень хорошую скорость. И, например, в стратегии, где надо пускать много юнитов по длинному пути (выбрали пачку из 100 юнитов и шлём на вражескую базу за речкой в другом конце карты) в обычном виде будет страшно глючить.
Я бы с удовольствием почитал об оптимизациях этих алгоритмов. Были мысли о кешировании результата (но как корректно применить кеш, что делать при динамически меняющейся карте) и (бить карту на блоки/использовать контрольные точки). Но всё-же хотелось бы почитать про готовые решения.
Я бы с удовольствием почитал об оптимизациях этих алгоритмов. Были мысли о кешировании результата (но как корректно применить кеш, что делать при динамически меняющейся карте) и (бить карту на блоки/использовать контрольные точки). Но всё-же хотелось бы почитать про готовые решения.
0
И да, в дополнение — "Сравнение алгоритмов поиска маршрутов в StarCraft и StarCraft 2"
0
Интересно, а какой алгоритм на какой основе показывает лучший результат? А* с хорошей эвристикой, по-моему, лучший алгоритм для нахождения пути на клетчатом поле.
0
Имхо, тоже, но без оптимизации он слишком медлителен.
Был пример на Флеше. При более менее загруженной карте (а она всего лишь 60*60) — поиск пути для одного юнита — 200 мс:
Тут есть ещё одна дилемма для оптимизации — считать ли первый найденный маршрут самым коротким, или поискать более короткий?
Был пример на Флеше. При более менее загруженной карте (а она всего лишь 60*60) — поиск пути для одного юнита — 200 мс:
Тут есть ещё одна дилемма для оптимизации — считать ли первый найденный маршрут самым коротким, или поискать более короткий?
+1
Если соблюдено некое условие для эвристической функции, то алгоритм всегда находит минимальный путь (или один из минимальных). Условие звучит примерно так, что оценка не должна превышать минимально допустимый теоретический путь. Могу ошибаться.
0
К сожалению, А* показывает не очень хорошую скорость.Базовый — не значит оптимальный или лучший. Хотя А* достаточно сбалансирован для большинства задач. Базовый — это основной или простейший, на котором легко показать основные задачи алгоритма в целом. ИМХО конечно.
0
0
Насколько я помню, этот алгоритм оптимизирует решения нескольких функций в многомерном пространстве (обычно больше 2). Он слишком далёк от реального поиска пути.
0
А если сделать одну функцию минимума и одну функцию оценки, и искать кратчайший путь по этим двум функциям? Транспортные задачи симплекс-метод решает на ура, самое длинное решение, которое я видел — 20 итераций. Хотя да, возможно, что составление матрицы потребует больше итераций, чем любой из приведенных алгоритмов.
0
Действительно, в этой статье алгоритмы поиска в графе описаны в больше мере с математической точки зрения, нежели с точки зрения гейм-дева.
В играх поиск пути обычно заканчивается на А* и компании ( IDA, D*, fringe search ) а дальше идут специфичные для представления и топологии карты оптимизации — иерархический поиск, мемоизация, прогрессивное улучшение, адаптивный поиск итп. Если же игра — интерактивная, то найденное решение требует дальнейшей обработки с учетом динамических коллизий, сглаживания и всего остального.
Кстате, стоит упомянуть, что поиск на графе даже в гейм-деве не ограничивается картами. Это так же ИИ, планирование и многое другое.
В играх поиск пути обычно заканчивается на А* и компании ( IDA, D*, fringe search ) а дальше идут специфичные для представления и топологии карты оптимизации — иерархический поиск, мемоизация, прогрессивное улучшение, адаптивный поиск итп. Если же игра — интерактивная, то найденное решение требует дальнейшей обработки с учетом динамических коллизий, сглаживания и всего остального.
Кстате, стоит упомянуть, что поиск на графе даже в гейм-деве не ограничивается картами. Это так же ИИ, планирование и многое другое.
+2
Кратчайшие пути не только в играх нужны. В связи есть целое направление по проектированию сетей связи с целью получить наиболее оптимальный вариант сети с заданной надёжностью.
0
Разумеется, но в данном случае автор в самом начале статьи сослался на гейм-дев.
0
вот тут тоже есть мануалы по алгоритмам
algolist.manual.ru/maths/graphs
algolist.manual.ru/maths/graphs
0
Sign up to leave a comment.
Базовые алгоритмы нахождения кратчайших путей во взвешенных графах