균일 비용 검색과 Dijkstra의 알고리즘의 차이점은 무엇입니까?
모든 컴퓨터 과학 학생 (저를 포함하여 제가 CS 학사 학위를 받았을 때)은 아마도 유명한 단일 소스 최단 경로 Dijkstra의 알고리즘 (DA)을 접했을 것입니다 . 인공 지능에 대한 입문 과정 ( 몇 년 전 학사 과정에서 했던 것처럼)도 수강 했다면, 일부 검색 알고리즘, 특히 UCS (Uniform Cost Search) 도 접했을 것 입니다.
웹의 일부 기사 (예 : DA의 Wikipedia 기사 )에서는 DA (또는 그 변형)가 UCS와 동일하다고 말합니다. 유명한 Norvig와 Russell의 저서 인 Artificial Intelligence : A Modern Approach (3rd edition)는
Dijkstra (1959) 의 2 점 최단 경로 알고리즘 은 균일 비용 검색의 원점입니다. 이 작품은 또한 탐색 및 프론티어 세트 (폐쇄 및 공개 목록)의 아이디어를 도입했습니다.
DA가 UCS와 정확히 얼마나 일치합니까?
답변
내 질문에 대한 답은 논문 Position Paper : Dijkstra 's Algorithm vs Uniform Cost Search 또는 A Case Against Dijkstra 's Algorithm (2011), 특히 DA 및 UCS의 유사성 섹션 에서 찾을 수 있으므로 모든 세부 사항에 대해이 문서를 읽어야합니다.
DA와 UCS는 논리적으로 동일하지만 (즉, 동일한 정점을 동일한 순서로 처리) 다르게 수행합니다. 특히 단일 소스 DA와 UCS 의 주요 실질적인 차이점은 DA에서는 모든 노드가 처음에 우선 순위 대기열에 삽입되고 UCS 노드에서는 느리게 삽입된다는 것입니다.
다음은 DA의 의사 코드 (인용 된 논문에서 발췌)입니다.
다음은 BFS (Best-First Search)의 의사 코드이며, UCS는 특별한 경우입니다. 실제로 이것은 UCS의 의사 코드입니다.$g(n)$ 소스 노드에서 경로의 비용입니다. $n$ (제목은 이것이 BFS의 의사 코드임을 나타내지 만).
