균일 비용 검색과 Dijkstra의 알고리즘의 차이점은 무엇입니까?

균일 비용 검색과 Dijkstra의 알고리즘의 차이점은 무엇입니까?

---

균일 비용 검색 과 Dijkstra의 알고리즘 의 차이점이 무엇인지 궁금 합니다 . 그들은 같은 알고리즘 인 것 같습니다.

---

더 잘 알려진 Dijkstra의 알고리즘은 목표 상태가없고 모든 노드가 우선 순위 대기열에서 제거 될 때까지, 즉 모든 노드에 대한 최단 경로 ( 목표 노드가 아닌) 결정되었습니다.

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

---

Dijkstra의 알고리즘 은 그래프의 루트에서 다른 모든 노드 로의 최단 경로를 검색하는 반면 균일 비용은 목표 노드에 대한 비용 측면에서 최단 경로를 검색 합니다 .

또한 균일 한 비용은 공간 요구 사항이 적은 반면, 우선 순위 대기열은 시작시 무한한 비용으로 모든 노드를 대기열에 추가하는 Dijkstra와 달리 "게으르게"채워집니다.

---

NotAUser, dreaMone 및 Bruno Calza의 다른 답변 편집

Dijkstra의 알고리즘은 루트 노드에서 다른 모든 노드까지의 최단 경로를 찾습니다. 균일 비용은 루트 노드에서 목표 노드까지의 비용 측면에서 최단 경로를 검색합니다. 균일 비용 검색은 모든 지점에 대한 최단 경로가 아닌 단일 종료 지점에 대한 단일 최단 경로를 찾는 데 초점을 맞춘 Dijkstra의 알고리즘입니다.

UCS는 종료 지점이 발견되는 즉시 중지하여이를 수행합니다. Dijkstra의 경우 목표 상태가 없으며 모든 노드가 우선 순위 대기열에서 제거 될 때까지, 즉 목표 노드뿐 아니라 모든 노드에 대한 최단 경로가 결정될 때까지 처리가 계속됩니다.

UCS는 공간 요구 사항이 적으며, Dijkstra와 달리 우선 순위 대기열이 점진적으로 채워져 시작시 모든 노드를 무한 비용으로 대기열에 추가합니다.

위의 사항으로 인해 Dijkstra는 UCS보다 시간이 더 많이 걸립니다.

UCS는 일반적으로 나무에서 공식화되고 Dijkstra는 일반 그래프에서 사용됩니다.

Djikstra는 전체 그래프가 입력으로 제공되는 명시 적 그래프에만 적용됩니다. UCS는 소스 정점에서 시작하여 그래프의 필요한 부분을 점차적으로 횡단합니다. 따라서 명시 적 그래프와 암시 적 그래프 (상태 / 노드가 생성되는 위치) 모두에 적용됩니다.

---

둘 다에 대한 유사점과 차이점에 대해 이야기하는 논문이 있습니다.

http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/view/4017/4357

참고 URL : https://stackoverflow.com/questions/12806452/whats-the-difference-between-uniform-cost-search-and-dijkstras-algorithm