Gonagi

최단경로탐색_알고리즘

11 min read

Dijkstra

음이 아닌 간선의 가중치를 가진 그래프에서 두 정점 사이의 최단 거리를 찾는 알고리즘

  • 출발 지점을 기준으로 영역을 확장하여 검색하고 목적 지점인지 조사하는 과정을 목적지를 찾을 때까지 반복한다. 이 때, 정점 간 거리보다 이웃 경로의 거리가 더 짧으면 해당 거리를 짧은 거리로 업데이트 한다.
  • 1956년 Edsger W. Dijkstra가 개발함
  • 음수 가중치 간선을 다룰 수 없으며, 불필요한 간선들을 모두 체크해야 해서 거리가 길수록 탐색 시간이 비례하기 때문에 잘 안쓴다.(이후, 개선된 알고리즘을 사용한다.)

A*

현재까지의 경로와 목표 까지의 예상 경로를 결합해 짧은 경로를 탐색하는 알고리즘

  • 공식을 사용하여 경로를 탐색한다.
    • : 출발점에서 현재 위치까지의 실제 거리
    • : 현재 위치에서 목표 지점까지의 예상거리(Heuristic 함수), 추정값
  • Heuristic 함수를 사용하여 가장 적절한 탐색 방향을 평가한 후 탐색을 진행하며, 탐색이 잘못되었을 경우 다시 뒤로 돌아와 다른 방향을 탐색하여 최단 경로를 산출한다.
  • 1968년 Peter Hart, Nils Nilsson and Bertram Raphae가 개발함
  • Dijkstra 알고리즘보다 빠르지만, 경로를 탐색하는데 있어 여전히 많은 정점을 방문해야 한다.

CH(Contraction Hierarchy)

단축 경로를 생성해서 계층을 두고 탐색한다.

  • 적절하게 지름길을 만들어두고 효율적으로 탐색한다.
  • 정점 사이에 랭킹을 두고, 랭킹이 높아지는 쪽으로만 탐색하게 하여 더 효율적으로 탐색한다.
  • 전처리를 하기 때문에 쿼리 속도가 빠르지만 간선의 비용에 변동이 생기면 지름길을 만드는 작업, 전처리를 다시 수행해야 한다.

  • 단축 경로 생성(Contraction)

    • 지름길 추가와 비용 전처리를 동시에 진행한다.
    1. rank 부여(Node Ordering)
      • 노드를 정렬하는거에 따라 생성되는 shortcut의 양상과 개수가 달라진다.
      • 적절하게 정렬하기 위해 Edge Difference(v로 인해 도입된 지름길의 수 - v와 인접한 간선의 개수) Heuristic 함수를 활용한다.
      • Edge Difference 값이 작을수록 먼저 contract 하기 용이한 node이다.
      • 따라서 각 노드에 대해 edge difference 값을 계산한 후 이에 따라 우선순위 큐에 삽입하여 node ordering을 진행한다.
    2. 노드의 rank가 낮은 순으로 정점을 뽑아가며, 더 높은 order만을 고려해 지름길을 만든다.
      • 검은색 점선과 실선이 원본 간선인 그래프에서 정점의 rank를 매기고 1번 정점을 Contraction하면 빨간색 실선의 지름길이 추가된다.
      • 3 → 4 는 P(3, 5, 4)가 최단 경로이므로 P(3, 1, 4)의 지름길은 추가되지 않는다.
      • 각 노드가 contract 될 때마다 edge difference 값을 계산할 우선순위 큐를 다시 갱신해야 한다.
        • 하나의 노드를 contract 한 뒤, 우선순위 큐에서 다음으로 뽑힐 node에 대해 다시 edge difference를 계산한다. 해당 값이 여전히 작으면 계속 진행하고, 그게 아니라면 우선순위 큐를 업데이트하여 똑같은 과정을 반복한다.

  • 계층을 두고 탐색(Hierarchies)

    1. 양방향 다익스트라를 사용해 출도착 지점으로부터 상위 rank로 향하는 arc로만 탐색한다.(우선순위 큐 사용)
      • 정방향 검색(forward search) : upward graph(node order가 높아지는 쪽의 간선만 남긴 그래프)에서 출발지로부터 노드를 탐색하는 것
      • 역방향 검색(backward search) : downward graph(node order가 낮아지는 쪽의 간선만 남긴 그래프)에서 도착지로부터 노드를 탐색하는 것
      • 정방향 검색과 역방향 검색의 탐색 공간이 서로 겹치는 부분이 생기면, 각각의 검색에서 우선순위 큐에 있는 모든 key에 대해 임시 최단 경로를 추적한다. 그리고 모든 key가 처음 겹쳤을 때의 최단 경로보다 큰 게 확인이 되면 쿼리를 중단한다.
    2. 최단 경로를 찾았으면 해당 경로에 대해 unpacking 단계를 수행하여 원본 node, edge를 얻어온 후 결과를 응답한다.

CCH(Customizable Contraction Hierarchy)

CH를 기반으로 Customization 단계가 추가된 알고리즘

  • 그래프의 연결 관계가 같다면 항상 같은 지름길이 생기고, 간선 비용에 변동이 생겨도 해당 지름길의 비용만 수정하면 된다.
  • 빠르고 성능이 균일하지만, 전처리 시간이 길다.

  • 단축 경로 생성(Contraction, Metric-Independent-Preprocessing)

    • 지름길 추가와 비용 전처리를 나눠서 작업한다.
    1. rank 부여(Node Ordering)
      • CH와 동일
    2. 그래프의 형태만 보고 지름길로 사용할 수 있는 간선 추가
      • 최단 경로와 상관 없이 인접한 모든 정점들 사이에 지름길을 추가한다.
      • Contraction 했을 때 P(3, 1, 4)의 지름길이 추가된다.
      • 비용을 고려하지 않기 때문에 shortcut이 더 많이 생성될 수 있다. 단, shortcut을 추가할 때 CH와 마찬가지로 현재 정점의 rank보다 더 높은 rank를 가진 정점만 고려한다.
      • shortcut의 비용은 ♾️으로 초기화 한다.

  • 각 간선마다의 비용 전처리(Metric Customization, Metric-Dependent-Customization)

    • 실시간 교통정보, 도로 상태 등 간선의 비용이 변화함에 따라 주기적으로 업데이트 한다.
    • 최초 Customization 이후에 일부 간선의 비용만 바뀌는 경우, 필요한 간선의 비용만 골라서 Customize 한다.
      • 비용이 바뀐 arc와 바뀐 arc에 영향을 받을 상위 arc들을 rank 기준으로 우선순위 큐에 넣고 큐가 빌때까지 Customize를 진행한다.
    1. Basic Customization
      • 낮은 rank의 노드부터 bottom-up으로 순회하며 shortcut의 비용을 업데이트 한다.
      • lower triangle 이용
        • C(v, w) = min{C(v, w), C(v, u) + C(u, w)}
    2. Perfect Customization
      • 높은 rank의 노드부터 top-down으로 순회하며 추가적인 변경이 필요한 비용에 대해 업데이트를 하고 필요 없는 arc(shortcut 포함) 데이터를 삭제한다.
      • middle triangles, upper triangle 이용
        • C(u, w) = min{C(u, w), C(u, v) + C(v, w)}
        • C(u, v) = min{C(u, v), C(u, w) + C(w, v)}
    • Preprocessing 단계에서 생성된 Graph의 연결성과 노드의 rank를 이용하여 노드의 관계를 3가지로 구분한다.
      • lower triangles : v → u → w
      • middle triangles : u → v → w
      • upper triangles : u → w → v

  • 계층을 두고 탐색(Hierarchies)

    • rank가 높아지는 쪽으로만 탐색한다.
    • 양방향 다익스트라로 탐색할 수도 있으나 Elimination Tree를 이용해 우선순위 큐 없이 탐색할 수 있다.
      • Elimination Tree : CCH 그래프에서 각 정점마다 상위 rank인 이웃 중 rank가 가장 적은 정점으로 가는 간선만 남겨두어 트리 형태로 만든 것
      1. forward/ backward 탐색에서 사용할 최단거리 저장 배열인 d_f, d_b 를 ♾️으로 초기화한다.
      2. Elimination Tree에서 s, t의 최소 공통 조상인 x를 구한다.
      3. s → x 트리 경로의 정점을 순서대로 순회하며 d_f를 relax 한다.
      4. t → x 트리 경로의 정점을 순서대로 순회하며 d_b를 relax 한다.
      5. d_f + d_b가 최소가 되는 r을 지나는 경로가 최단 경로가 된다.

그래프 뷰

백링크