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

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

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

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

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

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


dijkstra ucs
person John    schedule 19.10.2012    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Время работы такое же, но мы по-другому смотрим?

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

person Fred Foo    schedule 19.10.2012
comment
Давайте придерживаться конечных графов (возможно, очень больших, но все же конечных). тогда как я могу доказать, что оба алгоритма имеют одинаковое время работы? - person John; 19.10.2012
comment
@John: переписывая псевдокод любого алгоритма, пока не найдете другой. Это может быть сложно, потому что диаграмма Дейкстры обычно представлена ​​для конечных графов, полностью хранящихся в памяти, а UCS - для потенциально бесконечных графов, представленных как функции генерации ребер. - person Fred Foo; 19.10.2012
comment
Я согласен с тем, что вы сказали, но в моем случае вот что я хочу доказать: учитывая карту городов (график), я хочу доказать, что оба алгоритма имеют одинаковую временную сложность, чтобы найти оптимальное решение. - person John; 19.10.2012