Comments 14
Когда я был студентом, у нас это была лабораторка на первом семестре второго курса, которую делал каждый студент, и почти все - успешно. А вы целую статью написали...
Диагональные ребра в граф не включать - это несколько ускорит работу алгоритма. Полученную ломаную линию сгладить при необходимости диагональными линиями.
Вместо MaxSlope использовать весовые коэффициенты, учитывающие не только расстояние, но и угол наклона.
У данного алгоритма есть недостаток. При нахождения пути на непрерывных пространствах алгоритм не дает оптимальный путь. Например, на изображении зеленый путь явно короче.
Необходимо учитывать все возможные траектории: https://en.wikipedia.org/wiki/Any-angle_path_planning
Занудства ради, утверждение, что "алгоритм Дейкстры при нахождении пути на непрерывных пространствах не даёт оптимальный путь" означает примерно то же, что и "топор плохо подходит для рисования акварелью". Алгоритм Дейкстры и непрерывные пространства находятся в разных областях математики и в разных, практически не пересекающихся, сферах задач.
А вот это уже — правильная реализация алгоритма Дейкстры. Спасибо, что исправили вашу статью.
Есть несколько предложений по коду:
GetAllAdjacentVertices можно сократить раз в 10, если завести константый массив на 8 позиций со сдвигами +-1 для координат соседей. Или просто пустить два цикла от -1 до 1.
Что-то вроде этого (я попытался в C#, но не гарантирую, что код ниже компилируется. Но идея должна быть понятна):
for(dx = -1; dx <= 1; ++dx) {
for (dy = -1; dy <= 1; ++dy) {
int nx = v.Coordinate.i + dx;
int ny = v.Coordinate.j + dy;
if ((dx == 0 && dy == 0) || nx < 0 || ny < 0 || nx == N || ny == M) continue;
list.Add(Vertices[nx, ny]);
}
}
return list;ConcurrentPriorityQueue вам не нужен, хватит и PriorityQueue, у вас же нет никакой многопоточности.
Я бы сказал, почти правильная реализация. Всё же условием останова следовало бы предпочесть вариант "целевая вершина достигнута И ни один кандидат в очереди не лучше уже найденного пути". Достаточно легко представить граф, где целевая вершина может быть сначала достигнута по менее оптимальному маршруту, чем это возможно, и этот маршрут нашёлся бы уже буквально на следующей итерации (хотя это и не обязательно, зависит от структуры графа), если бы мы опрометчиво не прервали поиск. Кажется, на графе, представленном обычной регулярной сеткой "без сюрпризов", такого случиться не должно, но в случае с графами произвольного вида или когда в игру вступают веса (как в данном случае: "регулярная сетка + высоты"), такие ситуации вполне возможны.
Да не, все правильно с остановом. isVisited выставляется, когда вершина вынимается из очереди, т.е. она является минимальной из пока не посещенных. В тот момент никаких более коротких путей в нее быть не может.
Да, действительно, моя ошибка. Видимо, перепутал с А* (мне в основном приходится с ним сталкиваться), там из-за эвристики такая ситуация возможна. А в Дейкстре, в силу его жадности, извлечение целевой вершины из очереди эквивалентно нахождению оптимального пути до неё.
Вы что-то путаете. Если евристика удовлетворяет необходимым в A* условиям, то даже с ней, если вершина выбирается из очереди, то до нее известен кратчайший путь.
Если же у вас могут кучу раз улучшаться одни и те же вершины, уже ранее рассмотренные, то это не A*, а форд-беллман или волновой алгоритм получается. И работает эта вся радость на порядок хуже дейкстры.
В моём случае строгая математичность A* (вернее, его требований к эвристике, на чём и основана гарантия его оптимальности), к сожалению, разбивается о суровую реальность.
Если мы оптимизируем не тот же параметр, в контексте которого можем точно посчитать эвристику (например, эвристику мы считаем как расстояние, а оптимизируем время проезда, и, значит, эвристическое расстояние также нужно перевести во время), наступает момент компромиссов между оптимистичностью эвристики и количеством перебираемых вершин, что напрямую влияет на производительность.
Под "точно посчитать эвристику" я имею ввиду "с минимальным возможным оптимизмом, но не хуже", т.е. так, чтобы не рассматривать ни одной лишней вершины, но рассмотреть все необходимые для гарантии оптимальности. То есть h(x) = 0 -- максимально оптимистичная эвристика, но с ней A* вырождается в Дейкстру и перебирает огромное количество "лишних" вершин, чего мы как раз пытаемся избежать.
Поэтому приходится как-то выкручиваться, чтобы и рыбку съесть, и в рамках накалываемых на время расчёта ограничений остаться.
Но это всё, конечно, не имеет отношения к чистому строго математическому A* или Дейкстре (и к данной статье в частности), это скорее уже сложности, вызванные особенностями предметной области. Моё профессиональное искажение подсунуло эти сложности туда, где их исходно нет)
Достаточно, чтобы эвристика не переоценивала реальную метрику (вермя у вас). Можете сначала оценить расстояние снизу и поделить на максимальную скорость передвижения, например. Если у вас эвристика переоценивает метрику, то вы можете не только больше вершин рассмотреть, чем надо — вы вообще можете эти вершины рассматривать очень много лишних раз. И тупая дейкстра будет быстрее. Но это, правда, для специфичных графов. Может, в вашем случае этот странный алгоритм действительно работает быстрее дейкстры. Хотя, я уверн, что подкрутив эвристику вы его еще ускорите.
Идея с оптимизацией поиска смежных вершин отличная. Добавил изменения в проект.
О том, как алгоритм Дейкстры реализовывал и некоторых его применениях