Подтвердить что ты не робот

Какая разница между поиском единообразной стоимости и алгоритмом Дейкстры?

Мне было интересно узнать, в чем разница между обычным поиском и алгоритмом Дейкстры. Они, похоже, являются одним и тем же алгоритмом.

4b9b3361

ОТВЕТЫ

Ответ 1

Алгоритм Дейкстры, который, возможно, более известен, можно рассматривать как вариант поиска по единой стоимости, где нет целевого состояния и обработка продолжается до тех пор, пока все узлы не будут удалены из приоритетной очереди, т.е. до кратчайших путей ко всем узлам (а не только к цель node)

http://en.wikipedia.org/wiki/Uniform-cost_search#Relationship_to_other_algorithms

Ответ 2

Алгоритм Dijkstra ищет кратчайшие пути от корня до каждого другого node в графе, тогда как единообразная стоимость ищет кратчайшие пути с точки зрения стоимости до цели node.

Кроме того, равномерная стоимость имеет меньше требований к пространству, тогда как очередь приоритетов заполняется "лениво", противоположная Dijkstra, которая добавляет все узлы в очередь при запуске с бесконечной стоимостью.

Ответ 3

Компиляция других ответов NotAUser, dreaMone и Bruno Calza

Dijkstra Algorithm находит самый короткий путь от корня node до всех остальных node. равномерная стоимость ищет кратчайшие пути с точки зрения стоимости от root node до цели node. Равномерный поиск затрат - это алгоритм Dijkstra, который ориентирован на поиск одного кратчайшего пути к одной конечной точке, а не кратчайший путь к каждой точке.

UCS делает это, останавливаясь, как только будет найдена конечная точка. Для Dijkstra не существует состояния цели и обработки продолжается до тех пор, пока все узлы не будут удалены из очереди приоритетов, то есть до тех пор, пока не будут определены кратчайшие пути ко всем узлам (а не только цель node).

UCS имеет меньше требований к пространству, где очередь приоритетов заполняется постепенно, в отличие от Dijkstra's, которая добавляет все узлы в очередь при запуске с бесконечной стоимостью.

В результате вышеуказанных пунктов Дикстра занимает больше времени, чем UCS

UCS обычно формулируется на деревьях, а Dijkstra используется на общих графах

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