Сложность времени - Двунаправленная Dijkstra

Question

Я хочу знать временную сложность двунаправленного алгоритма Дейкстры.

Нормальный Дейкстра, использующий Min-Heap, имеет O(n log n + m), Я думаю, что двунаправленный остается неизменным. Однако Википедия предполагает, что улучшение двунаправленного поиска в целом может быть выражено в О-нотации.

Можно ли это рассчитать и для двунаправленной Дейкстры и как?

Answer 1

В основном двунаправленный подход стоил вдвое больше однонаправленной обработки полуразмерного графа. Для экспоненциальных алгоритмов перебора это огромный выигрыш (от O (mⁿ) до O (2 * (m^{n / 2})).
Для Джикстра наихудший случай остается в основном таким же.

Однако сложность времени, возможно, не лучший показатель для оценки эффективности.

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

Интуитивно понятно, что если R - прямое расстояние между началом и концом, стоимость прямого поиска будет равна O (R²), тогда как двунаправленный подход будет в O (2 * (R / 2)²), то есть в 2 раза быстрее.,

эта статья охватывает тему довольно хорошо.

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