Алгоритм Дейкстры против поиска равномерной стоимости (временная сложность)

Question

Мой вопрос заключается в следующем: по разным данным, алгоритм Дейкстры - не что иное, как вариант поиска с равномерной стоимостью. Мы знаем, что алгоритм Дейкстры находит кратчайший путь между источником и всеми пунктами назначения (один источник). Однако мы всегда можем изменить Dijkstra, чтобы найти кратчайший путь между START и состоянием GOAL (когда цель извлекается из очереди с приоритетами, мы просто останавливаемся); но при этом в худшем случае все равно будет найден кратчайший путь от START ко всем остальным узлам (предположим, что целью является самый дальний узел на графике).

Если мы реализуем алгоритм Дейкстры с использованием кучи с минимальным приоритетом, время выполнения будет O(V log V +E), где E - это число ребер, а V - количество вершин.

Поскольку Uniform Cost Search - это то же самое, что Dijkstra (слегка отличающаяся реализация), тогда время выполнения UCS должно быть похоже на Dijkstra, верно? Однако, согласно моему классу искусственного интеллекта, Поиск Унифицированной стоимости является экспоненциальным в худшем случае, и он принимает O (b^{1 + [C* / ε]}), где C* - стоимость оптимального решения. (б - фактор ветвления)

Как оба алгоритма могут быть одинаковыми при разном времени выполнения? Время выполнения одинаково, но то, как мы смотрим на него, отличается?

Буду признателен за вашу помощь:):) Спасибо

Answer 1

Время выполнения одинаково, но то, как мы смотрим на него, отличается?

Да. Поиск с равномерной стоимостью можно использовать на бесконечно больших графах, на которых оригинальный алгоритм Дейкстры никогда не закончится. В таких ситуациях бесполезно определять сложность в терминах V и E, так как оба могут быть бесконечными, а полученная цифра big-O не имеет смысла.