Действительно ли A * лучше, чем Дейкстра в поиске путей в реальном мире?

Я разрабатываю программу поиска пути. Теоретически говорят, что А * лучше, чем Дейкстра. Фактически, последний является частным случаем первого. Однако, при тестировании в реальном мире, я начинаю сомневаться, что A * действительно лучше?

Я использовал данные Нью-Йорка, от 9-й вызов реализации DIMACS - кратчайшие пути, в котором даны широта и долгота node.

При применении A * мне нужно рассчитать сферическое расстояние между двумя точками, используя Формулу Хаверсина, которая включает в себя sin, cos, arcsin, square root. Все они очень трудоемкие.

В результате получается

Использование Dijkstra: 39.953 ms, расширенные узлы 256540.

Использование A *, 108.475 ms, расширенных узлов 255135.

Заметив, что в * мы расширили менее 1405 узлов. Однако время для вычисления эвристики намного больше, чем это было спасено.

По моему мнению, причина в том, что на очень большом реальном графике вес эвристики будет очень мал, и его эффект можно игнорировать, а время вычисления доминирует.

Ответ 1

Я думаю, что вы более или менее теряете точку A *. Он призван быть очень эффективным алгоритмом, частично за счет намеренного выполнения большего количества работы, но с дешевой эвристикой, и вы как бы разрываете это на биты, обременяя его тяжелой чрезвычайно точной эвристикой прогноза.

Для выбора node в * вы должны просто использовать приближение расстояния. Просто используя (latdiff ^ 2) + (lngdiff ^ 2), поскольку приблизительное расстояние должно сделать ваш алгоритм намного более действенным, чем Дейкстра, и не дать гораздо худших результатов в любом реальном сценарии. Фактически, результаты должны быть точно такими же, если вы правильно рассчитали пройденное расстояние на выбранном node с помощью Haversine. Просто используйте дешевый алгоритм для выбора потенциальных последующих обходов.

Ответ 2

A* можно свести к Дейкстре, установив некоторые тривиальные параметры. Существует три возможных способа, которыми он не улучшается на Дейкстре:

Используемая эвристика неверна: это не так называемая допустимая эвристика. A* должен использовать эвристику, которая не переоценивает расстояние до цели как часть своей функции стоимости.
Эвристика слишком дорога для расчета.
Структура графика в реальном времени является специальной.

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

Ответ 3

Как все еще во вселенной, есть компромисс. Вы можете взять алгоритм dijkstra, чтобы точно рассчитать эвристику, но это могло бы победить цель, не так ли?

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

Фактически, более точные геометрические расчеты, которые не основаны на фактических данных, не обязательно дают вам лучшее направление. Пока они не основаны на данных, все эти эвристики дают вам только правильное направление (in).

Ответ 4

В целом A * более эффективен, чем Dijkstra, но на самом деле это зависит от эвристической функции, которую вы используете в *. Вам понадобится h (n), который оптимистичен и найдет самый дешевый путь, h (n) должен быть меньше истинной стоимости. Если h (n) >= стоимость, то вы попадете в ситуацию, подобную той, которую вы описали.

Не могли бы вы разместить свою эвристическую функцию?

Ответ 5

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

Если вы сравниваете Dijkstra vs A * при навигации из лабиринта, где каждый проход соответствует одному краю графа, вероятно, очень мало различий в производительности. С другой стороны, если граф имеет много ребер между "отдаленными" узлами, разница может быть довольно драматичной. Подумайте о роботе (или персонаже компьютерной игры, управляемом AI), проводящем почти открытую местность с несколькими препятствиями.

Я хочу сказать, что, несмотря на то, что набор данных в Нью-Йорке, который вы использовали, определенно является хорошим примером "реального мира", он не является репрезентативным для всех проблем поиска путей в реальном мире.