Почему A * работает быстрее, чем алгоритм Дейкстры?

Я думаю, что временная сложность A *, указанная в Википедии, неверна (или, по крайней мере, вводит в заблуждение). Эта временная сложность, по-видимому, учитывает только количество расширенных состояний при поиске, а не время, необходимое для определения того, какие состояния исследовать.

Чтобы быть эффективным, поиск A * должен хранить очередь приоритетов, содержащую, какие узлы на периферии должны быть исследованы, и он должен иметь возможность вызывать кнопку уменьшения для этих приоритетов. Время выполнения для этого в худшем случае составляет O (n log n + m), если реализовано с использованием очереди с хорошим приоритетом. Следовательно, в худшем случае можно ожидать, что A * перейдет в алгоритм Дейкстры. При хорошей эвристике A * не будет расширять все узлы и ребра, как алгоритм Дейкстры, что является основной причиной того, почему A * работает быстрее.

Конечно, временная сложность поиска A * должна учитывать затраты на вычисление эвристики. Некоторые сложные эвристики могут быть не вычислимы за время O (1), и в этом случае время выполнения для A * может быть хуже, чем алгоритм Дейкстры.

Надеюсь это поможет!

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