Комментарии 18
поиск Дейкстры находит минимальные пути. по таблице результатов это не так — 115 vs 112. где-то ошибки
A* тоже должен был найти 112, но тут можно списать на нелучшую эвристистику
Это связано с тем, что для Дейкстры и A* мы используем стоимость единичного перехода горизонталь и вертикаль 10, а диагональ 14, потом делим общий результат на 10. А в JPS мы более точно считаем 1 для горизонтали и вертикали, и sqrt(2) для диагонали. Делалось это для демонстации того, что можно по разному считать: для Дейкстры и AStar'а быстрее, но менее точно, а т.к. JPS сам очень эффективный и быстрый, можем пожертвовать капелькой времени, ради точности. Я хотел об этом сказать, но забыл) Спасибо, что напомнили
Правило левой или правой руки не работает для любого лабиранта.
Вероятностый алгоритм Тарри обходит любой лабиринт за минимальное м.о. времени
Вероятностый алгоритм Тарри обходит любой лабиринт за минимальное м.о. времени
Я не полностью понимаю все детали JPS, но не верю, что можно взять и провести прямую линию между двумя клетками, не просмотрев все клетки по пути, что следует из представленной иллюстрации. Алгоритм Дейкстры, в свою очередь, не будет просматривать точки на бОльшем удалении от искомой точки, так что эту иллюстрацию тоже сложно назвать корректной.
JPS тоже рекурентно просматривает множество клеток, но он не совершает с ними много операций(не заносит в открытий и закрытый список, не проверяет соседей, не вычисляет F, G, H), а лишь вызывает рекурсивную функцию далее, пока точка не будет соответствовать правилам перхода, это и значительно увеличивает скорость поиска. Об этом можно прочитать по ссылке из поста. Цвет в свою очередь показывает принадлежность закрытому(желтый) и открытому(синий) спискам, поэтому все честно)
А Декстра слева ушел далеко, потому что правой стороне надо было еще искать путь обогнуть стену. Если оставить две точки на пустом поле ваше утверждение будет верным, как только появляются препятсвия, Дейкстра пойдет неравномерно.
А Декстра слева ушел далеко, потому что правой стороне надо было еще искать путь обогнуть стену. Если оставить две точки на пустом поле ваше утверждение будет верным, как только появляются препятсвия, Дейкстра пойдет неравномерно.
JPS тоже рекурентно просматривает множество клеток, но он не совершает с ними много операций
Сложность от этого не меняется и остается линейной количеству просмотренных клеток (Дейкстра, конечно, медленее асимптотически, но этот тут не принципиально). Хотя бы подсветить их другим цветом и учесть в графиках количества пройденных клеток не помешало бы.
А Декстра слева ушел далеко, потому что правой стороне надо было еще искать путь обогнуть стену
Не должно быть посещено ни одной клетки, которая находится дальше от старта, чем целевая вершина, т.е. как минимум клетки в нижнем правом углу не должны быть посещены. Ну или меня глазомер обманывает :)
Про JPS спасибо за совет, обязательно введу какое-нибудь обозначение.
Дейкстра реализовывалась строго по «учебникам», поэтому поиск должен быть верным. Приложу парочку гифок для понятности.
Здесь вы на 100% правы
Здесь расстояние между точками тоже, только появляется стена(вверх короче чем вниз). Пока левая сторона обходит стену, правая продолжает расширятся.
Мы могли бы и прерывать поиск в одну сторону, когда видим, что превышен радиус, в котором находится выход, но одним из ключевых преимуществ Дейкстры является то, что не нужна вообще никакая информация о выходе, и, добавляя проверку радиуса, мы это теряем.
Также этот эффект наблюдается и в проверенной многими библиотеке PathFinding.js (на случай, если вы мне не верите, можете попробовать :) ). Это объясняется тем, что когда мы натыкаемся на стену, например, слева (как на гифке), поиск влево временно прекращается, поэтому и нарушается равенства радиуса поиска во всех направлениях.
Дейкстра реализовывалась строго по «учебникам», поэтому поиск должен быть верным. Приложу парочку гифок для понятности.
Gif #1
Здесь вы на 100% правы
Gif #2
Здесь расстояние между точками тоже, только появляется стена(вверх короче чем вниз). Пока левая сторона обходит стену, правая продолжает расширятся.
Мы могли бы и прерывать поиск в одну сторону, когда видим, что превышен радиус, в котором находится выход, но одним из ключевых преимуществ Дейкстры является то, что не нужна вообще никакая информация о выходе, и, добавляя проверку радиуса, мы это теряем.
Также этот эффект наблюдается и в проверенной многими библиотеке PathFinding.js (на случай, если вы мне не верите, можете попробовать :) ). Это объясняется тем, что когда мы натыкаемся на стену, например, слева (как на гифке), поиск влево временно прекращается, поэтому и нарушается равенства радиуса поиска во всех направлениях.
Не должно быть посещено ни одной клетки, которая находится дальше от старта, чем целевая вершина, т.е. как минимум клетки в нижнем правом углу не должны быть посещены. Ну или меня глазомер обманывает :)На похожем принципе и работает алгоритм А*.
В общем случае это не верно. Если стена в форме буквы П, то нам придется посетить клетки, которые находятся дальше* от старта.
*) по прямой.
ПС. Если вы можете быстро посчитать расстояние с учетом препятствий, то можете просто выбирать соседа с наименьшим расстоянием до финиша.
→ Скачать архив с программой можно с ЯД или с DropBox.Выкладывать программы без исходников нехорошо. :-)
А можете подробнее описать процедуру подсчёта времени. Это результаты в каких единицах?
Это в миллисекундах.
Время считают QTimer'ы, один считает общее время, второй считает время на паузы(отрисовка, переходы функций). Если использовать один и постоянно тормозить его, получалось вообще неточно. Эта часть статистики остро нуждается в доработке, желательно поискать какую-нибудь библиотеку для этого или, ещё лучше, попробовать QDebug или QTest для этого.
Время считают QTimer'ы, один считает общее время, второй считает время на паузы(отрисовка, переходы функций). Если использовать один и постоянно тормозить его, получалось вообще неточно. Эта часть статистики остро нуждается в доработке, желательно поискать какую-нибудь библиотеку для этого или, ещё лучше, попробовать QDebug или QTest для этого.
Эта ссылка должна быть в каждой статье про алгоритмы поиска пути в качестве опытного материала для исследования…
Она там есть в самом конце. Сейчас ещё раз отдельно вставлю.
Возможно, череда улучшений приведет к тому, что мы получим мощную библиотеку с алгоритмами, а программа станет приятной демкой для неё (Как PathFinding.js, только лучше).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Попытки сделать изучение алгоритмов поиска пути проще