Войти
ZhekasФорум

Поэлементный поиск кратчайшего пути в пространстве (комментарии)

Страницы: 1 2 Следующая »
#0
21:31, 21 мая 2010

Поэлементный поиск кратчайшего пути в пространстве (комментарии)

Это сообщение сгенерировано автоматически.


#1
21:31, 21 мая 2010

хм..а чем данный алгоритм отличается от поиска в ширину или алгоритма Дейкстры?

#2
22:11, 21 мая 2010

Ну тут основной аспект в том что мы при этом можем использовать разные направления...

#3
22:32, 21 мая 2010

что Вы подразумеваете под разными направлениями?? движение по вертикали, горизонтали, диагонали?
пока что я вижу просто алгоритм полного перебора, который не стал бы использовать в реальных задачах. намного эффективнее использовать WA*

#4
22:47, 21 мая 2010

ммм... это поиск в ширину... по крайней мере на такой малой карте точно.

#5
23:27, 21 мая 2010

f204
а можно поподробней про этот метод, эту статью я отправил на конференцию в Донецке.... ничего нового я не изобрел вообще будем говорить так просто на каком-то этапе метод этого алгоритма мне пригодился

#6
0:42, 22 мая 2010

WA* это взвешенная версия алгоритма A*
т.е. для в алгоритме А* для выбора последующей клетки для раскрытия используется f-значение:
f=g+h, где g-все пути из начальной точки в текущую, h-значение эвристики, оценивающее вес пути из текущей в конечную.
в WA* используется:
f=g+w*h, где w какоето число. при w=1 получаем просто А*, при w>1 алгоритм раскрывает меньше клеток при поиске пути, что иногда является достаточно эффективным. недостатком использования w>1 является тот факт, что найденный путь может быть не кратчайшим.

#7
0:06, 25 мая 2010

Поиск в ширину работает за O(M) где M - количество ребер. В графе, описанном в статье, это равно, что O(N), где N - количество вершин, потому что количество ребер пропорционально количеству вершин.
Предложенный в статье алгоритм (который называется волновой) работает за O(N^2) в худшем случае, потому что на каждой итерации (которых в худшем случае сравнимо с N, если надо пройти по всем клеткам лабиринта) надо пройтись по всем вершинам и найти те, которые имеют нужное удаление (про поддержание очереди, по крайней мере, в статье не сказано).

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

#8
15:23, 25 мая 2010

Алгоритм хорош тем, что прост для понимания и пригодится новичкам.

Недостаток статьи, на мой взгляд, не описано условие прекращения цикла, когда из точки а нельзя пройти в точку б.

#9
15:25, 25 мая 2010

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

>>Все равно для поиска пути нужны какие-то эвристики, нет?
да, если только у тебя не глобальная карта с десятком пунктов, которые в лоб перебрать можно.

>>Есть примеры, когда в игре на большой карте применяют алгоритм поиска пути, который возвращает гарантированно кратчайший путь?
Что есть "большая карта" в твоем понимании?

>>Недостаток статьи, на мой взгляд, не описано условие прекращения цикла, когда из точки а нельзя пройти в точку б.
Если говорить о недостатках, то было неплохо еще добавить, что "волну" можно пускать одновременно и из пункта назначения, что при минимальном усложнении даст неиллюзорный профит.

#10
21:07, 25 мая 2010

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

>> Что есть "большая карта" в твоем понимании?
Ну допустим. Есть карта 1000 на 1000, то есть миллион вершин. Это порядка 4КК ребер.
Возьмем не ширину, а дийкстру, допустим что у ребер есть веса. Сложность E log E, то есть очень грубо говоря это займет 0.2 секунды на поиск пути в худшем случае. Полагаю, что худший случай никогда не наступит. Вот и вопрос - реально кто-то на практике такое применял, или все-таки всегда используют эвристики?

#11
22:09, 25 мая 2010

>>, которым в школе учат искать путь, когда проходят паскаль.
фигасе, меня бы в школе этому учили.
>> Есть карта 1000 на 1000, то есть миллион вершин.
Ну в играх такое не используют, думаю. Разве ММО, но там имхо, нет нужды поиска пути на такие расстояния. Впрочем, не вижу реальных трудностей.
Что касается эвристик, то  Дейкстра - это просто А* с эвристикой == 0, то есть поиск в ширину, то есть предложенный алгоритм)) . С учетом того, что эвристика на клетчатом поле, даже с учетом весов, никакой сложности не представляет, почему не сделать А*, и получить просто эпический профит для описанной ситуации?

#12
22:09, 25 мая 2010

давайте посмотрим.
найденный путь алгоритмом А* на полностью проходимом графе (цветом обозначены рассмотренные клетки)
a* | Поэлементный поиск кратчайшего пути в пространстве (комментарии)
и алгоритм Дейкстры на том же графе
Дейкстра | Поэлементный поиск кратчайшего пути в пространстве (комментарии)

разница очевидна

#13
0:14, 26 мая 2010

GeniusIsme
f204
Спасибо, это то что я хотел понять.

#14
14:54, 26 мая 2010

>> можно пускать одновременно и из пункта назначения
Хотя да, статья скорее предназначена для понимания алгоритма и чем меньше в ней тонкостей, тем она проще, а значит лучше )))

Страницы: 1 2 Следующая »
ZhekasФорум

Тема в архиве.