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